第七章特殊图讲课.ppt

第七章 特殊图 引言 7.1 欧拉图 7.2 哈密尔顿图 7.3 二部图 7.4 平面图 7.5 无向树 7.6 根树 7.7 图的应用 引 言 7.1 欧拉图 7.2 哈密尔顿图 7.3 二部图 7.4 平面图 7.5 无向树 7.6 根树 例6 判断下图中的（1）图与（2）图的可平面性。 （1） （2） 解：对图（1），依次删除边e1, e2, e3, e4, e5，端点分别合并为w1, w2, w3, w4, w5，得（1）的一个初等收缩图见下图中的（a）。此图即K5，所以（1）图是个非平面图。 对图（2），因为它含有子图（见下图中的（b）），此图即K3,3，所以（2）图是个非平面图。 （a） （b） 7.5.1 无向树的概念及性质 一、无向树的概念 1.无向树：连通且不含简单回路的无向图。 2.树叶：无向树中的度为1的结点。 3.分支点：无向树中度大于1的结点。 4.树枝：无向树中的边。 5.无向森林：每个连通分支都是无向树的图。 6.平凡树：平凡图是无向树，称为平凡树。 例1 在下图中，（1）是无向树，其中含有4片树叶，7根树枝。（1）同时也是一片森林， 是由一棵树组成的森林。 （2）不是无向树（因为它不是连通图），但是是森林， 是由两棵树组成的森林。（3）不是无向树（因为 其中含有简单回路），也不是森林。 （1） （2） （3） 二、无向树的性质 定理1 对任何一个含有n个结点，m条边的无向图G=V,E，下列命题互相等价。 （1）G是无向树。 （2）G不含简单回路且连通。 （3）G不含简单回路，且n=m+1。 （4）G连通，且n=m+1。 （5）G中不含简单回路，但往G中添加任何一条新边后，将出现一条简单回路。 （6）G连通，但删除G中的任何一条边后，将变成一个非连通图。 （7）G的任何一对结点之间，有且仅有一条简单通路。 定理2 任何一棵非平凡的无向树中至少含有两片树叶。 7.5.2 最小生成树 无向树的直接应用，就是最小生成树。 一、生成树 1. 生成树的概念 定义： （1）若无向图G的生成子图是无向树，则称该无向树为G的一棵生成树。 （2）设T是无向图G的一棵生成树，则G的在T中存在的边称为T的树枝，G的不在T中存在的边称为T的弦。所有弦组成的集合称为T的补。 例如，在下面的图中，（2）是（1）的一棵生成树，e2, e3, e4, e5, e8 是该生成树的树枝，e1, e6, e7是该生成树弦，{e1, e6, e7}是该生成树补。 （1） （2） 2. 生成树的存在性 定理3 对任何一个无向图G，其中含有生成树，当且仅当G是连通图。 证明：先证充分性 设T是无向图G的一棵生成树，则T是一个连通图，因而T中任意两结点之间都有通路。 又由于T是G的生成子图， 其中含有G的所有结点，并且每条边都是G的边，所以，G的任意两结点之间都有通路，即G是个连通图。 再证必要性 设G是连通图。若G中无简单回路，则G本身是无向树；又因为每个图都是自身的生成子图，所以G就是G的生成树。若G中有简单回路，就任意找出一条来，删除这条回路上的任意一条边，此时剩下的图仍是连通的。重复上述操作，直到不再含有简单回路为止，就可以得到G的一棵生成树。 二、最小生成树 1. 带权图 在一个无向图G中，用一个正实数ω表示边e的“长度”，称为边e所带的权。 如果G的每条边都带权，就称G是一个带权图。 在实际中不同的带权图里，权的含义不尽相同。例如，根据一个图描述的系统情况，图中的边的权值可以用来表示公路里程、票价（费用）、运行时间、最大车流量、收