Tournament (graph theory) 竞赛图 Tournament (graph theory) 制作人：殷天润

目录 CONTENTS 主要问题 定义解释 ？ 主要问题 强行证明 凉心剧透 参考鸣谢

目录 CONTENTS 主要问题 （任意）竞赛图一定含有有向哈密尔顿通路 定义解释 强行证明 凉心剧透 参考鸣谢

目录 CONTENTS 竞赛图 哈密尔顿路？ 主要问题 ONE TWO 定义解释 强行证明 凉心剧透 主要问题 参考鸣谢 THREE (时间可以洗刷一切） TWO 定义解释 强行证明 凉心剧透 主要问题 参考鸣谢 THREE （任意）竞赛图一定含有有向哈密尔顿通路。

目录 CONTENTS 主要问题 定义解释 定义解释 强行证明 凉心剧透 参考鸣谢

目录 有向图中的哈密尔顿（回）路 CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 PS:A closed walk of length at least 2 in which no vertex is repeated except for the initial and terminal vertices is a (directed) cycle. 定义解释 图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密尔顿回路(cycle). 强行证明 凉心剧透 参考鸣谢 PS:A walk in which no vertex is repeated is a (directed) path. 有向图D的路P(path)包含D的所有顶点时被称为是D的哈密尔顿路(path).

目录 竞赛图 CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 A tournament is an orientation of a complete graph. 参考鸣谢 竞赛图是完全图的一个定向。

目录 有向图的定向（orientation） CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 An oriented graph can also be obtained by assigning a direction to (that is, orienting) each edge of a graph G. The digraph D is then referred to as an orientation of G. 主要问题 定义解释 对无向图D的每一条边规定一个方向可以形成有向图G，此时有向图G被称为无向图D的一个定向(orientation). 强行证明 凉心剧透 参考鸣谢

目录 竞赛图 CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 PS: 竞赛图可以视作是循环赛的图模型 第一轮 第二轮 第三轮 1-2 1-3 1-4 3-4 2-4 2-3

目录 CONTENTS 主要问题 定义解释 强行证明 强行证明 凉心剧透 参考鸣谢

目录 …… (任意)竞赛图一定含有有向哈密尔顿通路 CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 反证法证明： 设n=|V|， 且P={1,2,3,…,k}(k<n)是G中的最长path,标号按拓补排序给出. 对于a∉P,可以显然得到下图：（没有方向的部分表示不确定方向） 主要问题 定义解释 强行证明 a …… 1 2 3 k k-1 凉心剧透 参考鸣谢

目录 …… 喵喵喵？显然？？ CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 a …… 1 2 3 k k-1 主要问题 定义解释 强行证明 如果a与1之间的边是(a,1),那么把P添到1之前就可以构成一条更长的路P1…k，与之前的假设矛盾 同理a与k之间的边是(k,a)的时候也不行 凉心剧透 参考鸣谢

目录 … … (任意)竞赛图一定含有有向哈密尔顿通路 CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 a … 1 2 3 k k-1 i-1 i 主要问题 定义解释 … 强行证明 考虑a与顶点2,3……k-1之间的边,设从左往右数,第一条一a为起点的边,终点为i（2≤i≤𝑘−1）,考虑到这种范围的i可能不存在，因此根据前面的证明不妨设2≤i≤𝑘 （因为有边(a,k）,这时必然存在i。此时可以构造新的路径P’：123…i-1ai…k，比原先的路径P长度大1，与P为最长路径的假设矛盾！ 因此必然存在哈密尔顿path。 凉心剧透 参考鸣谢

目录 CONTENTS 主要问题 定义解释 凉心剧透 强行证明 凉心剧透 参考鸣谢

目录 竞赛图构造哈密尔顿回路（相当于数学归纳法证明） CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 假设你已经找到了一条长度为k的哈密尔顿路径P：V1…VK,然后要往路径中加入第k+1个点。 主要问题 定义解释 这个点与P可能出现三种情形：(证明当然已经证过了） 存在边(k,v1); 存在边(vk,k); 存在边(vi,k),(k,vi-1) 强行证明 凉心剧透 参考鸣谢

目录 …… 情形1 CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 k+1 1 2 3 k k-1

目录 …… 情形2 CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 k+1 1 2 3 k k-1

目录 … 情形3 CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 K+1 1 2 3 k k-1 i-1 i

目录 CONTENTS 主要问题 定义解释 参考鸣谢 强行证明 凉心剧透 参考鸣谢

目录 CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢 https://en.wikipedia.org/wiki/Tournament_(graph_theory) https://blog.csdn.net/di4CoveRy/article/details/70230029 https://blog.csdn.net/unsolvedmys/article/details/73608770 https://www.cnblogs.com/Ash-ly/p/5452580.html 图论导引第七章 定义解释 强行证明 凉心剧透 参考鸣谢

敬请指导 WELCOME TO GUIDE