图论与组合 / 习题/考试 / 作业 / 2

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$ 后会形成至少两个环. 所以满足这个条件的图必然连通且无环所以是树.

$n,m\geqslant 2$.

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

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

$n=m=1$.

直径, 半径均为 1.

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

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

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$ 的对称点即为直径.

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

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

c. 一条链.

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

由 Cayley 公式, $K_n$ 的生成树一共有 $n^{n-2}$ 种, 考虑计算含有给定边的生成树数量 $v$, 考虑所有生成树的总边数, 我们有

所以 $v=2n^{n-3}$, 从而删除给定边剩余的生成树数量为 $n^{n-2}-2n^{n-3}=(n-2)n^{n-3}$.

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