1,592
个编辑
更改
Moved page from wikipedia:en:Degree (graph theory) (history)
此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。
[[File:UndirectedDegrees (Loop).svg|thumb|A graph with a loop having vertices labeled by degree]]
A graph with a loop having vertices labeled by degree
有顶点按度标记的圈的图
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.
在图论中，一个图的顶点的度(或价)是关联到该顶点的边的数量，在多重图中，循环被计数两次。顶点的度数表示“ math”或“ math”。图 < math > g </math > 的最大度，用 < math > Delta (g) </math > 表示; 图的最小度，用 < math > Delta (g) </math > 表示，是其顶点的最大度和最小度。在右多重图中，最大度为5，最小度为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>.
在正则图中，每个顶点都具有相同的度，因此我们可以称之为图的度。一个完全图(表示“ math” > k _ n </math > ，其中 < math > n </math > 是图中顶点的数目)是一种特殊的正则图，其中所有顶点都有最大度，< math > n-1 </math > 。
==Handshaking lemma==
{{main|Handshaking lemma}}
The '''degree sum formula''' states that, given a graph <math>G=(V, E)</math>,
The degree sum formula states that, given a graph <math>G=(V, E)</math>,
度和公式表明，给定一个图 < math > g = (v，e) </math > ,
:<math>\sum_{v \in V} \deg(v) = 2|E|\, .</math>
<math>\sum_{v \in V} \deg(v) = 2|E|\, .</math>
<math>\sum_{v \in V} \deg(v) = 2|E|\, .</math>
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.
该公式表明，在任何无向图中，奇次顶点的个数是偶数。这个语句(以及度和公式)被称为握手引理。后一个名字来自一个流行的数学问题，证明在任何人群中，与奇数人握过手的人数是偶数。
==Degree sequence==
[[File:Conjugate-dessins.svg|thumb|200px|Two non-isomorphic graphs with the same degree sequence (3, 2, 2, 2, 2, 1, 1, 1).]]
Two non-isomorphic graphs with the same degree sequence (3, 2, 2, 2, 2, 1, 1, 1).
具有相同度数列(3,2,2,2,2,2,1,1)的两个不同构图。
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.
无向图的度序列是其顶点度的非递增序列，对于上述图是(5,3,3,2,2,1,0)。度序列是图的不变量，因此同构图具有相同的度序列。然而，度序列通常不能唯一地标识一个图，在某些情况下，不同构图具有相同的度序列。
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.
度序列问题是寻找度序列为给定的正整数非增序列的部分或全部图的问题。(拖尾的零可能被忽略，因为它们通过向图中添加适当数量的孤立顶点来实现。)一个序列是某个图的度序列，即。度序列问题有解决方案的，称为图形序列或图形序列。由于度和公式的结果，任何具有奇数和的序列，如(3,3,1) ，都不能实现为图的度序列。反之亦然: 如果一个序列有偶数和，它就是重图的度序列。这样一个图的构造很简单: 通过匹配将奇数度数的顶点成对连接起来，然后通过自循环填充剩余的偶数度数。
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.
一个给定的度序列是否可以用一个简单的图来实现的问题更具有挑战性。这个问题也称为图实现问题，既可以用 erd s-Gallai 定理解决，也可以用 Havel-Hakimi 算法解决。
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.
寻找或估计具有给定度序列的图的个数问题是图计数领域中的一个问题。
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 ).
一般来说，超图的度序列是其顶点度的非递增序列。一个序列是 < math > k </math >-graphic，如果它是一些 < math > k </math >-uniform 超图的度序列。特别是 < math > 2 </math >-graphic 序列是图形。决定一个给定的序列是否是 < math > k </math >-graphic 可以在多项式时间内通过 erd s-Gallai 定理实现 < math > k = 2 </math > ，但是对于所有 < math > k ge 3 </math > 是 np 完全的(Deza et al. ，2018)。
==Special values==
[[File:Depth-first-tree.png|thumb|An undirected graph with leaf nodes 4, 5, 6, 7, 10, 11, and 12]]
An undirected graph with leaf nodes 4, 5, 6, 7, 10, 11, and 12
具有叶节点4、5、6、7、10、11和12的无向图
*A vertex with degree 0 is called an [[isolated vertex]].
*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.
* A vertex with degree ''n'' − 1 in a graph on ''n'' vertices is called a [[dominating vertex]].
==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]].
*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.
*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.
*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.
*A [[Degeneracy (graph theory)|''k''-degenerate graph]] is a graph in which each subgraph has a vertex of degree at most ''k''.
==See also==
*[[Indegree]], [[outdegree]] for [[digraph (mathematics)|digraph]]s
*[[Degree distribution]]
*[[bipartite graph|degree sequence]] for bipartite graphs
==Notes==
{{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|first1=P.|last1=Erdős|author1-link=Paul Erdős|first2=T.|last2=Gallai|author2-link=Tibor Gallai|title=Gráfok előírt fokszámú pontokkal|language=Hungarian|journal=Matematikai Lapok|volume=11|year=1960|pages=264–274|url=http://www.renyi.hu/~p_erdos/1961-05.pdf}}.
*{{citation
| last= Havel
| last= Havel
| last = Havel
| first= Václav
| first= Václav
| first= Václav
| authorlink =V. J. Havel
| authorlink =V. J. Havel
| authorlink = v.J · 哈维尔
| year = 1955
| year = 1955
1955年
| title = A remark on the existence of finite graphs
| title = A remark on the existence of finite graphs
| title = 关于有限图存在性的一个注记
| language = Czech
| language = Czech
| language = Czech
| journal = Časopis pro pěstování matematiky
| journal = Časopis pro pěstování matematiky
| journal = Časopis pro pěstování matematiky
| volume = 80
| volume = 80
80
| pages = 477–480
| pages = 477–480
| 页数 = 477-480
| url = http://eudml.org/doc/19050
| url = http://eudml.org/doc/19050
Http://eudml.org/doc/19050
}}
}}
}}
*{{citation
| last = Hakimi | first = S. L. | authorlink = S. L. Hakimi
| last = Hakimi | first = S. L. | authorlink = S. L. Hakimi
最后 = Hakimi | first = S.l. | authorlink = S.l. Hakimi
| journal = Journal of the [[Society for Industrial and Applied Mathematics]]
| journal = Journal of the Society for Industrial and Applied Mathematics
工业与应用数学学会杂志
| mr = 0148049
| mr = 0148049
0148049先生
| pages = 496–506
| pages = 496–506
| 页数 = 496-506
| title = On realizability of a set of integers as degrees of the vertices of a linear graph. I
| title = On realizability of a set of integers as degrees of the vertices of a linear graph. I
| title = 一组整数作为线性图顶点度的可实现性。一
| volume = 10
| volume = 10
10
| year = 1962}}.
| year = 1962}}.
1962}}.
*{{citation
| last1 = Sierksma | first1 = Gerard
| last1 = Sierksma | first1 = Gerard
1 = 杰拉德
| last2 = Hoogeveen | first2 = Han
| last2 = Hoogeveen | first2 = Han
| last2 = Hoogeveen | first2 = Han
| doi = 10.1002/jgt.3190150209
| doi = 10.1002/jgt.3190150209
10.1002/jgt. 3190150209
| issue = 2
| issue = 2
2
| journal = [[Journal of Graph Theory]]
| journal = Journal of Graph Theory
| Journal = Journal of Graph Theory
| mr = 1106533
| mr = 1106533
1106533先生
| pages = 223–231
| pages = 223–231
| pages = 223-231
| title = Seven criteria for integer sequences being graphic
| title = Seven criteria for integer sequences being graphic
| title = 整数序列为图形的七个条件
| volume = 15
| volume = 15
15
| year = 1991}}.
| year = 1991}}.
1991}}.
[[Category:Graph theory]]
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>
[[Category:待整理页面]]
[[File:UndirectedDegrees (Loop).svg|thumb|A graph with a loop having vertices labeled by degree]]
A graph with a loop having vertices labeled by degree
有顶点按度标记的圈的图
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.
在图论中，一个图的顶点的度(或价)是关联到该顶点的边的数量，在多重图中，循环被计数两次。顶点的度数表示“ math”或“ math”。图 < math > g </math > 的最大度，用 < math > Delta (g) </math > 表示; 图的最小度，用 < math > Delta (g) </math > 表示，是其顶点的最大度和最小度。在右多重图中，最大度为5，最小度为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>.
在正则图中，每个顶点都具有相同的度，因此我们可以称之为图的度。一个完全图(表示“ math” > k _ n </math > ，其中 < math > n </math > 是图中顶点的数目)是一种特殊的正则图，其中所有顶点都有最大度，< math > n-1 </math > 。
==Handshaking lemma==
{{main|Handshaking lemma}}
The '''degree sum formula''' states that, given a graph <math>G=(V, E)</math>,
The degree sum formula states that, given a graph <math>G=(V, E)</math>,
度和公式表明，给定一个图 < math > g = (v，e) </math > ,
:<math>\sum_{v \in V} \deg(v) = 2|E|\, .</math>
<math>\sum_{v \in V} \deg(v) = 2|E|\, .</math>
<math>\sum_{v \in V} \deg(v) = 2|E|\, .</math>
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.
该公式表明，在任何无向图中，奇次顶点的个数是偶数。这个语句(以及度和公式)被称为握手引理。后一个名字来自一个流行的数学问题，证明在任何人群中，与奇数人握过手的人数是偶数。
==Degree sequence==
[[File:Conjugate-dessins.svg|thumb|200px|Two non-isomorphic graphs with the same degree sequence (3, 2, 2, 2, 2, 1, 1, 1).]]
Two non-isomorphic graphs with the same degree sequence (3, 2, 2, 2, 2, 1, 1, 1).
具有相同度数列(3,2,2,2,2,2,1,1)的两个不同构图。
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.
无向图的度序列是其顶点度的非递增序列，对于上述图是(5,3,3,2,2,1,0)。度序列是图的不变量，因此同构图具有相同的度序列。然而，度序列通常不能唯一地标识一个图，在某些情况下，不同构图具有相同的度序列。
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.
度序列问题是寻找度序列为给定的正整数非增序列的部分或全部图的问题。(拖尾的零可能被忽略，因为它们通过向图中添加适当数量的孤立顶点来实现。)一个序列是某个图的度序列，即。度序列问题有解决方案的，称为图形序列或图形序列。由于度和公式的结果，任何具有奇数和的序列，如(3,3,1) ，都不能实现为图的度序列。反之亦然: 如果一个序列有偶数和，它就是重图的度序列。这样一个图的构造很简单: 通过匹配将奇数度数的顶点成对连接起来，然后通过自循环填充剩余的偶数度数。
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.
一个给定的度序列是否可以用一个简单的图来实现的问题更具有挑战性。这个问题也称为图实现问题，既可以用 erd s-Gallai 定理解决，也可以用 Havel-Hakimi 算法解决。
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.
寻找或估计具有给定度序列的图的个数问题是图计数领域中的一个问题。
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 ).
一般来说，超图的度序列是其顶点度的非递增序列。一个序列是 < math > k </math >-graphic，如果它是一些 < math > k </math >-uniform 超图的度序列。特别是 < math > 2 </math >-graphic 序列是图形。决定一个给定的序列是否是 < math > k </math >-graphic 可以在多项式时间内通过 erd s-Gallai 定理实现 < math > k = 2 </math > ，但是对于所有 < math > k ge 3 </math > 是 np 完全的(Deza et al. ，2018)。
==Special values==
[[File:Depth-first-tree.png|thumb|An undirected graph with leaf nodes 4, 5, 6, 7, 10, 11, and 12]]
An undirected graph with leaf nodes 4, 5, 6, 7, 10, 11, and 12
具有叶节点4、5、6、7、10、11和12的无向图
*A vertex with degree 0 is called an [[isolated vertex]].
*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.
* A vertex with degree ''n'' − 1 in a graph on ''n'' vertices is called a [[dominating vertex]].
==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]].
*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.
*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.
*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.
*A [[Degeneracy (graph theory)|''k''-degenerate graph]] is a graph in which each subgraph has a vertex of degree at most ''k''.
==See also==
*[[Indegree]], [[outdegree]] for [[digraph (mathematics)|digraph]]s
*[[Degree distribution]]
*[[bipartite graph|degree sequence]] for bipartite graphs
==Notes==
{{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|first1=P.|last1=Erdős|author1-link=Paul Erdős|first2=T.|last2=Gallai|author2-link=Tibor Gallai|title=Gráfok előírt fokszámú pontokkal|language=Hungarian|journal=Matematikai Lapok|volume=11|year=1960|pages=264–274|url=http://www.renyi.hu/~p_erdos/1961-05.pdf}}.
*{{citation
| last= Havel
| last= Havel
| last = Havel
| first= Václav
| first= Václav
| first= Václav
| authorlink =V. J. Havel
| authorlink =V. J. Havel
| authorlink = v.J · 哈维尔
| year = 1955
| year = 1955
1955年
| title = A remark on the existence of finite graphs
| title = A remark on the existence of finite graphs
| title = 关于有限图存在性的一个注记
| language = Czech
| language = Czech
| language = Czech
| journal = Časopis pro pěstování matematiky
| journal = Časopis pro pěstování matematiky
| journal = Časopis pro pěstování matematiky
| volume = 80
| volume = 80
80
| pages = 477–480
| pages = 477–480
| 页数 = 477-480
| url = http://eudml.org/doc/19050
| url = http://eudml.org/doc/19050
Http://eudml.org/doc/19050
}}
}}
}}
*{{citation
| last = Hakimi | first = S. L. | authorlink = S. L. Hakimi
| last = Hakimi | first = S. L. | authorlink = S. L. Hakimi
最后 = Hakimi | first = S.l. | authorlink = S.l. Hakimi
| journal = Journal of the [[Society for Industrial and Applied Mathematics]]
| journal = Journal of the Society for Industrial and Applied Mathematics
工业与应用数学学会杂志
| mr = 0148049
| mr = 0148049
0148049先生
| pages = 496–506
| pages = 496–506
| 页数 = 496-506
| title = On realizability of a set of integers as degrees of the vertices of a linear graph. I
| title = On realizability of a set of integers as degrees of the vertices of a linear graph. I
| title = 一组整数作为线性图顶点度的可实现性。一
| volume = 10
| volume = 10
10
| year = 1962}}.
| year = 1962}}.
1962}}.
*{{citation
| last1 = Sierksma | first1 = Gerard
| last1 = Sierksma | first1 = Gerard
1 = 杰拉德
| last2 = Hoogeveen | first2 = Han
| last2 = Hoogeveen | first2 = Han
| last2 = Hoogeveen | first2 = Han
| doi = 10.1002/jgt.3190150209
| doi = 10.1002/jgt.3190150209
10.1002/jgt. 3190150209
| issue = 2
| issue = 2
2
| journal = [[Journal of Graph Theory]]
| journal = Journal of Graph Theory
| Journal = Journal of Graph Theory
| mr = 1106533
| mr = 1106533
1106533先生
| pages = 223–231
| pages = 223–231
| pages = 223-231
| title = Seven criteria for integer sequences being graphic
| title = Seven criteria for integer sequences being graphic
| title = 整数序列为图形的七个条件
| volume = 15
| volume = 15
15
| year = 1991}}.
| year = 1991}}.
1991}}.
[[Category:Graph theory]]
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>
[[Category:待整理页面]]