Tournament (graph theory)

Presentation on theme: "Tournament (graph theory)"— Presentation transcript:

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

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

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

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

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

6 目录 有向图中的哈密尔顿（回）路 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).

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

8 目录 有向图的定向（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). 强行证明 凉心剧透 参考鸣谢

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

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

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

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

13 目录 … … (任意)竞赛图一定含有有向哈密尔顿通路 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。 凉心剧透 参考鸣谢

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

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

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

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

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

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

20 目录 CONTENTS 主要问题 定义解释 强行证明 凉心剧透 参考鸣谢
图论导引第七章 定义解释 强行证明 凉心剧透 参考鸣谢

21 敬请指导 WELCOME TO GUIDE