(完整版)图论及其应用1-3章习题答案(电子科大)

v G
G1的度序列为： (d1+1,d2+1,…,dn+1, n) 由条件：不存在小于(n+1)/2的正整数m,使得dm+1≦m,且 d(n+1)-m <(n+1)-m。于是由度序列判定定理知：G1是H图，得 G有H路。
G1Leabharlann 613.证明：若G不是H图，则G度弱于某个 Cm1 ,n ， 且有
v m1 2
3
32. （1）证明：考虑G=Cn˅H 的最小点割V。根据联图的定义， 则必有V包含Cn 或者H，否则G-V后一定连通。如果Cn ∈V，则 由H是K连通的可知|V|=n+k。若H ∈V，则V中至少还需要包含Cn 中两个不相邻的顶点，也可得|V|=n+k。故G是n+k连通的。 （2）在Cn 上任取相邻的两点x,y，设这两个点在Cn上的两条路分 别为P1和P2。考虑宽为n+k的x-y容器，因为H仅包含n+k-2个点， 经过H中的点，且独立的（x，y）路最多有n+k-2个，且每条路的 长度都为2。因此在每个容器中必包含P1和P2。故dn+k(x,y)=n-1。
1. 证明方法与p. 47 定理3类似
3. 设无环图G是阶数大于2的连通图，则下列命题等价 （1）G是块，即G是2-连通的； （2）G的任意两个顶点在某个圈上； （3）G的任一个顶点和任一条边在某个圈上； （4）G的任意两边在某个圈上； （5）G的任意两个顶点u，v及任一边e，总存在连接u，v 且过e的路； （6）G的任意三个顶点，总存在连接其中任意两个顶点， 并且通过第三个顶点的路 （7）G的任意三个顶点，总存在连接其中任意两个顶点， 并且不过第三个顶点的路 证明：1 2 2：p.48 定理4 3：令u是任一顶点，vw是任一边，由（2），存在

习题一1. 一个工厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。

若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。

若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。

2. 若存在孤立点，则m 不超过K n-1的边数, 故 m <= (n-1)(n-2)/2, 与题设矛盾。

3.4. 用向量(a 1,a 2,a 3)表示三个量杯中水的量, 其中a i 为第i 杯中水的量, i = 1,2,3.以满足a 1+a 2+a 3 = 8 (a 1,a 2,a 3为非负整数)的所有向量作为各结点, 如果(a 1,a 2,a 3)中某杯的水倒满另一杯得到 ( a ’1, a ’2, a ’3 ) , 则由结点到结点画一条有向边。

这样可得一个有向图。

本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以下即是这样的一条：5. 可以。

7. 同构。

同构的双射如下：8. 记e 1= (v 1,v 2), e 2= ( v 1,v 4), e 3= (v 3,v 1), e 4= (v 2,v 5), e 5= (v 6,v 3), e 6= (v 6,v 4), e 7= (v 5,v 3), e 8= (v 3,v 4), e 9 = (v 6,v 1), 则邻接矩阵为： 关联矩阵为：∑∑∑∑∑∑∑==+====-=++=-==---=--=ni i n i i n i n i n i ni i i n i i n i i i i a a n n a a a n n n a n a v v 1111121212/)1()1(2)1(])1[(。

，　所以 因为 ，＋ 的负度数，则为结点的正度数，为结点记－－－－－22 222 i i C a a ⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡---------100110000001001000010100010011010100000001001100000111, 001101000100000000001001010000001010⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡( 8, 0, 0 ) ( 5, 3, 0 ) ( 5, 0, 3 ) ( 2, 3, 3 ) ( 2, 5, 1 )(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 4, 0 )( 4, 1, 3 )边列表为：A= (1,1,3,2,6,6,5,3,6), B= (2,4,1,5,3,4,3,4,1). 正向表为：A= (1,3,4,6,6,7,10), B= (2,4,5,1,4,3,3,4,1).习题二1. 用数学归纳法。

-28-
图论及其应用第一章
1.2 图的同构
由前已知，同一个图有不同形状的图示。反过来， 两个不同的图也可以有形状相同的图示。比如：
u2
u3
可见 G1 和 G2 的顶点及边之间都一一对应，且连
接关系完全相同，只是顶点和边的名称不同而已。这
样的两个图称为是同构的(isomorphic)。
-29-
图论及其应用第一章
v1
(i=1,2,3,4,5,6)下是同构的。
x1
y1
v6
y3
x2
v2
x3
y2
v4
v3
-31-v5
图论及其应用第一章 画出所有的阶数不大于4，大小为3的所有非同构 简单图：
-32-
图论及其应用第一章 画出阶数为5大小为3的所有非同构简单图
G1
G2
G3
G4
-33-
图论及其应用第一章
无标号的图 注：判断两个图是否同构目前没有好算法。
图论起源于18世纪的一个游戏----俄罗斯的哥尼斯堡七桥问 题。
（1736年 瑞士数学家欧拉——图论之父）
-2-
图论及其应用第一章
七桥问题
C
A
D
B
包含两个要素：对象（陆 地）及对象间的二元关系 （是否有桥连接）
转化
Euler 1736年
C
A
D
B 图论中讨论的图
问题：是否能从A，B，C，D 转化 中的任一个开始走，通过每 座桥恰好一次再回到起点？
从数学上看，同构的两个图，其顶点间可建立一 一对应，边之间也能建立一一对应，且若一图的两点 间有边，则在另一图中对应的两点间有对应的边。严 格的数学定义如下。
定义: 两个图G = (V (G), E(G)) 与H = (V (H), E(H)) ， 如果存在两个一一映射：

第四次作业
四(13).设M是二分图G的最大匹配，则 | M || X | max| S | | N ( S )| ，
SX
证明： | X | max| S | | N ( S )| min(| X | | S |) | N ( S )| ，而（X - S ) N ( S )是G的一个覆盖，则 min(| X | | S |) | N ( S )|是G的最小覆盖，
第七次作业
• 五(28).设sn是满足下列条件的最小整数，把 {1,2,...,sn}任划分成n个子集后，总有一个子集 中含有x+y=z的根，求s1,s2,s3是多少？ • 解：n=1,枚举得s1=2; • s2=5 • s3=14
第七次作业
五(34).求证r(k, l) = r(l, k) 证明：若G含有K k 子图，则G c 含有k个顶点的独立集；若G含有 l个顶点的独立集，则G c 含有K l 子图。则命题成立。
五 (13).若 是单图 G 顶的最小次数，证明； 若 1则存在 1边着色， 使与每顶关联的边种有 1种颜色。 反证法：假设在 v1处无 i 0色 设 C (E 1 , E 2 ,..., E 1 )为 G 的( 1) 最佳边着色 第一步：构造点列： v1 , v 2 ,..., v h , v h 1 ,....., vl ,.... v1处无 i 0色， v j v j 1着 i j色，且在 v j点处 i j 色重复出现，可知在 v j1处仅一 个 i j色；证明如下： 用反证法证明，假设在 v j1处 i j色重复出现，将 v j v j 1改成 v j 所关联的边 没有的颜色 im，则可以对图 G 的找色进行改善。与 C 是最佳边着色矛盾， 假设不成立。 又 是单图 G 顶的最小次数，则必存 在最小整数 h使得 i h i l 第二步：着色调整： v j v j 1着 i j-1色 ( j 1,2,..., h )，所得新着色为 C ' 在 C '中， v1处多了个 i 0色， v h 1处少了个 i h 色，其他点的边着色数 不变， 所以 C ' 还是 1最佳边着色