526
个编辑
更改
→Degree sequence
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 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.
'''<font color="#ff8000">度序列问题 Degree Sequence Problem</font>'''，是指寻找具有以非增方式排列给定正整数的度序列的局部或全部图的问题。(序列尾部的零可能会被忽略，因为通过向图中添加适当数量的孤立顶点就可以轻松实现序列尾部不断加零。)一个序列是某个图的度序列，即一个度序列问题有解时，该序列称为图形序列。由于度和公式的存在，任何具有奇数和的序列，如(3,3,1) ，都不会是图的度序列。反之亦然: 如果一个序列和是偶数，它就是重图的度序列。构造这样一个图是很简单: 匹配奇数度值的顶点并成对连接起来，然后剩余的偶数度值顶点都连出一条边指向自己。
'''<font color="#ff8000">度序列问题 Degree Sequence Problem</font>'''，是指寻找给定以非增方式排列的正整数的度序列的局部或全部图的问题。(序列尾部的零可能会被忽略，因为通过向图中添加适当数量的孤立顶点就可以轻松实现序列尾部不断加零。)一个序列是某个图的度序列，即一个度序列问题有解时，该序列称为图形序列。由于度和公式的存在，任何具有奇数和的序列，如(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]].