863
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − 本词条由Ryan初步翻译 由CecileLi初步审校+ + + + − − − In [[graph theory]], the '''degree''' (or '''valency''') of a [[vertex (graph theory)|vertex]] of a [[Graph (discrete mathematics)|graph]] is the number of [[edge (graph theory)|edges]] that are [[incidence (graph)|incident]] to the vertex, and in a [[multigraph]], [[loop (graph theory)|loop]]s are counted twice.<ref>Diestel p.5</ref> The degree of a vertex <math>v</math> is denoted <math>\deg(v)</math> or <math>\deg v</math>. The '''maximum degree''' of a graph <math>G</math>, denoted by <math>\Delta(G)</math>, and the '''minimum degree''' of a graph, denoted by <math>\delta(G)</math>, are the maximum and minimum degree of its vertices. In the multigraph on the right, the maximum degree is 5 and the minimum degree is 0. − − In graph theory, the degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex, and in a multigraph, loops are counted twice. The degree of a vertex <math>v</math> is denoted <math>\deg(v)</math> or <math>\deg v</math>. The maximum degree of a graph <math>G</math>, denoted by <math>\Delta(G)</math>, and the minimum degree of a graph, denoted by <math>\delta(G)</math>, are the maximum and minimum degree of its vertices. In the multigraph on the right, the maximum degree is 5 and the minimum degree is 0. − − − − In a [[regular graph]], every vertex has the same degree, and so we can speak of ''the'' degree of the graph. A [[complete graph]] (denoted <math>K_n</math>, where <math>n</math> is the number of vertices in the graph) is a special kind of regular graph where all vertices have the maximum degree, <math>n-1</math>. − − In a regular graph, every vertex has the same degree, and so we can speak of the degree of the graph. A complete graph (denoted <math>K_n</math>, where <math>n</math> is the number of vertices in the graph) is a special kind of regular graph where all vertices have the maximum degree, <math>n-1</math>. + − − ==Handshaking lemma 握手引理== − 握手引理 第37行：
第27行： + − The formula implies that in any undirected graph, the number of vertices with odd degree is even. This statement (as well as the degree sum formula) is known as the [[handshaking lemma]]. The latter name comes from a popular mathematical problem, to prove that in any group of people the number of people who have shaken hands with an odd number of other people from the group is even. − − The formula implies that in any undirected graph, the number of vertices with odd degree is even. This statement (as well as the degree sum formula) is known as the handshaking lemma. The latter name comes from a popular mathematical problem, to prove that in any group of people the number of people who have shaken hands with an odd number of other people from the group is even. − 此公式表明，在任何无向图中，拥有奇数度值的顶点的个数是偶数。这一阐释（以及度和公式)被称为'''<font color="#ff8000">握手引理 Handshaking Lemma</font>'''。该名称来自一个有趣的数学问题，即求证无论该群体内有多少人，与奇数个人握过手的人数总是偶数。+ − --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）标题涉及到的专业名词 要么标注一下标题要么标注一下正文~ − ==Degree sequence== − '''<font color="#ff8000">度序列 Degree Sequence</font>''' − − − The '''degree sequence''' of an undirected graph is the non-increasing sequence of its vertex degrees;<ref>Diestel p.216</ref> for the above graph it is (5, 3, 3, 2, 2, 1, 0). The degree sequence is a [[graph invariant]] so [[Graph isomorphism|isomorphic graphs]] have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a graph; in some cases, non-isomorphic graphs have the same degree sequence. − − The degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees; for the above graph it is (5, 3, 3, 2, 2, 1, 0). The degree sequence is a graph invariant so isomorphic graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a graph; in some cases, non-isomorphic graphs have the same degree sequence. − --[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]]) 【审校】不确定：“无向图的度序列是指将其各顶点度值按非递增方式排序”一句中的“非递增”改为“递减/并不是按递增方式排序的”+ − The '''degree sequence problem''' is the problem of finding some or all graphs with the degree sequence being a given non-increasing sequence of positive integers. (Trailing zeroes may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the graph.) A sequence which is the degree sequence of some graph, i.e. for which the degree sequence problem has a solution, is called a '''graphic''' or '''graphical sequence'''. As a consequence of the degree sum formula, any sequence with an odd sum, such as (3, 3, 1), cannot be realized as the degree sequence of a graph. The converse is also true: if a sequence has an even sum, it is the degree sequence of a multigraph. The construction of such a graph is straightforward: connect vertices with odd degrees in pairs by a [[matching (graph theory)|matching]], and fill out the remaining even degree counts by self-loops.+ − The degree sequence problem is the problem of finding some or all graphs with the degree sequence being a given non-increasing sequence of positive integers. (Trailing zeroes may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the graph.) A sequence which is the degree sequence of some graph, i.e. for which the degree sequence problem has a solution, is called a graphic or graphical sequence. As a consequence of the degree sum formula, any sequence with an odd sum, such as (3, 3, 1), cannot be realized as the degree sequence of a graph. The converse is also true: if a sequence has an even sum, it is the degree sequence of a multigraph. The construction of such a graph is straightforward: connect vertices with odd degrees in pairs by a matching, and fill out the remaining even degree counts by self-loops.+ − + − The question of whether a given degree sequence can be realized by a [[simple graph]] is more challenging. This problem is also called [[graph realization problem]] and can either be solved by the [[Erdős–Gallai theorem]] or the [[Havel–Hakimi algorithm]]. + − The question of whether a given degree sequence can be realized by a simple graph is more challenging. This problem is also called graph realization problem and can either be solved by the Erdős–Gallai theorem or the Havel–Hakimi algorithm. + + − “一个给定的度序列是否可以用一个简单的图进行表示”是一个具有挑战性的问题。这个问题也称为'''<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>'''解决。+ − The problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of [[graph enumeration]].+ − The problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of graph enumeration.+ − 基于给定度序列寻找或估计可能的图的个数，是'''<font color="#ff8000">图枚举 Graph Enumeration</font>'''领域中的一个问题。+ + + − More generally, the '''degree sequence''' of a [[hypergraph]] is the non-increasing sequence of its vertex degrees. A sequence is '''<math>k</math>-graphic''' if it is the degree sequence of some <math>k</math>-uniform hypergraph. In particular, a <math>2</math>-graphic sequence is graphic. Deciding if a given sequence is <math>k</math>-graphic is doable in [[Time complexity|polynomial time]] for <math>k=2</math> via the [[Erdős–Gallai theorem]] but is [[NP-completeness|NP-complete]] for all <math>k\ge 3</math> (Deza et al., 2018 <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>).+ − More generally, the degree sequence of a hypergraph is the non-increasing sequence of its vertex degrees. A sequence is <math>k</math>-graphic if it is the degree sequence of some <math>k</math>-uniform hypergraph. In particular, a <math>2</math>-graphic sequence is graphic. Deciding if a given sequence is <math>k</math>-graphic is doable in polynomial time for <math>k=2</math> via the Erdős–Gallai theorem but is NP-complete for all <math>k\ge 3</math> (Deza et al., 2018 ).+ − 一般来说，'''<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>'''(Deza et al. ，2018)。+ − + − 特殊值 − [[File:Depth-first-tree.png|thumb| − 图3：An undirected graph with leaf nodes 4, 5, 6, 7, 10, 11, and 12 一个具有叶节点的无定向图]] − − *A vertex with degree 0 is called an [[isolated vertex]]. − 度数为0的顶点成为'''<font color="#ff8000">孤立顶点 Isolated Vertex</font>''' − *A vertex with degree 1 is called a leaf vertex or end vertex, and the edge incident with that vertex is called a pendant edge. In the graph on the right, {3,5} is a pendant edge. This terminology is common in the study of [[tree (graph theory)|tree]]s in graph theory and especially [[tree (data structure)|tree]]s as [[data structure]]s. − 度数为1的顶点称为叶顶点或尾顶点，该顶点的入射边称为'''<font color="#ff8000">悬挂边 Pendant Edge</font>'''。在右侧的图中，{3,5}就是一个悬挂边。在图论中，该术语主要在研究'''<font color="#ff8000">树 Tree</font>'''时使用，特别是具有树形结构的数据。 − * A vertex with degree ''n'' − 1 in a graph on ''n'' vertices is called a [[dominating vertex]]. − 在有n个顶点的图中，度数为n-1的顶点叫作'''<font color="#ff8000">主导顶点 Dominating Vertex</font>''' − ==Global properties==+ − 全局属性 − *If each vertex of the graph has the same degree ''k'' the graph is called a [[regular graph|''k''-regular graph]] and the graph itself is said to have degree ''k''. Similarly, a [[bipartite graph]] in which every two vertices on the same side of the bipartition as each other have the same degree is called a [[biregular graph]]. − 如果一个图中的所有顶点的度值都为k，那么该图被称为'''<font color="#ff8000">''k''-正则图 ''k''-regular graph</font>'''，该图的度数也为k。同样的，同侧每两个顶点都具有相同度数的二分图叫作'''<font color="#ff8000">二分正则图 Biregular Graph</font>'''。 − *An undirected, connected graph has an [[Eulerian path]] if and only if it has either 0 or 2 vertices of odd degree. If it has 0 vertices of odd degree, the Eulerian path is an Eulerian circuit. − 当且仅当一个图具有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。 − *By [[Brooks' theorem]], any graph other than a clique or an odd cycle has [[chromatic number]] at most Δ, and by [[Vizing's theorem]] any graph has [[chromatic index]] at most Δ + 1. − 根据布鲁克斯定理，除团簇或奇数循环外，任何图的色度数最大为Δ，而根据维辛定理，任何图的色度指数最大为Δ+ 1。 − *A [[Degeneracy (graph theory)|''k''-degenerate graph]] is a graph in which each subgraph has a vertex of degree at most ''k''. − '''<font color="#ff8000">k简并图 K-Degenerate Graph </font>'''是其中每个子图最多具有度数为k的顶点的图。 − + − + − '''<font color="#ff8000">有向图的入度和出度 Indegree,Outdegree For Digraph</font>''' − *[[Degree distribution]] − '''<font color="#ff8000">度分布 Degree Distribution</font>''' − *[[bipartite graph|degree sequence]] for bipartite graphs − − + 第127行：
第84行： − + 第309行：
第266行： − + − − Category:Graph theory − − 范畴: 图论 − − <noinclude> − − <small>This page was moved from [[wikipedia:en:Degree (graph theory)]]. Its edit history can be viewed at [[度/edithistory]]</small></noinclude> − + +
无编辑摘要
{{#seo:
|keywords=图论,度
|description=图论,度
}}
[[File:UndirectedDegrees (Loop).svg|thumb|
[[File:UndirectedDegrees (Loop).svg|thumb|
图1：A graph with a loop having vertices labeled by degree 内含自环按度标记的图]]
图1：A graph with a loop having vertices labeled by degree 内含自环按度标记的图]]
在'''<font color="#ff8000">图论 Graph Theory</font>'''中，图中顶点的'''<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">图论 Graph Theory</font>'''中，图中顶点的'''<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">握手引理<font color="#ff8000">==
{{main|Handshaking lemma}}
{{main|Handshaking lemma}}
此公式表明，在任何无向图中，拥有奇数度值的顶点的个数是偶数。这一阐释（以及度和公式)被称为'''<font color="#ff8000">握手引理 Handshaking Lemma</font>'''。该名称来自一个有趣的数学问题，即求证无论该群体内有多少人，与奇数个人握过手的人数总是偶数。
==度序列==
[[File:Conjugate-dessins.svg|thumb|200px|
[[File:Conjugate-dessins.svg|thumb|200px|
图2：Two non-isomorphic graphs with the same degree sequence (3, 2, 2, 2, 2, 1, 1, 1).
图2：Two non-isomorphic graphs with the same degree sequence (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>'''（两个图中顶点的度值都相同，但形状不同）具有相同的度序列。然而，度序列通常不能唯一地标识一个图，在某些情况下，非同构图也会具有相同的度序列。
无向图的度序列是指将其各顶点度值按非递增方式排序，对于上述图是(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">度序列问题 Degree Sequence Problem</font>'''，是指寻找给定以非增方式排列的正整数的度序列的局部或全部图的问题。(序列尾部的零可能会被忽略，因为通过向图中添加适当数量的孤立顶点就可以轻松实现序列尾部不断加零。)一个序列是某个图的度序列，即一个度序列问题有解时，该序列称为图形序列。由于度和公式的存在，任何具有奇数和的序列，如(3,3,1) ，都不会是图的度序列。反之亦然: 如果一个序列和是偶数，它就是重图的度序列。我们可以轻易地构造一个图: 匹配奇数度值的顶点并成对连接起来，然后剩余的偶数度值顶点都连出一条边指向图形/起点本身。
一般来说，'''<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>'''(Deza et al. ，2018<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>)。
==特殊值==
[[File:Depth-first-tree.png|thumb|
图3：An undirected graph with leaf nodes 4, 5, 6, 7, 10, 11, and 12 一个具有叶节点的无定向图]]
*度数为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>'''
==全局属性==
*如果一个图中的所有顶点的度值都为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的顶点的图。
==Special values==
==参阅==
*'''<font color="#ff8000">有向图的入度和出度 Indegree,Outdegree For Digraph</font>'''
*A directed graph is a [[pseudoforest]] if and only if every vertex has outdegree at most 1. A [[functional graph]] is a special case of a pseudoforest in which every vertex has outdegree exactly 1.
==See also==
*'''<font color="#ff8000">度分布 Degree Distribution</font>'''
*[[Indegree]], [[outdegree]] for [[digraph (mathematics)|digraph]]s
*'''<font color="#ff8000">二分图的度序列 Degree Sequence For Bipartite Graphs </font>'''
'''<font color="#ff8000">二分图的度序列 Degree Sequence For Bipartite Graphs </font>'''
==Notes==
==笔记==
{{reflist}}
{{reflist}}
==References==
==参考==
*{{Citation | last1=Diestel | first1=Reinhard | title=Graph Theory | url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ | publisher=Springer-Verlag | location=Berlin, New York | edition=3rd | isbn=978-3-540-26183-4 | year=2005 }}.
*{{Citation | last1=Diestel | first1=Reinhard | title=Graph Theory | url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ | publisher=Springer-Verlag | location=Berlin, New York | edition=3rd | isbn=978-3-540-26183-4 | year=2005 }}.
[[Category:Graph theory]]
本中文词条由[[用户:Ryan|Ryan]] 参与编译， [[用户:CecileLi|CecileLi]] 审校，[[用户:不是海绵宝宝|不是海绵宝宝]]编辑，欢迎在讨论页面留言。
[[Category:待整理页面]]
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[分类: 图论]]