[音乐] 嗨，欢迎回来，接下来呢我们
来谈论两个由于这个路径和回路
这个概念所定义的两种特殊的图，一种呢 叫做欧拉图，一种呢叫做哈密尔顿图。
那么首先呢我们来看欧拉图。
当然欧拉呢，就是创立图论的那个欧拉，所以这个图呢以他的名字来命名。
那么欧拉图是什么呢？就是说如果一个图G
上有一条能够通过所有顶点和所有的边的 一个闭路径的话，那么我们知道这个所谓的闭路径
就是这个路径它是不允许边重复的，但是呢它可以允许顶点重复，
那么也就是要经过所有的顶点以及所有的边，
那么如果存在这么一条闭路径的话，我们就把这种图称之为欧拉图。
当然如果说没有这个闭路径，那么路径也好
那么如果有一条经过所有顶点和所有的边的路径
也就是说不需要回到原地的话，那么这种叫做欧拉路径，
当然也还是那个要求，就是既然是路径，那么边就不允许重复， 那么但是呢也允许这个顶点重复。
那么对于欧拉图呢， 或者欧拉路径这个问题它已经得到了非常圆满的解决，
那么欧拉图呢它有存在一个判定的条件，或者叫做充分必要条件，也就是等价条件吧，
这个条件呢非常的简单，对于无向图来说 只要求这个无向图G是连通的，
它是一个连通的无向图，并且呢所有顶点的度都是偶数， 那么这样呢就能够构成一个欧拉图。
对于一个有向图而言，那么就只需要这个G是弱连通的，
而且呢每一个顶点的出度和入度都相等，这样呢就可以称之为
一个欧拉图，那么相应的欧拉路径因为它不需要返回到自身，
自身这个顶点，那么所以呢对于无向图来讲，欧拉路径呢 的充分必要条件也就是等价条件呢就是这个图本身是连通的，
并且呢刚好有两个顶点的度是奇数， 也就是说只有两个顶点的度是奇数，其它所有顶点
的度就必须是偶数了，那么当然要构造出这个
路径来，那很显然也是从这两个奇数度的顶点
其中的一个出发能够到达另外一个，然后再也回不来了。
那么对于有向图来说呢就要求这个G是连通的，
而且呢恰好有两个顶点它的出度和入度是不相等，
那么其它的顶点的出度入度都必须相等，就是 如果你出度为3，那么入度也必须为3，这样，
那么对于欧拉路径来说，那么它就有，恰好有两个出度 和入度是不相等，那么其中一个，出度比入度要多1，
也就是从这个顶点出发，然后另外一个呢，是入度比出度多1，
那么终结于这个入度比出度多1的 这个顶点，那么这样呢也可以构造出一个欧拉路径来。
那么欧拉图和欧拉路径呢，就是欧拉在 解决了一笔画问题里边提出来的，
那么我们从这个图的例子，也可以看出来，这个一笔画 问题，那么当然首先，这个欧拉是解决了
这个柯尼斯堡七桥问题，那么我们再来看看柯尼斯堡七桥问题它所
抽象出来的这么一个图，也就是最右边的这个有四个顶点
以及七条边，每条边呢都代表一座桥，
那么从这呢，很显然可以看出来，每个顶点，它的，有三个顶点它的度呢是为3，
还有一个呢度为5，它所有的顶点度都是奇数， 所以呢很显然不可能构造成一个欧拉图，甚至
也不可能构造成一个欧拉路径，所以呢它就没有办法
出现一个可以经过所有的顶点和所有的边，而且呢不允许边重复，
不允许边重复呢，就是说这些桥，每座桥只能走一次， 是吧，这样的，那么我们就很容易判断出来，七桥问题，
它是不可能解决的，就不存在这样的一个欧拉图或者欧拉路径。
而我们下方的这两个，第一个我们很熟悉，就是奥运的五环，
如果我们把这个每一个圈的这个交叉点都看作是一个结点，其他的那个圆弧都是边的话，
那么我们可以看出来它有1，2，3，4，5，6，7，8，有8个顶点，
然后呢，8个顶点之间呢，连接了所有的这个圆弧的边， 那么我们很容易知道，这个边呢，
每一个顶点都是一个4度的顶点，全部都是偶数， 那所以呢，这个五环的这个圈呢，它是一个
欧拉图，对吧？也就是说我可以从这个图的任何一个顶点出发， 做这个一笔画，然后呢回到这个顶点，
所以，当然就是你实际去画的话，你需要照顾到一些技巧，有一些技巧，
那么右下角这个，是一个三角形中间加了一条，那么 如果我们把它看作是一个四个顶点的，每个交叉的地方都是一个
顶点的话，那么它就是一个四个顶点以及五条边的一个图，
那么这个图呢有两个顶点，它的度是2，然后呢恰好有 两个顶点，它的图，它的度呢是3，那么
正好符合欧拉路径的这个定义，所以呢它可以从 其中的一个三度顶点出发，做这个一笔画，回到
另一个三度的顶点，这就是欧拉图和欧拉路径。
那么第二个特殊图，就是哈密顿图，
以及哈密顿通路，哈密顿图的这个提出，它 实际上是由这个数学家哈密顿所发明的一个游戏，
来构造出来，抽象出来的，他做的这个游戏呢 是做了一个木头的球，木质的球，是一个正十二面体，
正十二面体的每一个面都是一个正五边形， 那么它有，相应地有这些顶点，它一共有10，
5个，10个，20个顶点，它有20个顶点，
那么他这个游戏呢就叫做"周游世界"的游戏，他把每一个顶点呢都标上世界上当时一个大城-
市的名称， 那么他的意思就是说能不能只经过这些所有的大城市，
仅一次，那么可以周游世界，就经过这些所有的边，
所以呢，哈密顿图它的定义是这样的， 一个图G有一条经过所有顶点的回路，
那么既然回路，就是不允许这个顶点重复，但是呢它不要求经过所有的边，
那么如果有这样的一个回路的话，就称之为哈密顿回路。
当然我们在对这个哈密顿的这个游戏进行抽象的时候，把它抽象成图的时候，
就要把这个三维立体的这个正十二面体，把它拍扁，
然后投射到这个平面上，就变成了左边这个 有外面是一个五边形，然后中间是一个十边形，然后里边又有一个
五边形，然后它们之间有连接的，这么一个图出来， 那么它是一个有
二十个顶点的图，那么最终呢，它实际上可以证明出来，
它是一个哈密顿图。
那么 哈密顿通路，也就是说它不要求这个闭合，也就是说不要求是一个回路，
也就是只要这个图上有一条经过所有顶点仅仅一次的这个通路的话，
那么这种就叫做哈密顿通路，当然我们不要看这个哈密顿图好像
经过这个顶点仅一次，
然后它看起来好像跟这个欧拉图挺相像的，欧拉图是经过所有的顶点和所有的边，
边不重复，顶点可以任意重复， 那么一笔画问题，这看起来好像也是某种程度的一笔画问题。
但是呢，我们说，哈密顿图可比这个欧拉图的这个难度，可要难得多了。
欧拉图 的这个充分必要条件多简单啊，只要每个顶点的度是偶数，那它就必然是一个欧拉图。
但是呢，哈密顿图却是一个非常难的难题。
那么我们这介绍一个它的充分条件， 这是一个，只是一个充分条件，它不是必要条件，也就是说满足这个条件的图，
是哈密顿图，但是呢并不是所有的哈密顿图都是这样的。
这个判定定理是这样的，如果说一个图它有n个顶点，
只要任意每一对顶点，它的度数之和不小于n减1，
那么G呢，就存在一条哈密顿通路， 如果G的每一对顶点的度数之和不小于n，
并且呢，这个n大于等于3的话，那么它就存在一个回路，也就是说它是一个哈密顿图。
那么这个哈密顿图，这个问题， 非常的难，难到什么样的程度呢？在上个世纪七十年代
的时候它被证明是一个NP完全问题， NP问题呢是在计算理论里头
一个专有的名词，它是说 为了要解决这个问题我们所发明出来的算法，
它不会有这种随着这个问题的规模增长，而是
这个需要解这个问题的时间的复杂度，或者是说占据空间，它是多项式增长，
所谓的多项式就是n的平方啊，n的立方，我们这里的n是定义为这个图上有多少个
顶点，多少个顶点，那么随着顶点数的增加，
那么现有的这个算法，它都是整个的时间的规模，是随着这个n的增加
它是呈n的指数增加的，那么也就是说如果要解决任意
图去判断有没有这个哈密顿通路，或者说哈密顿回路这个问题，
最好的算法，它的算法的时间也是随着这个顶点个数的增长呈指数增长，
也就是说一般来说，这个问题是不能够得到很好的解决的， 那么到指数增长是一个什么样的概念呢？
我们说，实际上对于一些顶点不到100的这种网络，这种图，100我们想象就是很少的
或者说比较小的一个网络，那么要为了要判断它有没有哈密顿通路，
利用现在最好的算法和最好的计算机， 它也需要一个比较荒唐的时间，比如说它需要几百年
的时间才能够确定，是否存在一条这样的路径。
那么实际上呢，正是因为这一类的，很多，图论上有很多这样的难题，像哈密顿
图这样的难题，正式因为这样的难题的存在，虽然我们可能
觉得人类的智慧受到了挑战，但是我们实际上呢，我们在信息安全领域，
在数据加密领域，很多这种领域呢， 它能够，之所以能够正常的运转，也正是托这些
NP问题，就是这些最难的难题所赐的。
陈斌副教授
