六图论.ppt

树的有些性质可用来作为树的定义，我们列出下面三条： （1）每两个结点间由唯一的真路相连接的图是树； （2）m=n–1的连通图是树； (3）m=n–1且无环的图是树。 三、生成树与最小生成树 1．生成树 定义6-14 若连通图G的生成子图T是一棵树，则称T为G的生成树。 例4 下图中（b）和（c）都是（a）的生成树。 2．构造连通图G=（V，E）的生成树的方法 （a）破环法 例5 用破环法，构造上页图（a）的生成树的过程如下： （b）避环法 例6 用避环法构造（a）的生成树过程如下： 3．最小生成树 定义6-15 每条边都以实数赋权的图称为带权图。 例8 下图是一连通带权图。 当G是一带权图时，常将其表示为有序三元组G=（V，E，f），这里f是一由边集E到实数集R的函数 f：E?R. 定义6-16 设G=（V，E，f）是一连通带权图，T是G的一棵生成树，T的边集用E（T）表示，T的各边权值之和W（T）= 称为T的权。G的所有生成树中权最小的生成树称为G的最小生成树。 例9 它们的权W（T1）=24，W（T2）=30。 4．构造连通带权图G=（V，E，f）的最小生成树的方法 例10 以例8中图为例， （1） 破环法 G=G1 G2 G3 G4 G5 G6=T0 W(T0)=18 （2） 避环法 G=G1 G1 G2 G3 G4 G5 = T0 练习6-4 1．设树T有7条边，问T有多少个结点？（ ） 2．设G是一个树林，由3个分图组成，若G有15个结点，问G有多少条边？（ ） 3．互不同构的2结点树有（ ）棵？ 互不同构的4结点树有（ ）棵？ 8 12 1 2 24 4．求下图给出的带权图的最小生成树的权（ ） 6.5 二部图 一、二部图 　　定义6-17 　 若一个图G的结点集V能划为两个子集V1和V2，使得G的每一条边{vi，vj}满足vi?V1，vj?V2，则称G是一个二部图，V1和V2称为G的互补结点子集。此时可将G记作G=（V1，V2，E）。 若V1中任一结点与V2中每一结点均有边相连接，则称二部图为完全二部图。若#V1=r，#V2=t，则记完全二部图G为Kr, t。 例 V4 　　例1 　 下图中的图是否是二部图？ (a) (b) (c) 　　二部图不一定是连通图。 　　定理6-13 　图G为二部图的充要条件是G的所有回路均为偶数长。 　　二、匹配 　 定义6-18 　 设G是具有互补结点子集V1和V2的二部图，其中V1={v1，v2，…，vr}，V1对V2的匹配是G的一个子图，它由r条边{v1，v?1}，{v2，v?2}，…，{vr，v?r}组成，其中，v ?1，v ?2，…，v ?r是V2中r个不同的元素。 　　例2 　下图所给出的二部图是否存在V1对V2的匹配？是否存在V2对V1的匹配？ 　　例3 　 某班级成立了三个运动队：篮球队、排球队和足球队。今有张、王、李、赵、陈5名同学，若已知张、王为篮球队员；张、李、赵为排球队员；李、赵、陈为足球队员，问能否从这5人中选出3名不兼职的队长？ 在图中存在V1对V2的匹配，因此题目的要求可以满足。 解　　构造二部图G=（V1，V2，E）， V1 V2 N 练习6-5 1．在括号中键入“Y”或“N”回答相应的问题。 （1）图(a)是否为二部图？（ ） 若是，找出它的互补结点子集： V1={ } 　　V2={ } (a) (b) （2）图(b)是否为二部图？（ ） Y v1，v3，v5，v6 v2，v4，v7 6.6 平面图 一、平面图的定义 定义6-19 一个图