5.图论(III)

尝试用英语记。后面有自己翻译一遍的，顺带复习（

Euler tour

An Euler tour is a walk that traverses every edge exactly once and starts and finishes at the same vertex.

Theorem

A connected graph has an Euler tour iff(if and only if) every vertex has even degree.

[!Proof] Only if: Assume connected graph has an Euler tour..Each time the tour visits a vertex , it enters via one edge and leaves via another, contributing 2 to its degree. So the degree of any vertex is even.

if: For ，assume deg() is even for all : Let : be the longest walk that traverses no edge more than once. It is common to consider the shortest or longest path. We want to show: ①: All edges incident to are used in : if is not in , could be a longer path, contradictory. ②: , otherwise has odd degree in , according to ①, has odd degree in as well. This is a contradiction. So the original proposition holds. Suppose is not an Euler tour, is connected, so edge is not in but incident to some vertex in . Let be the edge. Then we start from , walking through .This is a longer path than . This gives contradiction. So is an Euler tour.

Directed Graph(digraphs)

Every edge has a direction. , then called tail, called head. indegree : the number of incoming edges outdegree : the number of outgoing edges

Theorem

Let be an -node graph with . Let denote the adjacency matrix for . That is Let denotes the number of walks of length k from to . Then .

[!Proof] denote the entry in . Let be the statement that correctly counts the walks of length .

Base case: ,Edge :, this is true by definition. The case for non-adjacent vertices follows similarly. : .

Inductive step: Assume Def : A digraph is strongly connected if for all , directed path from to in .

Def : A directed graph is called a directed acyclic graph(DAG) if it does not contain any directed cycles

Tournament graph

A vertex denotes a team. Between , either win or win. So there’s only one directed edge between them.

Def : A directed Hamiltonian path is directed walk that visits every vertex exactly once.

Theorem

Every tournament graph contains a directed Hamiltonian path.

[!Proof] By induction on .

Base case: , holds obviously.

Inductive step: Assume ). Take out one node . This gives a tournament graph. By , is a directed Hamiltonian path. : , obviously right. :, let be the smallest number such that , then , so . Thus, the proposition holds.

A king chicken

Def : Let vertex denote a chicken, if pecks then or . If a chicken pecks everyone else, then it is a king chicken.

Theorem

A chicken with highest outdegree is a king.

[!Proof] By contradiction. Let have highest outdegree. Suppose is not a king. , and cannot be true. So if then . Thus,,that’s a contradiction. So is a king.

---

复习 & 手动翻译：

欧拉巡回

欧拉巡回是指遍历每条边恰好一次，并且起点终点相同的途径。

定理

一个连通图有欧拉巡回当且仅当每个顶点的度为偶数。

[!证明] 当： 假设连通图 有一条欧拉巡回 , 因为每条边只遍历一次， 出现在巡回中的次数 。因而每个顶点的度数都是偶数。

仅当： 假设连通图 的每个顶点度数都是偶数： 设 : 是 中最长的，遍历所有边至多一次的途径。图论中常常考虑最长、最短路径。 那么： ①：每条连着 的边都在 中，否则加上那条边显然会构造出一条更长的路径。 ②： ，否则 的度数在 中为奇数，又因为①，所以其在 中也是奇数，从而矛盾。 这时，假设 不是欧拉巡回，因为 是连通图，存在一条边不在 里但连到了 中的某个顶点（否则就可以分成两个无关图），假设这条边是 ，那么从 开始走到 再走一圈 显然更长，矛盾。从而 就是一个欧拉巡回。

有向图

每条边都有一个方向。如果 那么称 是尾， 是头。 入度是指指向顶点的边的数量，出度类似。

定理

设 是一个 个节点的图，。让矩阵 代表其邻接矩阵，则 设 表示长度为 的途径从 到 . 那么 .

[!证明] 表示 处的元素 . 即命题

初始状况: ,如果有 :, 这根据定义就是对的，没有边也类似 : .

归纳步骤：假设 定义 ： 一个有向图 是强连通的，如果任意两个点之间都存在一条有向路径。 定义 ： 有向无环图是没有环的有向图（

竞赛图

顶点代表参赛选手/队伍。每对选手只有一个赢，我们用有向箭头表示。即每对顶点之间都有一条有向箭头。

定义 ： 有向哈密顿路径是指一条恰好经过每个顶点一次的有向路径。

定理

每个竞赛图都有有向哈密顿路径。

[!证明] 利用对 的归纳法。 即命题。

初始情况： ，显然成立。

归纳步骤：假设 成立。 拿出一个顶点 ，这仍然是一个竞赛图，利用归纳假设，可知有 这样一条有向哈密顿路径。 ① 指向 ，显然成立。 ② 否则，设 是最小的编号，使得 指向 ，那么 ， ，插进去就好了。 综上原命题成立。

鸡王

定义 ： 如果一个顶点代表一只🐔， 如果可以啄 那么就是说有 ，或者 。如果一只鸡可以啄所有其他鸡，那他就是鸡王。

定理

出度最高的鸡是鸡王。

[!证明] 用反证法。 设 是出度最高的鸡，假设他不是鸡王。 那么存在 ， 而且不存在 ，那么如果 就有 ，这样就说明 的出度至少比 多 ，这就矛盾了，所以 就是鸡王。