7,129
个编辑
更改
跳到导航
跳到搜索
第8行：
第8行： + 第21行：
第22行： + 第41行：
第43行： + 第52行：
第55行： + 第64行：
第68行： + 第72行：
第77行： − + +
无编辑摘要
在[[图论 Graph theory]]中，图中顶点的'''<font color="#ff8000">度 Degree</font>'''(或价)是入射到该顶点的边的数量。在'''<font color="#ff8000">多重图 Multigraph</font>'''中，'''<font color="#ff8000">自环 Loops</font>'''会被计算两次。顶点的度数可表示为<math>\deg(v)</math>或<math>\deg v</math>。一个图<math>G</math>的最大度值可表示为<math>\Delta(G)</math>，最小度值可表示为 <math>\delta(G)</math>。在右侧的多重图中，最大度值为5，最小度值为0。
在[[图论 Graph theory]]中，图中顶点的'''<font color="#ff8000">度 Degree</font>'''(或价)是入射到该顶点的边的数量。在'''<font color="#ff8000">多重图 Multigraph</font>'''中，'''<font color="#ff8000">自环 Loops</font>'''会被计算两次。顶点的度数可表示为<math>\deg(v)</math>或<math>\deg v</math>。一个图<math>G</math>的最大度值可表示为<math>\Delta(G)</math>，最小度值可表示为 <math>\delta(G)</math>。在右侧的多重图中，最大度值为5，最小度值为0。
在'''<font color="#ff8000">正则图 Regular Graph</font>'''中，每个顶点都具有相同的度数，因此我们可以将其称之为该图的度数。一个'''<font color="#ff8000">完全图 Complete Graph</font>'''(表示为<math>K_n</math>，其中<math>n</math>是图中顶点的数目)是一种特殊的正则图，它所有顶点都有最大度值，<math>n-1</math>。
在'''<font color="#ff8000">正则图 Regular Graph</font>'''中，每个顶点都具有相同的度数，因此我们可以将其称之为该图的度数。一个'''<font color="#ff8000">完全图 Complete Graph</font>'''(表示为<math>K_n</math>，其中<math>n</math>是图中顶点的数目)是一种特殊的正则图，它所有顶点都有最大度值，<math>n-1</math>。
此公式表明，在任何无向图中，拥有奇数度值的顶点的个数是偶数。这一阐释（以及度和公式)被称为'''<font color="#ff8000">握手引理 Handshaking Lemma</font>'''。该名称来自一个有趣的数学问题，即求证无论该群体内有多少人，与奇数个人握过手的人数总是偶数。
此公式表明，在任何无向图中，拥有奇数度值的顶点的个数是偶数。这一阐释（以及度和公式)被称为'''<font color="#ff8000">握手引理 Handshaking Lemma</font>'''。该名称来自一个有趣的数学问题，即求证无论该群体内有多少人，与奇数个人握过手的人数总是偶数。
<br>
==度序列==
==度序列==
一般来说，'''<font color="#ff8000">超图 Hypergraph</font>'''的度序列是其顶点度的非递增序列。如果一个序列是<math>k-uniform</math>超图的度序列，那么它即是<math>k-graphic</math>。特别地，<math>2</math>-graphic序列是图形。决定一个给定的序列是否是<math>k</math>-graphic可以在 <math>k=2</math>的多项式时间内通过Erdős–Gallai定理实现，但是当<math>k\ge 3</math>时该问题可转化为'''<font color="#ff8000">NP完全问题 NP-complete</font>'''<ref>{{Cite journal|last=Deza|first=Antoine|last2=Levin|first2=Asaf|last3=Meesum|first3=Syed M.|last4=Onn|first4=Shmuel|date=January 2018|title=Optimization over Degree Sequences|url=https://epubs.siam.org/doi/10.1137/17M1134482|journal=SIAM Journal on Discrete Mathematics|language=en|volume=32|issue=3|pages=2067–2079|doi=10.1137/17M1134482|issn=0895-4801|arxiv=1706.03951}}</ref>。
一般来说，'''<font color="#ff8000">超图 Hypergraph</font>'''的度序列是其顶点度的非递增序列。如果一个序列是<math>k-uniform</math>超图的度序列，那么它即是<math>k-graphic</math>。特别地，<math>2</math>-graphic序列是图形。决定一个给定的序列是否是<math>k</math>-graphic可以在 <math>k=2</math>的多项式时间内通过Erdős–Gallai定理实现，但是当<math>k\ge 3</math>时该问题可转化为'''<font color="#ff8000">NP完全问题 NP-complete</font>'''<ref>{{Cite journal|last=Deza|first=Antoine|last2=Levin|first2=Asaf|last3=Meesum|first3=Syed M.|last4=Onn|first4=Shmuel|date=January 2018|title=Optimization over Degree Sequences|url=https://epubs.siam.org/doi/10.1137/17M1134482|journal=SIAM Journal on Discrete Mathematics|language=en|volume=32|issue=3|pages=2067–2079|doi=10.1137/17M1134482|issn=0895-4801|arxiv=1706.03951}}</ref>。
<br>
==特殊值==
==特殊值==
*在有n个顶点的图中，度数为n-1的顶点叫作'''<font color="#ff8000">主导顶点 Dominating Vertex</font>'''
*在有n个顶点的图中，度数为n-1的顶点叫作'''<font color="#ff8000">主导顶点 Dominating Vertex</font>'''
<br>
==全局属性==
==全局属性==
*'''<font color="#ff8000">k简并图 K-Degenerate Graph </font>'''是其中每个子图最多具有度数为k的顶点的图。
*'''<font color="#ff8000">k简并图 K-Degenerate Graph </font>'''是其中每个子图最多具有度数为k的顶点的图。
<br>
==参阅==
==参阅==
*'''<font color="#ff8000">二分图的度序列 Degree Sequence For Bipartite Graphs </font>'''
*'''<font color="#ff8000">二分图的度序列 Degree Sequence For Bipartite Graphs </font>'''
<br>
==笔记==
==笔记==
{{reflist}}
{{reflist}}
<br>
==参考==
==参考==
* {{Citation|last=Diestel|first=Reinhard|title=Graph Theory|url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/|publisher=Springer-Verlag|place=Berlin, New York|edition=3rd}}.
* {{Citation|last=Diestel|first=Reinhard|title=Graph Theory|url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/|publisher=Springer-Verlag|place=Berlin, New York|edition=3rd}}.