树与最小生成树课案.ppt

计算机数学 例题2 下图为一个街道图。邮递员从邮局 a出发沿路投递邮件。问是否存在一条投递路线使邮递员从邮局出发通过所有街道一次再回到邮局？ 例题3 判断下面的4个图哪些可以一笔画？并说明原因。 定理8.2.3 一个连通有向图具有（有向）欧拉回路的充要条件是图中每个结点的入度等于出度。 一个连通有向图具有有向欧拉路的充要条件是最多除两个结点外的每个结点的入度等于出度， 但在这两个结点中， 一个结点的入度比出度大1， 另一个结点的入度比出度少1。 8.4 哈密尔顿图 与欧拉回路类似的是哈密尔顿回路问题。 它是1859年哈密尔顿首先提出的一个关于12面体的数学游戏： 能否在下页图中找到一个回路，使它含有图中所有结点一次且仅一次？ 若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地呢？为此，这个问题也被称作周游世界问题。 对右图 ， 图中粗线给出了这样的回路。 定义 8.4 给定图G， 若有一条路通过G中每个结点恰好一次， 则这样的路称为哈密尔顿路；若有一个圈， 通过G中每个结点恰好一次(起点两次)， 这样的圈称为哈密尔顿回路（或哈密尔顿圈）。 具有哈密尔顿回路的图称为哈密尔顿图。 尽管哈密尔顿回路与欧拉回路问题在形式上极为相似，但是到目前为止还不知道一个图为哈密尔顿图的充要条件，寻找该充要条件仍是图论中尚未解决的主要问题之一。下面先给出一个简单而有用的必要条件。 【例3】某地有５个风景点。若每个景点均有两条道路与其他景点相通，问是否可经过每个景点恰好一次而游完这５处？ 解 将景点作为结点，道路作为边，则得到一个有５个结点的无向图。 由题意，对每个结点vi，有 deg(vi)＝2（i∈Ｎ5）。 内 容 回 顾 例题1 求下图的一条欧拉通路。 类似于无向图的结论， 对有向图有以下结果。 12 面体游戏示图 定理8.4.1 设图G＝〈V ,E〉是哈密尔顿图， 则 对于V的每个非空子集S，均有W（G－S）≤|S| 成立， 其中W（G－S）是图G－S 的连通分支数。 判断哈密尔顿图的充分条件很多， 我们仅介绍一个。 定理8.4.2 设G＝〈V ,E〉是有n个结点的简单图， 1） 如果任一对不相邻结点u， v∈V， 均有 deg(u)＋deg(v)≥ n－1， 则在G中存在一条哈密尔顿路； 2） 如果任一对不相邻结点u， v∈V， 均有 deg(u)＋deg(v)≥ n， 则G是哈密尔顿图。 证明 略。 则对任两点vi， vj（i， j∈Ｎ5）均有 deg(vi)＋deg(vj)＝2＋2＝4＝5－1 可知此图一定有一条哈密尔顿路，本题有解。 一般来说，一个无向连通图G，如果G是树，则它的生 成树是惟一的，就是G本身；如果不是树，那么它的生 成树就不惟一了。如果G不是树，图G与它的生成树的 区别在于G可能包含回路，而生成树不包含回路。 由一个连通图G寻找它的生成树的过程是： 在G中寻找初级回路，找到后删去其中的一条边， 并继续寻找初级回路，找到后再删去其中一条边， 直到G中没有初级回路为止。 练习1： 画出下图所示的简单无向图的3个生成树。