图论-总结课件.ppt

图 论刘 峰2011.5 第二篇 图 论 1.图、图论 由点和线组成的图表称之为图。 系统地研究图的性质就构成了一门学科，被称为图论。 2.与上篇的关系：　 图论虽然是一门单独的学科，但实际上，图论可以看成是集合论的继续．就是在有限的集合上（V）上定义的一个反自反、对称的二元关系（E）。 3. 在图论的解题过程中常常使用两种解题方法： 一是反证法，另一个是数学归纳法。 第6章 第一节 图论发展概述-----了解 第二节　图的基本定义　　 设V是一个非空集合，V的一切二个元素所构成子集记为P2(V)，即P2(V)={A|A?V且|A|=2}； ２.１无向图 定义1 设V是一个非空有限集合，E?P2(V)，二元组(V,E)称为一个无向图。 2.2 顶点的度 定义2 设v为图G=(V，E)的任一顶点，G中与v邻接的边的条数称为顶点v的度，记为degv。 定理1 (握手定理)设G=(V,E)是一个具有p个顶点q条边的图,则G中各顶点度的和等于边的条数q的两倍，即∑degv=2q。 推论1任一图中，度为奇数的顶点的数目必为偶数。 定义3 设G是图，若Δ(G)=δ(G)=r，即G的每个顶点的度都等于r，则G称为r度正则图。 (1) 若Δ(G)=δ(G)=3，则称3-度正则图,也叫做三次图。 (2) 若Δ(G)=δ(G)=0，则称为零图，即0-度正则图。 (3) 若Δ(G)=δ(G)=p-1，则称为p-1度正则图，即 degv=p-1。 (4) p-1度正则图也称为p个顶点的完全图，记为Kp。在Kp中，每个顶点与其余各顶点均邻接。 显然，Kp有p(p-1)/2条边。 2.5 子 图 子图、生成子图、真子图、极大子图、导出的子图 2.6 同 构 第三节 路、回路（圈）、连通图 3.1 通道、迹、路 3.2 连通 定义2 设G=(V,E)是图，若G中任两个不同顶点间至少有一条路联结，则称G是一个连通图。 3.3 几个定理 定理2 设G=(V,E)是一个有p个顶点的图。若对G的任两个不邻接的顶点u和v,有 degu + degv≥p-1， 则G是连通的。[这个定理是一个充分条件] 定理3 设G=(V,E)是至少有一个顶点不是弧立顶点的图。若对任意v∈V，degv为偶数，则G中有回路。 定理4 若图G中的两个不同顶点u与v间有两条不同的路联结，则G中有回路。 第四节 补图、偶图 4.1 补图---什么样的图有补图？ 每个自补图都有4n或 4n+1个顶点。 4.2 偶图（双图、二部图、双色图） 4.3 偶图的特征性质 定理1 图G为偶图的充分必要条件是它的所有回路都是偶数长。 4.4 图兰(Turan)定理 定理2 具有P个顶点的而没有三角形的图中最多有[p2/4]条边。 第五节 欧拉图(Euler) 5.1 欧拉图 定义1 设(G,V)是一个图，则包含图的所有顶点和所有边的闭迹称为欧拉闭迹；存在一条欧拉闭迹的图称为欧拉图。 定理1 图G是欧拉图当且仅当G是连通的且每个顶点的度都是偶数。 (定理1对多重图也成立) 第六节 哈密顿图 6.1 哈密顿图 定义1 设G是一个图，则图G中包含G的所有顶点的生成 圈称为哈密顿圈； 具有哈密顿圈的图称为哈密顿图。 有割点的图一定不是哈密顿图； 有割点的图不一定不是欧拉图（可能是）； 6.2 性质 定理1 (G·A·Dirac)设G是一个有p个顶点的图，p≥3。若δ(G)≥p/2，则G是一个哈密顿图。 定理2 (O.Ore)设G是有p(p≥3)个顶点的图。若对G的任一对不邻接的顶点u和v，均有degu+degv≥p， 则G是一个哈密顿图。 定理3 设G是一个有P个顶点的图，若对G的每一对不邻接的顶点u和v，均有degu+degv≥p-1，则G有哈密顿路。 (书上习题) 第七节 图的邻接矩阵 7.1 邻接矩阵 定义1设G=(V，E)是一个图，矩阵称为G的邻接矩阵，其中 7.2 通道的条数 定理1 设G=(V,E)是一个(p,q)图，p×p矩阵A是G的邻接矩阵，则G中vi与vj间长为l通道的条数等于Al的第i行第j列元素的值，其中i≠j。 第7章 树和割集 第一节 树及其性质 1.1树和森林 定义1 连通且无回路的无向图称为无向树，简称树。 定义2 没有回路的无向图称为无向森林，简称森林。 1.2 树的特征性质 写出无向树等价的几个特征性质（至少5个） 推论1 任一非平凡树中至少有两个度为1的顶点。 推论2任一非平凡树的最长路的两个端点一定是树叶。 推论3 任意非平凡树都是偶图(显然，树中无圈)。 推论4 任意非平凡树都是2-色的。 第二节 生成树 2.1生成树（包含所有顶点的树）