文档库

最新最全的文档下载
当前位置:文档库 > 图论 复习

图论 复习

一、填空题

1. n 阶无向完全图,n 阶有向完全图的边数分别为 和 。

2.已知无向图G 有12条边,1度顶点有2个,2度、3度、5度顶点各1个,其余顶点度数均为4,则4度顶点的个数为 。

3.通过图中所有边一次并且仅一次行遍所有顶点的回路称为 。

4.设无向图中有6条边,3度与5度顶点各一个,其余的都是2度顶点,则该图的顶点个数为 。

5.在简单无向图G=中,如果V 中的每个结点都与其余的所有结点邻接,则该图称为_______________,如果V 有n 个结点,那么它还是__________度正则图。

6. 一个图为简单图需具备的两个条件是:既没有___________也没有_______________。

7. 设无向图G 有10条边,3度与4度顶点各2个,其余顶点的度数均小于3,则G 中至少有__________个顶点。

8. n 阶k-正则图中,边数m=________。

9. 经过图中所有顶点一次且仅一次的回路称为____________。无向图G 是__________当且仅当G 是连通图,且G 中没有奇度顶点。

10. 在有向图中,关联一对顶点的有向边如果多于1条,并且这些边的_________与_________相同,则称这些边为平行边。既不含平行边也不含环的图称为_________。

11.设非负整数列d=(n d d d ,,,21???),则d 是可图化的当且仅当 。

二、选择题

1.下列四组数据中,不能成为任何4阶无向简单图的度数序列的为( )

A. 1,1,2,2

B. 1,1,1,3

C. 2,2,2,2

D. 1,3,3,3

2.设图无向图G 的关联矩阵为???????

?????????0110110101

110110*********,则G 的顶点数与边数分别为( ).

A. 4, 5

B. 5, 8

C. 4, 10

D. 5,5.

三、简答题

1. 证明任何图中,奇度顶点的个数为偶数。

2.已知无向图G有11条边,2度与3度顶点各2个,其余都是4度顶点,求G 中共有几个顶点。(写出过程)

3.写出下图的关联矩阵。

图论 复习

4.有向图D如下图所示:求(1)长度为 3的通路数有多少条?

(2)长度为小于或等于3的通路数有多少条?

图论 复习

5.下图给出了一个有向图。求出它的邻接矩阵A;(2)求出A2,A3,A4及可达矩阵P。

图论 复习

6.写出下图的关联矩阵。

图论 复习

一、填空题

1.2)1(-n n ,)1(-n n

2.3

3. 欧拉回路

4. 4

5. (无向)完全图 , n-1

6. 环 , 平行边

7. 7 8. m=2nk

9. 哈密顿回路 欧拉图

10. 始点 终点 简单图 11.)2(mod 01=∑=n

i i d

二、选择题

1.D

2.D

三、简答题

1.证:设>=

1)()()(2V v V v V v v d v d v d m

由于∑∈2

)(2V v v d m 和均为偶数,因为1V 中顶点度数为奇数,所以||1V 必为偶数,

即奇度顶点的个数为偶数。

2.解:设度数为4的顶点个数为n 个,则11243222?=?+?+?n , 所以3=n ,故G 的顶点个数为7322=++。 或者设有n 个顶点,则()112443222?=?-+?+?n , 解得7=n 。

3.解:???????? ?

?100110010000000110000011101

00000112 4.解:

有向图的邻接矩阵????????????=0100

100101000021A ????????????=1001

0121100102212A ?????

???????=01211222012122233A 所以长度为3的通路数是24条。 ?????

?

??????=++=122223441222246532A A A B 所以长度小于或等于3 的通路数是44条。

5.解:邻接矩阵A=01

0100

1101

010

100???????????? 20111020101110011A ??????=??????

30212 0122 0212 0201

A

??????=

??????

40323 0413 0323 0122

A

??????=

??????

可达矩阵P=

1111 0111 0111 0111????????????

6.解:

11000 11100 00011 00111 -????-

??????

---??