树与最小生成树.ppt

树与最小生成树
1
内
容
回
顾
2
例题1 求下图的一条欧拉通路。
3
例题2 下图为一个街道图。邮递员从邮局 a出发沿路投递邮件。问是否存在一条投递路线使邮递员从邮局出发通过所有街道一次再回到邮局?
4
例题3 判断下面的4个图哪些可以一笔画?并说明原因。
5
一个连通有向图具有(有向)欧拉回路的充要条件是图中每个结点的入度等于出度。一个连通有向图具有有向欧拉路的充要条件是最多除两个结点外的每个结点的入度等于出度, 但在这两个结点中, 一个结点的入度比出度大1, 另一个结点的入度比出度少1。
类似于无向图的结论, 对有向图有以下结果。
6
哈密尔顿图
与欧拉回路类似的是哈密尔顿回路问题。它是1859年哈密尔顿首先提出的一个关于12面体的数学游戏: 能否在下页图中找到一个回路,使它含有图中所有结点一次且仅一次? 若把每个结点看成一座城市,连接两个结点的边看成是交通线,那么这个问题就变成能否找到一条旅行路线,使得沿着该旅行路线经过每座城市恰好一次,再回到原来的出发地呢?为此,这个问题也被称作周游世界问题。
7
12 面体游戏示图
对右图, 图中粗线给出了这样的回路。
定义 给定图G, 若有一条路通过G中每个结点恰好一次, 则这样的路称为哈密尔顿路;若有一个圈, 通过G中每个结点恰好一次(起点两次), 这样的圈称为哈密尔顿回路(或哈密尔顿圈)。
具有哈密尔顿回路的图称为哈密尔顿图。
8
尽管哈密尔顿回路与欧拉回路问题在形式上极为相似,但是到目前为止还不知道一个图为哈密尔顿图的充要条件,寻找该充要条件仍是图论中尚未解决的主要问题之一。下面先给出一个简单而有用的必要条件。
设图G=〈V ,E〉是哈密尔顿图, 则
对于V的每个非空子集S,均有W(G-S)≤|S| 成立,
其中W(G-S)是图G-S 的连通分支数。
9
10