34.图论复习讲解.ppt

第七章 图论复习;7.1 图的基本概念;7.1.3 图的分类 (1)按G的结点个数和边数分为(n,m)图, 特殊图, (n,0)称为零图, (1,0) 图称为平凡图 。 (2) 按G中关联于同一对结点的边数分为多重图和简单图; (3)按G的边有方向、无方向分为有向图、无向图和混合图; (4)按G的边旁有无数量特征分为边权图 、无权图; (5)按G的任意两个结点间是否有边分为完全图Kn 7.1.4 补图 定义7.1.2 设G＝〈V, E〉是一个具有n个结点的简单图。以V为结点集，以从完全图Kn中删去G的所有边后得到的图（或由G中所有结点和所有能使G成为完全图的添加边组成的图）称为G的补图，记为 。 ;7.1.5 图的结点度数 无向图的度数和有向图的出度与入度的计算 7.1.6 子图和图的同构 1.子图 定义7.1.5 设有图G=V , E和图 G′= V′, E′ 。 1) 若V′?V， E′ ? E， 则称G′是G的子图。 2) 若G′是G的子图，且E′≠E，则称G′是G的真子图。 3) 若V′=V， E′? E，则称G′是G的生成子图。 2. 图的同构 定义7.1.6 设有图 G=〈V , E〉和图G′= 〈 V′, E′〉。 如果存在双射ｇ：V→V′，使得 e=(u, v) ∈E iff e′=(ｇ(u),ｇ(v))∈E′， 且 (u， v)与(ｇ(u),ｇ(v))有相同的重数，则称G与G′ 同构。记作G≌G′。 ;7.2.1 路与回路 定义 7.2.1 给定图G＝〈V ,E〉, 设v0, v1, … , vk∈V，e1，e2，…，ek∈E， 其中ei是关联于结点vi-1和vi的边， 称交替序列v0e1v1e2…ekvk为连接v0到vk的路， v0和vk分别称为路的起点与终点。路中边的数目k称作路的长度。 定义 7.2.2 设μ=v0e1v1e2…ekvk是图G中连接v0到vk的路。 1)若e1， e2， …， ek都不相同， 则称路μ为迹； 2)若v0， v1， …， vk都不相同，则称路μ为通路； 3)长度大于２的闭的通路（即除v0＝vk外， 其余结点均不相同的路）μ称作圈。 ;定义 7.2.3 在图G中， 若结点vi到vj有路连接（这时称vi和vj是连通的）， 其中长度最短的路的长度称为vi到vj 的距离， 用符号d(vi,vj)表示。若从vi到vj不存在路径,则d(vi,vj)=∞。 7.2.2 图的连通性 1. 无向图的连通性 定义 7.2.4 在无向图如果一个图的任何两个结点之间都有一条路，那么我们称这个图???连通的，否则是不连通的。 定义 7.2.5 图G的一个连通的子图G′（称为 连通子图）若不包含在G的任何更大的连通子图中， 它就被称作G的连通分支。 我们把图G的连通分支数记作W（G）。 2. 有向图的连通性 定义7.2.6 在有向图中,若从结点u到v有一条路，则称u可达v。 定义7.2.7 设有有向图G的单向连通、强连通、弱连通。 ;7.3 图的矩阵表示 7.3.1 邻接矩阵 7.3.2 可达性矩阵 ;7.4 欧拉图与哈密尔顿图 定义 7.4.1 给定无孤立结点的图G， 若存在一条经过G中每边一次且仅一次的回路， 则该回路为欧拉回路。 具有欧拉回路的图称为欧拉图。 定理 7.4.1 连通图G是欧拉图的充要条件是G的所有结点的度数都是偶数。 定义7.4.2 通过图G的每条边一次且仅一次的路称为图G的欧拉路。 定理7.4.2 连通图G具有一条连接结点vi和vj的欧拉路当且仅当vi和vj是G中仅有的两个奇数度结点。 ;7.6 树与生成树 7.6.1 无向树 定义7.6.1 一个连通无圈无向图称为无向树(简称为树)。记作T。树中度数为1的结点称为树叶（或终端结点）， 度数大于１的结点称为分枝点（或内点，或非终端结点）。一个无圈图称为森林。 7.6.2无向图中的生成树与最小生成树 定义7.6.2 若无向(连通图)G的生成子图是一棵树，则称该树是G的生成树，记为TG。生成树TG中的边称为树枝。图G中其它边称为TG的弦。 所有这些弦的集合称为TG的补。 ?定义7.6.3 设G=〈V , E〉是一连通的有权图，则G的生成树TG为带权生成树, TG的树枝所带权之和称为生成树TG的权,记为C(TG ) 。G中具有最小权的生成树TG称为G的最小生成树。克