图论与组合：作业 / 1.4

"$\Rightarrow$": 对于竞赛图, 有 $d^-(v)+d^+(v)=n-1$, 又 $d^-(v)=d^+(v)$, 所以 $n$ 是奇数.

"$\Leftarrow$": 用 $0,\ldots,n-1$ 表示节点编号, 以如下方式定向

如此, 每个点出边指向比其大的一半点, 入边由比其小的一半点指来.

"$\Rightarrow$": 根据强连通性质, 任取 $u\in S,v\in T$, 存在一条 $u,v$-path. 可以找到路径中属于 $S$ 的最后一个点, 和属于 $T$ 的第一个点, 从而这两个点之间的边就是一条从 $S$ 到 $T$ 的边.

"$\Leftarrow$": 对任意两个点 $u,v\in V(G)$, 考虑初始划分 $S=\{u\}, T=V(G)-\{u\}$, 存在一条 $S$ 到 $T$ 的边.

• (1) 这条边的另一个端点不是 $v$, 记作 $u_1$, 那么将 $u_1$ 加入 $S$ 中, 并从 $T$ 删去.
• (2) 这条边的另一个端点是 $v$, 那么我们就找到了一条 $u,v$-walk, 从而有 $u,v$-path, 即 $u$ 可达 $v$.

我们只需反复进行 (1) 操作直到 (2) 成立, 并且 (2) 一定会成立, 因为每次 (1) 都会使得 $T$ 中顶点数量减一, 至多 $n-2$ 次操作就会得到 $v$.

因为是有向无环图, 那么一定存在入度为 $0$ 的点, 否则所有点入度都不为零一定存在环.

那么我们就将这个入度为 $0$ 的点加入最终序列里, 并删除这个点及其出边.

注意到, 删除这样的点和边后, 剩余的图仍是有向无环图, 所以可以重复上述操作直到所有点被取出.

下证上述操作得到的序列满足条件.

对于边 $v_iv_j\in E(G)$, 考虑这条边什么时候被删除, 当且仅当删除点 $v_i$ 的时候删除这条边, 而将点 $v_i$ 加入序列后 $v_j$ 仍在图中, 所以 $v_i$ 的位置一定在 $v_j$ 前面, 故满足 $i<j$.

"$\Rightarrow$": 如果是欧拉图, 那么存在一个闭合的迹遍历边集. 所以显然底图除了孤立点是连通的. 又点 $v$ 在迹中每次出线都会有一条入边, 一条出边即入度和出度分别加 1, 故总数上有 $d^-(v)=d^+(v)$.

"$\Leftarrow$": 考虑数学归纳法, 对边数 $l$ 归纳.

$l=0$ 时, 显然成立.

设 $l\leqslant k$ 时成立.

当 $l=k+1$ 时, 考虑底图非平凡的连通分支, 由 $d^+(v)=d^-(v)$, 可推出 $d^+(v)\geqslant 1$, 从而根据引理可以找到一个环. 如果这个环就是欧拉回路那么成立, 否则将这个环上的边删去, 剩下的图的每个连通分支根据归纳假设存在欧拉回路, 再用这个环将若干欧拉回路有向拼接就可得到整体的欧拉回路.