一、填空题
1. n阶无向完全图，n阶有向完全图的边数分别为 和 。
2．已知无向图G有12条边，1度顶点有2个，2度、3度、5度顶点各1个，其余顶点度数均为4，则4度顶点的个数为 。 3．通过图中所有边一次并且仅一次行遍所有顶点的回路称为 。
4．设无向图中有6条边，3度与5度顶点各一个，其余的都是2度顶点，则该图的顶点个数为 。
5．在简单无向图G=<V，E>中，如果V中的每个结点都与其余的所有结点邻接，则该图称为_______________，如果V有n个结点，那么它还是__________度正则图。
6. 一个图为简单图需具备的两个条件是：既没有___________也没有_______________。
7. 设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，则G中至少有__________个顶点。
8. n阶k-正则图中，边数m=________。
9.经过图中所有顶点一次且仅一次的回路称为____________。无向图G是__________当且仅当G是连通图，且G中没有奇度顶点。
10. 在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的_________与_________相同，则称这些边为平行边。既不含平行边也不含环的图称为_________。
11．设非负整数列d=()，则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的关联矩阵为嵌入式pc，则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．3
3．中国典籍与文化 欧拉回路
4． 4
5． (无向)完全图 ， n-1
6． 环 ， 平行边
7． 7北京青年报网站
8. m=。
9. 哈密顿回路 欧拉图
10. 始点 终点 简单图
11．
二、选择题
1．D
2．D
三、简答题
1．证：设为任意一图，令，
，则，，由握手定理得
由于均为偶数，因为中顶点度数为奇数，所以必为偶数，即奇度顶点的个数为偶数。
2．解：设度数为4的顶点个数为个，则，
所以，故G的顶点个数为。
或者设有个顶点，则，
解得。
3．解：
4．解：
有向图的邻接矩阵
所以长度为3的通路数是24条。
所以长度小于或等于3 的通路数是44条。
5．解：邻接矩阵A=
可达矩阵P=
6．解：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议