离散数学期末复习试题及答案
第 五 章 图论 1．画出下面两图的补图?
2．下面两图是否同构？为什么？?
e
d
4 b c
同构 1 a, 2 b , 3 c , 4 d , 5 e (2 ,1) (d,a) (5,2) (e,b) (4 ,1) (d,a) (3,2) (c,b) (1 ,3) (a,c) (3,4) (c,d) (1 ,5) (a,e) (5,4) (e,d)
3．一个图如果同构于它的补图，则该图称为自补图? ｉ）给出有4个顶点的自补图。? ｉｉ）给出有5个顶点的自补图。?
ｉｉｉ）证明一个自补图或者有4k个顶点，或者有4k+1个顶点。?