图论习题 1.4：有向图与 de Bruijn 图

设 $n\geqslant 1$。必要性：竞赛图中每个顶点都满足 $d^-(v)+d^+(v)=n-1$，故入度等于出度时，$n-1$ 必为偶数。

充分性：写成 $n=2r+1$，用 $0,1,\ldots,n-1$ 编号，对每个 $i$ 加入如下所有有向边：

对任意不同顶点 $i,j$，令 $d=(j-i)\bmod n\in\{1,\ldots,2r\}$。若 $1\leqslant d\leqslant r$，就有 $i\to j$；否则 $1\leqslant n-d\leqslant r$，就有 $j\to i$。两种情况互斥且穷尽，故每对不同顶点恰好有一个方向，构成竞赛图。

每个顶点的出邻点为后续 $r$ 个模 $n$ 顶点，入邻点为前面的 $r$ 个模 $n$ 顶点，因此 $d^+(i)=d^-(i)=r$。当 $n=1$ 时偏移集合为空，单顶点无边图也满足条件。

必要性：任取 $u\in S,v\in T$。强连通性给出一条从 $u$ 到 $v$ 的有向路径。沿路径取第一次进入 $T$ 的顶点，其前一个顶点仍在 $S$，两者之间的边即从 $S$ 指向 $T$。

充分性：固定顶点 $u$，令 $S$ 为从 $u$ 可达的所有顶点的集合，包含 $u$ 自身。若 $T=V(G)\setminus S$ 非空，则假设保证存在边 $x\to y$，其中 $x\in S,y\in T$。从 $u$ 到 $x$ 的路径接上这条边，就说明 $y$ 也可达，与 $y\notin S$ 矛盾。

所以从每个 $u$ 都可到达所有顶点，图强连通。只有一个顶点时，以零长路径到达自身，结论同样成立。

因为是有向无环图, 那么一定存在入度为 $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$ 时，只考虑含边的连通部分，其中每个顶点至少有一条入边和一条出边。反复沿出边前进，有限性保证出现重复顶点，从而找到有向环 $C$（也允许自环）。

删去 $C$ 的边，每个顶点的入度与出度仍相等。余图的每个含边的弱连通分量都比原图少边，可分别用归纳假设得到欧拉回路。

每个这样的分量都与 $C$ 有公共顶点：否则，沿原底图中通向 $C$ 的路径，第一条离开该分量的边既不能是余图的边，也不能是两端都在 $C$ 上的边，矛盾。在各公共顶点处将分量的欧拉回路插入 $C$，便得到遍历所有边一次的闭合有向迹。孤立顶点不影响结论。