s*******y
发帖数: 558 | 1 Let G=(V, E) be a simple undirected graph with degree sequence d_1 >=
d_2 >= ... >= d_n, where n >= 1.
Let d_1+a_1, d_2+a_2, ..., d_n+a_n be another graphic sequence (which
is realizable). Here
0 <= a_i <= n-1-d_i , i=1, ..., n.
问题是： 如果对图G进行修改， 要求只加边不减边， 加的边是原图没有的。
有没有可能构造出一个新的简单图， 使得其degree sequence是 d_1+a_1, ..., d_n+a
_n.
当什么情况下是可能的， 什么情况下是不可能的？
谢谢 |
|
