第56行: |
第56行: |
| 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. | | 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)。度序列是'''<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>'''(两个图中顶点的度值都相同,但形状不同)具有相同的度序列。然而,度序列通常不能唯一地标识一个图,在某些情况下,非同构图也会具有相同的度序列。 |
| | | |
− | --[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]]) 【审校】“无向图的度序列是指将其各顶点度值按非递增方式排序”一句中的“非递增”改为“递减/并不是按递增方式排序的” | + | --[[用户: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 (graph theory)|matching]], and fill out the remaining even degree counts by self-loops. |