图论课件1.ppt

第七章 图 论 重点 1、掌握图的基本概念，路与回路的确定与证明； 2、掌握欧拉图、哈密尔顿图和平面图的概念、判断方法以及相关证明； 3、掌握树、森林与生成树的概念与证明； 4、掌握最小生成树的构造方法。 7.1 图的基本概念 二、结点的度数 定理 定义3： 含有平行边的图称为多重图（考虑方向） 不含平行边和环的图称为简单图 定义4：简单图G=V，E中，若每一对结点间都有边相连，则称该图为完全图。 三、补图 四、子图 五、图的同构 例题分析 六、 路径和回路 定理 七、连通图 练习7-1 7.2 图的矩阵表示 二、图的可达性矩阵 练习7-2 7.3 几种特殊图 欧拉图的判断 二、哈密尔顿图 练习7-3 三、平面图 1、平面图的判别方法1 2、平面图的判别方法2 （欧拉公式） 3、平面图的判别方法3 （库拉托斯基定理） 练习7-5 7.4 树 二、树的性质 三、生成树与最小生成树 2．最小生成树 例题分析 练习7-7 四、有向树 练习7-8 定义3 一个图G若能画在平面上，它的边除在端点处外互不交叉，则称G为平面图。画出的没有边交叉的图解称为G的一个平面嵌入。 例1 图(a)是平面图，(b)是该图的一个平面嵌入。 （1）观察的方法 例1 判别下图中的两图是否平面图。 定义4 设G是一个连通平面图，G的边将G所在的平面划分成若干个区域，每一个区域称为G的一个面。其中面积无限的区域称为无限面。 面积有限的区域称为有限面。 包围每个面的所有边构成的回路称为面的边界。 例3 定理6 设G是n≥3的连通平面简单图(n，m） 则 m≤3n–6 证明 因G是简单图必无环，当n=3时, m=2，上式成立。 当m2时，每个面至少由三条边围成，因此各面边界的边数之和Σ≥3K。 另一方面，各面次数和等于边数的二倍即：Σ=2m。 于是得到不等式 2m ≥3K ， 即 K≤2m/3。 根据欧拉公式， 因此 m≤3n–6 定理5 设G是一连通平面图，有n个结点，m条边，K个面，则 n–m+K=2。此定理中的公式称为欧拉公式。 ② 图K3, 3中n=6，m=9，3n–6=12。此 m≤3n–6。满足（*）式，故无法判定K3,3是非平面图。但K3,3不是平面图。 例4利用定理6判别图下图中的K5和K3,3是否非平面图。 解 ① 图K5中n=5，m=10，3n–6=9。 显然m ≤ 3n–6不成立。因此k5不是平面图。 定义5 如果两个图G1和G2是同构的，或者通过反复插入或删除度为2的结点，它们能变成同构的图，则称G1和G2在度为2的结点内同构。 定理7 （库拉托斯基定理） 一个图是平面图的充要条件是它不包含在度为2的结点内与K5同构的子图，也不包含在度为2的结点内与K3,3同构的子图。 解法一 （1）去掉图G中边 {a，c}，{a，d}，{d，e}，{b，e}， 例5 利用定理7判别图G是否非平面图。 图G 2．用库拉托斯基定理判别下图是否平面图。 ( ) N 1．用简单、直观判别法判断下图所给出的两个图是否平面图。 ( ) ( ) Y Y 一、树的定义 定义1:不包含回路的连通图称为树，不包含回路的图称为森林.次数为1的结点为树叶，次数大于1的结点分枝点。 例1 定理1 若T是一棵n，m树，则m=n–1。 证明 （对结点数n进行归纳） 当n=1和n=2时，定理成立。 设对结点数n的所有树定理成立。T是一具有n个结点的树，由于T不包含环，因此从T中去掉任何一条边都将使T变成两个分图，且这两个分图也是树，设它们分别是n1，m1树和n2，m2树，由归纳假设m1=n1–1，m2=n2–1。又∵ n=n1+n2，m=m1+m2+1 ∴ m=(n1–1)+(n2–1)+1=n–1。 定理结论成立。 定理2 具有两个或更多结点的树至少有两片树叶。 证明 设T是一棵n，m树，n≥2，显然T中所有结点的度之和S=2m，由定理1，S==2(n-1)=2n–2。 若T中无树叶结点，则由T连通，每一结点的度≥2，因此S≥2n，这与S=2n–2矛盾。