《离散数学》图训练
单选题
1. 任何图中必定有偶数个
$\text{A.}$ 入度为偶数的结点
$\text{B.}$ 度数为奇数的结点
$\text{C.}$ 出度为奇数的结点
$\text{D.}$ 度数为偶数的结点
一个无向图有四个结点, 其中 3 个的度数是 $2,3,3$, 则第 4 个结点的度数不可能是 $\qquad$ .
$\text{A.}$ 0
$\text{B.}$ 1
$\text{C.}$ 2
$\text{D.}$ 4
对于下列序列, 可构成简单无向图的度数序列为 ( ) 。
$\text{A.}$ $3,3,4,4,5$
$\text{B.}$ $0,1,3,3,4$
$\text{C.}$ 1, 1, 2, 2, 3
$\text{D.}$ $1,1,2,2,2$
下列关于图连通性的描述中不正确的是
$\text{A.}$ 强连通图必然是单向连通的;
$\text{B.}$ 单向连通图也必然是强连通的;
$\text{C.}$ 弱连通图未必是单向连通的;
$\text{D.}$ 单向连通图必然是弱连通的.
设 $D=\langle V, E\rangle$ 为有向图， $V=\{a, b, c, d, e, f\}$,
$E=\{\langle a, b\rangle,\langle b, c\rangle,\langle a, d\rangle,\langle d, e\rangle,\langle f, e\rangle\}$ 是
$\text{A.}$ 强连通图
$\text{B.}$ 单向连通图
$\text{C.}$ 弱连通图
$\text{D.}$ 不连通图
已知无向图 $G$ 的邻接矩阵为 $\left[\begin{array}{lllll}0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0\end{array}\right]$,有（）.
$\text{A.}$ 5 点, 8 边
$\text{B.}$ 6 点, 7 边
$\text{C.}$ 5 点, 7 边
$\text{D.}$ 6 点, 8 边
填空题
设无向图 $G$ 的度数列是 $(1,2,3,4,2)$, 则图的边数是
有向图 $D$ 的度数列为 $(3,4,4,3)$, 出度列为 $(2,3,1,1)$, 则此图的入度列为
解答题
设图 $D$ 如图所示,
（1）求 $D$ 的邻接矩阵 $A$;
（2）求 $A^2$ ，并说明从 $v_1$ 到 $v_3$的长为 2 的通路有多少条？
（3） $D$ 中长为 2 的通路一共有多少条？
