图论-总结.pptVIP

第五节 有向树与有序树 5.1有向树 定义1 一个没有弱回路的弱连通的有向图称为有向树,记做T。 5.2有根树 定义2 设T是一个有向树，若T中恰有一个顶点的入度为0，而其余每个顶点的入度均为1，则称D为有根树。 定理1 有向图T=(V,A)是一个有根树当且仅当T有一个顶点v0可以达到其他任一顶点且T中没有弱回路。 5.3父亲、儿子、祖先、子孙、子树 5.4 有序树 定义6 设T=(V,A)是一个有根树,若T的每个顶点的各儿子排定了次序，则称T为一个有序树。 定义7 设T是一个有序树，则 (1) 若T的每个顶点的出度≤m，则称T为m元有序树。 (2) 若T的每个顶点的出度不是0就是m,则称T为正则m元有序树。 (3) 若存在一个正整数k,使得深度小于k的顶点的出度都是m,而深度等于k的顶点都是叶子，则称T是完全m元有序树。 当m=2时， 就是二元有序树。 定理3 一个高为h的二元树至多有2h+1-1个顶点。 定理4 高为k的二元树至多有2k个叶子。 例1设T=(V,A)是一个有根树,其每个顶点的出度不是0就是2。若T有n个叶子，试求的弧的条数。 例2 设T=(V,A)是一个正则树,若T有n0个叶子，试求的弧的条数。 例3 若二元树T有n0个叶子，n2个出度为2的顶点，证明：n0=n2+1。 例4 设T是正则二元树，T有n0个叶子，n2个出度为2的顶点，证明：n0=n2+1。 第七节 比赛图 7.2 定义 定义1 设D=(V,A)是一个有向图，若任两个不同的顶点之间有且仅有一条有向弧，则称D为比赛图。 问题 p个顶点的比赛图(顶点已命名)有多少个？(2p(p-1)/2) 7.2 性质 定理1 每个比赛图必有一条有向哈密顿路。 （用数学归纳法证明） 图 论刘 峰2011.5 第二篇 图 论 1.图、图论 由点和线组成的图表称之为图。 系统地研究图的性质就构成了一门学科，被称为图论。 2.与上篇的关系：　 图论虽然是一门单独的学科，但实际上，图论可以看成是集合论的继续．就是在有限的集合上（V）上定义的一个反自反、对称的二元关系（E）。 3. 在图论的解题过程中常常使用两种解题方法： 一是反证法，另一个是数学归纳法。 第一节 图论发展概述-----了解 第二节　图的基本定义　　 设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中有回路。 例1 若G是一个恰有两个奇度顶点u和v的无向图，则 G连通?G+uv连通。 例2 设G是一个(p,q)无向图,若q(p-1)(p-2)/2，则G是连通的。 例3 设G是一个(p,q)无向图,若δ(G)≥[p]/2,则G是连通的。 例4 证明：若G不连通，则GC是连通图。 例5 设G是有个p顶点，q条边的无向图，各顶点的度数均为3。则 (1)若q=3p-6,证明:G在同构意义下唯一，并求p,q。 (2)若p=6，证明:G在同构的意义下不唯一。 第四节 补图、偶图