526
个编辑
更改
跳到导航
跳到搜索
第56行：
第56行： − + − +
→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.
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.