知识库详情
知识库

以“词条释义”的形式对比特币区块链技术中经常涉及的术语及基本概念进行专业化的阐释和解读。

近完全图
返回上级
BSV区块链编辑 2022-04-14 17:29 434

图是顶点和边的集合。如果图中的每个顶点之间都有一条边相连,则此图被称为“完全图”。如果在这个完全图中,移除相对于总边数较少的边,就生成了一个“近完全图”。

数学定义

假定一个具有个v顶点、e条边和亏格g的图。

计算X=(e-3v+6)/6

令⎡X⎤表示大于或等于X的最小整数。所有图都满足欧拉下界

g≥⎡X⎤

完全图有g=⎡X⎤,边界是饱和的。

可以从一个完整的图开始,删除p条边,使得剩余的图满足

  • 欧拉的下界是饱和的g=⎡X⎤
  • 图是连通的

令NC(n)表示从完全图Kn中可能移除的边的最大数量,使得无论哪些边被移除,上述两个属性都成立。有n条边的图,如果它可以通过从完全图Kn中移除p≤NC(n)条边而得到,那么我们就可以称它为近完全图

参考文献

比特币原理
区块链
拜占庭将军难题
简易支付验证(SPV)
小世界网络
近完全图
重复使用地址
元网(Metanet)
时间链
曼达拉网络
OP_RETURN的历史
椭圆曲线数字签名算法
P2SH