度 (图论)

This article "度 (图论)" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:度 (图论). Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

一个多重图，每个顶点上的数字即为该顶点的度数

在图论中，图的顶点的度指的是其相邻边的数量。如果是多重图，顶点自身组成的环计为两度。顶点$v$的度数记为$\deg(v)$。图G的最大度记为Δ(G)，最小度记为δ(G)。在正则图中，所有顶点的度数都相等。完全图K_n是正则图的特殊情况，所有顶点都是n-1度。

握手引理

给定一个图$G=(V,E)$，其顶点的度数总和满足

$\sum _{v\in V}\deg(v)=2|E|$。

上式表明，任意一个无向图只可能有偶数个奇数度数的顶点，这就是。握手引理源自一个知名的数学问题的证明：一群人中，和奇数个人握过手的人数必然是偶数。

度数序列

两个图不同构，但度数序列均为(3, 2, 2, 2, 2, 1, 1, 1)

无向图的度数序列是一个单调非增整数序列，由该图各顶点的度数组成。首段配图中图的度数序列为(5, 3, 3, 2, 2, 1, 0)。度数序列是，也就是说同构的图度数序列也相同。但不同构的图也可能有相同的度数序列，如配图所示。

度数序列问题指的是给定一个单调非增正整数序列，找出部分或全部的图，这些图的度数序列等于给定序列（度数序列末尾的零可以省略，因为它们仅可能代表图中的孤立点，属于平凡情形）。

参见

• 有向图的和
• 度分布

参考文献

1. REDIRECT Template:Delete

This article "度 (图论)" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:度 (图论). Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

This article "度 (图论)" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:度 (图论). Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

拓展阅读

This article "度 (图论)" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:度 (图论). Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• 承现峻
• 库拉托夫斯基定理
• Kataomoi
• 陳-高斯-博内定理
• 五龙潭(jinan)
• 图特定理
• 裕仁街

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

<addthis />