图论习题 1.2：连通、迹与欧拉图

1.2 #

1.2.1 #

确定下列命题的真假.

a) 任意非连通图都有一个孤立顶点.
b) 一个图是连通的当且仅当它的某个顶点与其他所有顶点是连通的.
c) 任意闭合迹的边集可以划分成若干个环的边集.
d) 如果图中有一个极大迹不是闭合的, 则其端点的度是奇数.

答案

a) 假。两个互不相交的单边图就是反例：顶点集为 $\{1,2,3,4\}$ ，边集为 $\{\{1,2\},\{3,4\}\}$ 。它有两个连通分量，但每个顶点的度都是 $1$ 。

两条互不相交的边：1 与 2 相连，3 与 4 相连；没有孤立顶点。

b) 真。这里按非空图理解题意，“连通”表示存在路径，不要求两点之间有直接的边。

若图连通，任取一个顶点 $v$ ，它都与其他所有顶点连通。反过来，若存在这样的 $v$ ，则对任意两点 $x,y$ ，把 $x$ 到 $v$ 的路径与 $v$ 到 $y$ 的路径接起来，可得 $x$ 到 $y$ 的游走；删去其中重复绕行的部分即可得到路径。因此图连通。

路径图 P4：1、2、3、4 依次相连。任意两点之间都有路径，但没有顶点直接邻接其余三个顶点。

图中的 $P_4$ 是该命题的例子，而不是反例。若把题目中的“连通”改成“邻接”，就变成了另一个命题。单顶点图也满足原命题；零顶点空图是否称为连通图取决于约定，本题不把它包含在讨论范围内。

c) 真。

证明

对闭合迹的长度 $l$ 作强归纳。长度为 $0$ 时边集为空，可分为空族。若除首尾外没有重复顶点，这条闭合迹本身就是一个环；若允许自环，这也包括长度为 $1$ 的情形。

否则，在闭合迹的访问序列 $v_0,v_1,\ldots,v_l=v_0$ 中，可取 $v_i=v_j=w$ ，满足 $0\le i<j\le l$ 且 $0<j-i<l$ 。从第一次出现的 $w$ 到第二次出现的 $w$ ，取出一段非空闭合子迹。

闭合迹按访问顺序展开：u、若干点、w、若干点、w、若干点、v，其中 u 与 v 是同一点。两个 w 之间为子迹 C1，其余两段拼成 C2。

图按访问顺序展开，同一顶点可以画在不同位置； $u=v$ ，两个 $w$ 也表示同一顶点。中段构成闭合迹 $C_1$ ，其余两段在 $w$ 处拼接成闭合迹 $C_2$ 。它们的边集互不相交，合起来恰好是原迹的边集，长度都小于 $l$ 。由归纳假设，分别把二者分解成环，即得到所需划分。

d) 真。

证明

设极大非闭合迹的端点为 $u,v$ ，其中 $u\ne v$ 。迹在中间每次经过某顶点都使用成对的关联边；在端点处则多使用一条。因此，迹所使用的关联边数在 $u,v$ 处都是奇数，自环按两次关联计数。

若某端点在原图中的度为偶数，该点必还有一条未被这条迹使用的关联边。沿这条边延长，仍是一条更长的迹，与极大性矛盾。故两个端点在原图中的度都为奇数。

1.2.3 #

令 $G$ 是顶点集为 $\{1,\ldots,15\}$ 的图, 其中 $i$ 和 $j$ 邻接当且仅当它们的最大公因数大于 1. 计算 $G$ 的分量数, 并求最长路径长度.

答案

$1$ , $11$ , $13$ 三个点是孤立点, 其余节点连通, 所以共有 4 个分支.

最长路径长度为 $11$ , 考虑该路径 $7,14,12,9,6,3,15,5,10,8,4,2$ .

而由于该连通分支大小为 $12$ , 所以已经是最长路径.

1.2.8 #

确定 $m$ 和 $n$ 的值, 使得 $K_{m,n}$ 是欧拉图.

答案

在通常的 $m,n\geqslant 1$ 约定下， $K_{m,n}$ 连通。两部的顶点度数分别为 $n$ 和 $m$ ，因此它是欧拉图当且仅当 $m,n$ 都是偶数。

若另允许某一部为空，图没有边。此时是否把它称为欧拉图取决于对零边闭合迹的约定，不能沿用上述非退化情形的判定。

1.2.17 #

设 $G_n$ 是一个图, 其顶点是 $\{1,\ldots, n\}$ 的所有排列, 两个排列 $a_1,\ldots,a_n$ 和 $b_1,\ldots,b_n$ 是邻接的当且仅当他们是互换了某两个相邻位置上的元素. 证明: $G_n$ 是连通的.

证明

考虑证明任一排列和 $12\cdots n$ 连通.

对任意排列 $a_1,\ldots,a_n$ , 找到第一个 $i$ 满足 $a_i\neq i$ , 由于是排列, 故能找到 $j$ 满足 $a_j=i$ 并由 $i$ 的最小性得到 $j>i$ .

那么我们就存在一条路径 $a_1,\ldots,a_i,\ldots,a_{j-1}, a_j,\ldots,a_n\to a_1,\ldots,a_i,\ldots,a_j,a_{j-1},\ldots,a_n\to\cdots\to a_1,\ldots,a_j,a_i,\ldots,a_{j-2},a_{j-1},\ldots,a_n$ . 即依次将 $a_j$ 往前交换, 交换 $j-i$ 次后新的排列就满足 $a'_i=i$ .

于是反复上述操作, 每次寻找第一个满足 $a_i\neq i$ 的位置并调整该位置相同, 经过不超过 $n-1$ 次调整就可以得到 $12\cdots n$ . 而将每次操作的路径连起来就得到任意排列和 $12\cdots n$ 连通, 从而 $G_n$ 连通.

1.2.38 #

证明: 具有至少 $n$ 条边的 $n$ -顶点图含有至少一个环.

证明

考虑依次加边. 初始的图是 $n$ 个孤立点, 不存在边.

我们以任意顺序依次加入 $n$ 条边. 并记连通分支数量为 $d$ , 初始 $d=n$ .

设当前边的两个端点为 $x,y$ . 如果 $x,y$ 不连通, 那么加入该边会使得 $x,y$ 各自所属的连通分支连通, 即连通分支数量减一.

而如果 $x,y$ 已经连通, 那么存在一条 $x,y$ -path, 从而在加入这条边后变成一条闭合的 $x,y$ -walk, 进而存在一个环.

而对于第一种情况, 当我们加入 $n-1$ 条边的时候如果之前每条边都不构成环, 那么 $x_n,y_n$ 必定连通, 因为之前 $n-1$ 条边使连通分支数量减少 $n-1$ , 故此时只剩下 $n-(n-1)=1$ 个连通分支, 即 $x,y$ 连通. 所以存在环.