一、填空题
1. n阶无向完全图，n阶有向完全图的边数分别为 和 。 2．已知无向图G有12条边，1度顶点有2个，2度、3度、5度顶点各1个，其余顶点度数均为4，则4度顶点的个数为 。
3．通过图中所有边一次并且仅一次行遍所有顶点的回路称为 。 4．设无向图中有6条边，3度与5度顶点各一个，其余的都是2度顶点，则该图的顶点个数为 。
5．在简单无向图G=
6. 一个图为简单图需具备的两个条件是：既没有___________也没有_______________。
7. 设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，则G中至少有__________个顶点。 8. n阶k-正则图中，边数m=________。
9. 经过图中所有顶点一次且仅一次的回路称为____________。无向图G是__________当且仅当G是连通图，且G中没有奇度顶点。
10. 在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的_________与_________相同，则称这些边为平行边。既不含平行边也不含环的图称为_________。
11．设非负整数列d=(d1,d2,???,dn)，则d是可图化的当且仅当 。 二、选择题
1．下列四组数据中，不能成为任何4阶无向简单图的度数序列的为（ ） A. 1,1,2,2 B. 1,1,1,3 C. 2,2,2,2 D. 1,3,3,3
?0?12．设图无向图G的关联矩阵为??1??1??11111?0100??，则G的顶点数与边数分别为
1011??0101?0110??( ).
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．n(n?1)2，n(n?1)
2．3
3． 欧拉回路 4． 4
5． (无向)完全图 ， n-1 6． 环 ， 平行边 7． 7 8. m=nk2。
9. 哈密顿回路 欧拉图 10. 始点 终点 简单图 n11．?di?0(mod2)
i?1二、选择题 1．D 2．D
三、简答题
1．证：设G??V,E?为任意一图，令
V1?{v|v?V?d(v)为奇数}，
V2?{v|v?V?d(v)为偶数}，则
由于2m和v?V2?d(v)均为偶数，因为V1V1?V2?V，V1?V2??，由握手定理得
中顶点度数为奇数，所以|V1|必为偶数，即奇度顶点的个数为偶数。
2m??d(v)??d(v)??d(v)
v?Vv?V1v?V22．解：设度数为4的顶点个数为n个，所以长度小于或等于3 的通路数是44则2?2?2?3?n?4?2?11，
所以n?3，故G的顶点个数为2?2?3?7。
或者设有n个顶点，则
2?2?2?3??n?4??4?2?11， 解得n?7。
??2110000??0101110??3．解：??0000110?
??0000001???0011001??4．解：
??1200?有向图的邻接矩阵A??0010???1001?? ?0010????1220? A2??1001???1210?? ?1001????3222? A3??1210???2221?? ?1210??所以长度为3的通路数是24条。
??5642?B?A?A2?A3??2221???4432?? ?2221??条。
??0105．解：邻接矩阵A=?001??010?010??0111?A2??0201???0111?? ?0011????0212?A3??0122???0212?? ?0201????0323?A4??0413???0323?? ?0122????1111?可达矩阵P=?0111???0111?? ?0111?????11000?6．解：?1?1100???00011???00?1?1?1??
1?1?1?? 0??