2

2.1.2

令 $G$ 是一个图. - a 证明: $G$ 是一棵树当且仅当 $G$ 是连通的且每条边都是割边. - b 证明: $G$ 是一棵树当且仅当添加任一条以 $V(G)$ 中的顶点为端点的边恰好生成一个环.

证明

a. "$\Rightarrow$": $G$ 是树 $\Leftrightarrow$ 任意两点之间有且仅有一条路径, 从而删去任意一边 $e=uv$ 都会导致 $u,v$ 从连通变为不连通, 连通分支数量增加, 即 $e$ 是割边.

"$\Leftarrow$": 每条边都是割边意味着每条边都不在环上, 从而整个图无环, 又连通, 所以 $G$ 是树.

b. "$\Rightarrow$": $G$ 是树, 即任意两点之间有且只有一条路径, 对于任意两点 $u,v\in V(G)$, 存在 $u,v$-path, 从而加上 $uv$ 后构成一个环.

"$\Leftarrow$": 对任意两点 $u,v$ 添边都能生成一个环说明存在 $u,v$-path, 故 $G$ 连通, 恰好只生成一个环说明原本的图无环. 不然必然存在 $u,v$-path 上含有环上的边, 这样就存在至少两条不同的 $u,v$-path, 那么添加 $u,v$ 后会形成至少两个环. 所以满足这个条件的图必然连通且无环所以是树.

2.1.12

计算 $K_{m,n}$ 的直径和半径.

答案

$n,m\geqslant 2$.

对于同一部集的点之间距离为 2, 不同部集的点距离为 1.

从而直径是 2, 半径是 2.

$n=m=1$.

直径, 半径均为 1.

2.1.33

令 $G$ 是一个连通的 $n$-顶点图. 证明 $G$ 恰有一个环当且仅当 $G$ 恰有 $n$ 条边.

证明

"$\Rightarrow$": 恰有一个环, 那么删除环上任意一条边, 就得到一个连通且无环的图, 也就是树, 所以总边数为 $n-1+1=n$.

"$\Leftarrow$": 连通且恰有 $n$ 条边. 由连通性, 一定存在一个生成树, 而根据 2.1.2 树添加一条边会生成恰好一个环.

2.1.47

直径与半径 - a 证明: 图的顶点对的距离函数 $d(u,v)$ 满足三角不等式 $d(u,v)+d(v,w)\geqslant d(u,w)$. - b 由 $a$ 证明: diam$G\leqslant 2\text{rad}\ G$ 对任意图成立. - c 对满足条件 $r\leqslant d\leqslant 2r$ 的任意正整数 $r,d$. 构造半径为 $r$ 且直径为 $d$ 的一个简单图.

证明

a. 考虑 $d(u,v),d(v,w)$ 对应的两条路径 $u,v$-path, $v,w$-path, 那么就构成了 $u,w$-walk, 从而 $d(u,w)$ 一定不超过 $u,w$-walk 的长度, 即 $d(u,w)\leqslant d(u,v)+d(v,w)$.

b. 取顶点 $c$ 满足 $\varepsilon(c)=\text{rad}\ G$, 那么对任意两个点 $x,y$ 有 $d(x,y)\leqslant d(x,c)+d(c,y)\leqslant \text{rad}\ G+\text{rad}\ G$ 所以 $\text{diam}G\leqslant 2\text{rad}G$.

c. 先构造一个大小为 $2r$ 的环 $C_{2r}$, 再任选环上的一点 $u$, 从 $u$ 引出一条新的长度为 $d-r$ 的链. 由于 $d-r\leqslant r$, 所以 $u$ 就是离心率最小的点为 $r$, 且显然该图的直径为 $d$, 取新链端点到环上 $u$ 的对称点即为直径.

2.2.1

确定符合下列条件的树: - a Prufer 编码中只含有一个值; - b Prufer 编码中恰有两个值; - c Prufer 编码中的值各不相同;

答案

a. 星型图, 编号任意, Prufer 编码中只有中心节点编号.

b. 将两个星型图的中心用一条边相连即可.

c. 一条链.

2.2.3

令 $G$ 是下图. 用矩阵树定理找出行列式为 $\tau(G)$ 的一个矩阵, 并计算 $\tau(G)$ 的值.

答案

$$L=D-A=\left(\begin{aligned} 5 & -2 & -3 & 0\\ -2 & 5 & -1 & -2\\ -3 & -1 & 8 & -4\\ 0 & -2 & -4 & 6 \end{aligned}\right)$$

$\tau(G)=\det\left(\begin{aligned} 5 & -1 & -2\\ -1 & 8 & -4\\ -2 & -4 & 6 \end{aligned}\right)=106$

2.2.7

用 Cayley 公式证明: 由 $K_n$ 删除一条边后所得的图有 $(n-2)n^{n-3}$ 棵生成树.

证明

由 Cayley 公式, $K_n$ 的生成树一共有 $n^{n-2}$ 种, 考虑计算含有给定边的生成树数量 $v$, 考虑所有生成树的总边数, 我们有 $$ n^{n-2}(n-1)=\binom{n}{2}v $$ 所以 $v=2n^{n-3}$, 从而删除给定边剩余的生成树数量为 $n^{n-2}-2n^{n-3}=(n-2)n^{n-3}$.

2.3.3

在一个网络中, 共有 $5$ 个城市. 在城市 $i$ 和 $j$ 之间直接修一条路的成本是下面矩阵中 $a_{i,j}$ 的值. 无穷大表示在两个城市间有一座山, 因而无法修路. 确定为使所有城市相互连通必需的最小成本. $$\left(\begin{aligned} 0 & 3 & 5 & 11 & 9\\ 3 & 0 & 3 & 9 & 8 \\ 5 & 3 & 0 & \infty & 10\\ 11 & 9 & \infty & 0 & 7\\ 9 & 8 & 10 & 7 & 0 \end{aligned}\right)$$

答案

考虑最小生成树 Kruscal 算法, 选取 $12,23,35,45$ 四条边最小权值和为 $21$.

2.3.5

在一个网络中, 共有 5 个城市. 直接从城市 $i$ 到达城市 $j$ 所需要的时间是下面矩阵中 $a_{i,j}$ 的值. 这个矩阵不是对称的 (用有向图), 且 $a_{i,j} = \infty$ 表示两个城市间没有直接连接的路径. 对每个 $i, j$ 对, 确定从 $i$ 到 $j$ 的最小访问时间以及相应的访问路径.

$$\left(\begin{aligned} 0 & 10 & 20 & \infty & 17 \\ 7 & 0 & 5 & 22 & 33 \\ 14 & 13 & 0 & 15 & 27 \\ 30 & \infty & 17 & 0 & 10 \\ \infty & 15 & 12 & 8 & 0 \\ \end{aligned}\right)$$

答案

$$ \begin{aligned} 1: & 2: & 3: & 4: & 5:\

1\to2\ 10. &2\to3\ 5. & 3\to2\ 13 & 4\to5\ 10 & 5\to4\ 8\

1\to2\to3\ 15. &2\to1\ 7. & 3\to1\ 14 & 4\to 3\ 17 &5\to3\ 12 \

1\to5\ 17. &2\to3\to4\ 20. & 3\to4\ 15 & 4\to 5\to3\ 22 & 5\to 2\ 15\

1\to2\to3\to4\ 30. &2\to1\to5\ 24. & 3\to4\to 5\ 25 &4\to3\to1\ 31 &5\to2\to1\ 22 \end{aligned} $$