3,094
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − {{#seo:+ − |keywords=图论,度 − |description=图论,度 − }} − − 图1：内含自环按度标记的图]] − 度 （Degree）在[[图论 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>。 − − ==握手引理 Handshaking Lemma== − − '''<font color="#ff8000">度和公式 Degree Sum Formula</font>'''表明，任意给定一个图<math>G=(V, E)</math>,都有 − − − :<math>\sum_{v \in V} \deg(v) = 2|E|\, </math> − − − 此公式表明，在任何无向图中，拥有奇数度值的顶点的个数是偶数。这一阐释（以及度和公式）被称为'''<font color="#ff8000">握手引理 Handshaking Lemma</font>'''。该名称来自一个有趣的数学问题，即求证无论该群体内有多少人，与奇数个人握过手的人数总是偶数。 − − <br> − − ==度序列== − − [[File:Conjugate-dessins.svg|thumb|200px| − 图2：同一度序列（3，2，2，2，2，1，1，1）的非同构图]] − − '''无向图的度序列'''是指将其各顶点度值按非递增方式排序，对于上述图是（5，3，3，2，2，1，0）。度序列是'''<font color="#ff8000">图不变量 Graph Invariant</font>'''，因此'''<font color="#ff8000">同构图 Non-isomorphic Graphs</font>'''（两个图中顶点的度值都相同，但形状不同）具有相同的度序列。然而，度序列通常不能唯一地标识一个图，在某些情况下，非同构图也会具有相同的度序列。 − − − '''<font color="#ff8000">度序列问题 Degree Sequence Problem</font>'''，是指寻找给定以非增方式排列的正整数的度序列的局部或全部图的问题。（序列尾部的零可能会被忽略，因为通过向图中添加适当数量的孤立顶点就可以轻松实现序列尾部不断加零。）一个序列是某个图的度序列，即一个度序列问题有解时，该序列称为'''图形序列'''。由于度和公式的存在，任何具有奇数和的序列，如（3，3，1） ，都不会是图的度序列。反之亦然：如果一个序列和是偶数，它就是重图的度序列。我们可以轻易地构造一个图：匹配奇数度值的顶点并成对连接起来，然后剩余的偶数度值顶点都连出一条边指向图形/起点本身。 − − − “一个给定的度序列是否可以用一个简单的图进行表示”是一个具有挑战性的问题。这个问题也称为'''<font color="#ff8000">图实现 Graph Realization Problem</font>'''问题，但它可以用'''<font color="#ff8000">Erdős–Gallai定理 Erdős–Gallai Theoreme</font>'''解决，也可以用'''<font color="#ff8000">Havel-Hakimi算法 Havel–Hakimi Algorithm</font>'''解决。 − − − 基于给定度序列寻找或估计可能的图的个数，是'''<font color="#ff8000">图枚举 Graph Enumeration</font>'''领域中的一个问题。 − − − 一般来说，'''<font color="#ff8000">超图 Hypergraph</font>'''的度序列是其顶点度的非递增序列。如果一个序列是<math>k</math>-uniform超图的度序列，那么它即是<math>k</math>-graphic。特别地，<math>2</math>-graphic序列是图形。决定一个给定的序列是否是<math>k</math>-graphic可以在 <math>k=2</math>的多项式时间内通过'''<font color="#ff8000">Erdős–Gallai定理 Erdős–Gallai Theoreme</font>'''实现，但是当<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> − − ==特殊值== − − [[File:Depth-first-tree.png|thumb|250px|图3：一个具有叶节点的无定向图]] − − − * 度数为0的顶点成为'''<font color="#ff8000">孤立顶点 Isolated Vertex</font>''' − − * 度数为1的顶点称为叶顶点或尾顶点，该顶点的入射边称为'''<font color="#ff8000">悬挂边 Pendant Edge</font>'''。在右侧的图中，{3,5}就是一个悬挂边。在图论中，该术语主要在研究'''<font color="#ff8000">树 Tree</font>'''时使用，特别是具有树形结构的数据。 − − * 在有n个顶点的图中，度数为n-1的顶点叫作'''<font color="#ff8000">主导顶点 Dominating Vertex</font>''' − − <br> − − ==全局属性== − − *如果一个图中的所有顶点的度值都为k，那么该图被称为'''<font color="#ff8000">''k''-正则图 ''k''-regular graph</font>'''，该图的度数也为k。同样的，同侧每两个顶点都具有相同度数的二分图叫作'''<font color="#ff8000">二分正则图 Biregular Graph</font>'''。 − − *当且仅当一个图具有0或2个奇数度的顶点时，无向连通图才具有'''<font color="#ff8000">欧拉路径 Eulerian Path</font>'''。 如果它具有0个奇数度的顶点，则欧拉路径为'''<font color="#ff8000">欧拉回路 Eulerian Circuit</font>'''。 − − *当且仅当每个顶点的度数最大值为1时称该图为有向图'''<font color="#ff8000">伪森林 Pseudoforest</font>'''。'''<font color="#ff8000">功能图 Functional Graph</font>'''是伪森林的特例，其中每个顶点的度数都恰好为1。 − − *根据布鲁克斯定理，除团簇或奇数循环外，任何图的色度数最大为Δ，而根据维辛定理，任何图的色度指数最大为Δ+ 1。 − − *'''<font color="#ff8000">k简并图 K-Degenerate Graph </font>'''是其中每个子图最多具有度数为k的顶点的图。 − − <br> − − ==参阅== − − *'''<font color="#ff8000">有向图的入度和出度 Indegree,Outdegree For Digraph</font>''' − − *'''<font color="#ff8000">度分布 Degree Distribution</font>''' − − *'''<font color="#ff8000">二分图的度序列 Degree Sequence For Bipartite Graphs </font>''' − − <br> − ==笔记== − − {{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|author-link=Paul Erdős|author2-link=Tibor Gallai|title=Gráfok előírt fokszámú pontokkal|language=hu|journal=Matematikai Lapok|volume=11|year=1960|pages=264–274|url=http://www.renyi.hu/~p_erdos/1961-05.pdf}}. − * {{Citation|author-link=V. J. Havel|year=1955|title=A remark on the existence of finite graphs|language=cs|journal=Časopis pro pěstování matematiky|volume=80|pages=477–480|url=http://eudml.org/doc/19050|accessdate=2019-04-23}} − * {{Citation|author-link=S. L. Hakimi|journal=Journal of the Society for Industrial and Applied Mathematics|pages=496–506|title=On realizability of a set of integers as degrees of the vertices of a linear graph. I|volume=10|year=1962}}. − * {{Citation|last=Sierksma|first=Gerard|last2=Hoogeveen|first2=Han|doi=10.1002/jgt.3190150209|number=2|journal=Journal of Graph Theory|pages=223–231|title=Seven criteria for integer sequences being graphic|volume=15|year=1991}}. − − <br> − ==编辑推荐== − [[File:顶点.png|400px}right|thumb|[https://campus.swarma.org/course/1754 巴拉巴西网络科学系列课程]]] − ===集智课程推荐=== − ====[https://campus.swarma.org/course/1745 漫谈图论的起源、发展与应用]==== − 本课程中，介绍了图论中的基本概念和网络科学使用的工具，可以帮助认识真实网络的关键性质。 − − − − ====[https://campus.swarma.org/course/1790 书籍领读：图论]==== − 本课程中，将讲解巴拉巴西网络科学书籍第一章图论。 − − − <br> − ---- − 本中文词条由[[用户:Ryan|Ryan]] 参与编译， [[用户:CecileLi|CecileLi]] 审校，[[用户:不是海绵宝宝|不是海绵宝宝]]编辑，欢迎在讨论页面留言。 − − '''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。''' − [[分类: 图论]]
重定向页面至节点度
#重定向 [[节点度]]
[[File:UndirectedDegrees (Loop).svg|thumb|