图论习题+答案.pdfVIP

1设图G有12条边，G中有1度结点2个，2度结点2个，4度结点3个，其余结点度数不

超过3．求G中至少有多少个结点？

2设有向简单图G的度数序列为(2,2,3,3）,入度序列为(0,0,2,3),求G得出度序列.

3设D是n阶有向简单完全图,则图D的边数为.

4设G是n阶无向简单完全图K，则图G的边数为.

n

5仅有一个孤立结点组成的图称为()

(A)零图(B)平凡图(C)补图(D)子图

6设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有N个k度顶点，N

kk+1

个k+1度顶点，则Nk=.

7设图G如右图.已知路径

(1)P=(vevevev)

11557223

v1

(2)P=(vevevevevev)

256223348275

e1e5

(3)P=(vevev)

327562

vev

265

(4)P=(vevevevevev)

411223348265

e7e4

判断路径类型，并求其长度.

e2e8

v3v4