《一些特殊的图.pptx》由会员分享，可在线阅读，更多相关《一些特殊的图.pptx（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2023/3/231二部图二部图(偶图偶图)：若无向图若无向图G=G=的顶点集的顶点集V V能划能划 分成两个子集分成两个子集V V1 1和和V V2 2，使得，使得GG中任何一条边的中任何一条边的 两个端点一个属于两个端点一个属于V V1 1，另一个属于，另一个属于V V2 2，则称，则称GG 为二部图为二部图(偶图偶图)。V V1 1,V V2 2称为互补顶点子集。称为互补顶点子集。8.1 8.1 二部图二部图完全二部图完全二部图(完全偶图完全偶图)：若若V V1 1中任一顶点与中任一顶点与V V2 2中每个中每个 顶点均有且仅有一条边相关联，则称顶点均有且仅有一条边相关联，则称GG为完全
2、为完全 二部图二部图(完全偶图完全偶图)。若若|V V1 1|=n n，|V V2 2|=mm，则记完全二部图，则记完全二部图GG为为K Kn n,m m第1页/共22页2023/3/232二部图（续）K K2,2,3 3K K3,3,3 3一个无向图一个无向图G=G=是二部图当且仅当是二部图当且仅当GG中无奇数长度的回路。中无奇数长度的回路。二部图判定定理第2页/共22页2023/3/233二部图（续）例例1 1：判断下列图是否为二部图。：判断下列图是否为二部图。v v4 4v v3 3v v2 2v v1 1v v5 5v v6 6v v7 7v v8 8同构于同构于v v4 4v v3
3、3v v2 2v v1 1v v5 5v v6 6同构于同构于v v6 6v v4 4v v3 3v v2 2v v1 1v v5 5v v7 7v v8 8v v4 4v v3 3v v2 2v v1 1v v5 5v v6 6第3页/共22页2023/3/2348.2 8.2 欧拉图欧拉图哥尼斯堡七桥问题哥尼斯堡七桥问题第4页/共22页2023/3/235欧拉通路欧拉通路(欧拉回路欧拉回路)：经过图中经过图中每条边每条边一次且仅一一次且仅一 次并且行遍次并且行遍每个顶点每个顶点的通路的通路(回路回路)，称为欧拉通路称为欧拉通路(欧拉回路欧拉回路)。欧拉图：欧拉图：存在欧拉回路的图。存在欧拉
4、回路的图。第5页/共22页2023/3/236欧拉图（续）(1)(1)无向图无向图GG具有具有欧拉通路欧拉通路当且仅当当且仅当GG是连通图且有是连通图且有 零个或两个零个或两个奇数度顶点。奇数度顶点。欧拉图的判定定理：欧拉图的判定定理：(2)(2)无向图无向图GG是是欧拉图欧拉图(具有欧拉回路具有欧拉回路)当且仅当当且仅当GG是是 连通图且所有顶点的度数连通图且所有顶点的度数全为偶数全为偶数。第6页/共22页2023/3/237欧拉图（续）欧拉图的判定定理：欧拉图的判定定理：(4)(4)有向图有向图D D是是欧拉图欧拉图(具有欧拉回路具有欧拉回路)当且仅当当且仅当D D是是 连通图，且所有顶点
5、的连通图，且所有顶点的入度等于出度入度等于出度。(3)(3)有向图有向图D D具有具有欧拉通路欧拉通路当且仅当当且仅当D D是连通图，且是连通图，且 除了两个顶点外除了两个顶点外，其余顶点的，其余顶点的入度均等于出度入度均等于出度。这两个特殊的顶点中，一个顶点的入度比出度这两个特殊的顶点中，一个顶点的入度比出度 大大1 1，另一个顶点的出度比入度大，另一个顶点的出度比入度大1 1 1 1。第7页/共22页2023/3/238欧拉图（续）例例2 2：判断下列图是否为欧拉图。：判断下列图是否为欧拉图。f fd db ba ae ec cg gh hi ij jd db ba ae ec cd db
6、 ba ae ec c是欧拉图是欧拉图不是欧拉图，不是欧拉图，但有欧拉通路但有欧拉通路是欧拉图是欧拉图第8页/共22页2023/3/2398.3 8.3 哈密尔顿图哈密尔顿图哈密尔顿通路哈密尔顿通路(哈密尔顿回路哈密尔顿回路)：经过图中每个顶点经过图中每个顶点 一次且仅一次的通路一次且仅一次的通路(回路回路)，称为哈密尔顿通路称为哈密尔顿通路(哈密尔顿回路哈密尔顿回路)。哈密尔顿图：哈密尔顿图：存在哈密尔顿回路的图。存在哈密尔顿回路的图。d db ba ae ec cd db ba ae ec cd db ba ae ec cf f第9页/共22页2023/3/2310设设GG是是n n(n
7、n 3)3)阶无向简单图，阶无向简单图，(1)(1)若若GG中任何一对不相邻的顶点的度数之和中任何一对不相邻的顶点的度数之和 都大于等于都大于等于n n-1-1，则，则GG中存在哈密尔顿通路。中存在哈密尔顿通路。(2)(2)若若GG中任何一对不相邻的顶点的度数之和中任何一对不相邻的顶点的度数之和 都大于等于都大于等于n n，则，则GG是哈密尔顿图。是哈密尔顿图。哈密尔顿图设无向图设无向图G=G=是哈密尔顿图，是哈密尔顿图，V V1 1是是V V的的任意非空子集，则任意非空子集，则p p(GG V V1 1)|V V1 1|。其中，其中，p p(GG V V1 1)为从为从GG中删除中删除V V
8、1 1(删除删除V V1 1中各中各顶点及其关联的边顶点及其关联的边)后所得子图的连通分支数。后所得子图的连通分支数。必要条件充分条件第10页/共22页2023/3/2311哈密尔顿图例例3 3：判断下列图是否为哈密尔顿图。：判断下列图是否为哈密尔顿图。d db ba ae ec cf fV V1 1=a a p p(GG V V1 1)=2)=2|V V1 1|=1|=1不满足必要条件；不满足必要条件；V V1 1=a a，b b p p(GG V V1 1)=3)=3|V V1 1|=2|=2不满足必要条件；不满足必要条件；a ab b第11页/共22页2023/3/23128.4 8.4
9、 平面图平面图平面图：平面图：图图GG若若能够以除顶点外没有边交叉的方式能够以除顶点外没有边交叉的方式 画在平面上，则称画在平面上，则称GG为平面图。为平面图。K K5 5K K3,33,3一、平面图的基本概念及性质画出的没有边交叉的图称为画出的没有边交叉的图称为GG的一个的一个平面嵌入平面嵌入。第12页/共22页2023/3/2313一、平面图的基本概念及性质（续）面：面：设设GG是一个连通的平面图是一个连通的平面图(GG的某个平面嵌入的某个平面嵌入)，GG的边将的边将GG所在的平面划分成若干个区域，所在的平面划分成若干个区域，每个区域称为的一个面。每个区域称为的一个面。其中面积无限的区域称
10、为其中面积无限的区域称为无限面无限面(或外部面或外部面)，记，记R R0 0，面积有限的区域称为面积有限的区域称为有限面有限面(或内部面或内部面)。包围每个面的所有边所构成的回路称为该面的边界。包围每个面的所有边所构成的回路称为该面的边界。边界的长度称为该面的边界的长度称为该面的次数次数，R R的次数记为的次数记为degdeg(R R)。对于含对于含k k(k k 2 2)个连通分支的非连通的平面图，其个连通分支的非连通的平面图，其无限面无限面R R0 0的边界则由的边界则由k k个回路围成。个回路围成。第13页/共22页2023/3/2314一、平面图的基本概念及性质（续）v v1 1v v
11、2 2v v4 4v v3 3v v5 5v v6 6R R0 0R R1 1R R2 2v v1 1v v2 2v v4 4v v3 3v v5 5R R0 0R R1 1R R2 2R R3 3v v1 1v v2 2v v4 4v v3 3v v5 5R R0 0R R1 1R R2 2v v6 6v v7 7degdeg(R R1 1)=3)=3degdeg(R R1 1)=4)=4degdeg(R R1 1)=4)=4degdeg(R R2 2)=3)=3degdeg(R R0 0)=8)=8degdeg(R R2 2)=3)=3degdeg(R R3 3)=1)=1degdeg(R
12、 R0 0)=6)=6degdeg(R R2 2)=3)=3degdeg(R R0 0)=7)=7第14页/共22页2023/3/2315一、平面图的基本概念及性质（续）定理在一个平面图在一个平面图GG中，所有面的次数之和都中，所有面的次数之和都等于边数等于边数mm的的2 2倍。倍。即即 ，其中，其中r r为面数。为面数。第15页/共22页2023/3/2316设设GG是任意的连通的平面图，是任意的连通的平面图，则有则有n n m m+r r=2=2成立。成立。其中：其中：n n为顶点数，为顶点数，mm为边数，为边数，r r为面数。为面数。欧拉公式推广设设GG是任意的连通分支为是任意的连通分支
13、为p p(p p 2 2)的平面图，的平面图，则有则有n n m m+r r=p p+1+1成立。成立。其中：其中：n n为顶点数，为顶点数，mm为边数，为边数，r r为面数。为面数。一、平面图的基本概念及性质（续）第16页/共22页2023/3/23178.5 8.5 树树树：树：连通而连通而不含回路不含回路的无向图称为的无向图称为无向树无向树，简称树简称树。常记做常记做T T。树叶：树叶：树中度数为树中度数为1 1的结点。的结点。分支点：分支点：树中度数大于树中度数大于1 1的结点。的结点。森林：森林：连通分支数大于等于连通分支数大于等于2,2,2,2,且每个连通分支都是树的且每个连通分支
14、都是树的无向图。无向图。平凡树：平凡树：平凡图。平凡图。本章所指回路为简单回路或初级回路本章所指回路为简单回路或初级回路第17页/共22页2023/3/2318树第18页/共22页2023/3/2319 (1)(1)GG连通且不含回路；连通且不含回路；(2)(2)GG中无回路，且中无回路，且mm=n n-1-1，其中，其中mm为边，为边，n n为结点数；为结点数；(3)(3)GG是连通的，且是连通的，且mm=n n-1-1;(4)(4)GG中无回路，但在中无回路，但在GG中任意不相邻两结点之间增加一中任意不相邻两结点之间增加一条边，就得到唯一的一条初级回路；条边，就得到唯一的一条初级回路；(5
15、)(5)GG是连通的且是连通的且GG中每条边都是桥；中每条边都是桥；(6)(6)GG中每一对结点之间有唯一的一条基本通路。中每一对结点之间有唯一的一条基本通路。树的等价定义任意非平凡树任意非平凡树T(T(n n,mm)至少有两片树叶。至少有两片树叶。定理树第19页/共22页2023/3/2320例：例：画出画出6 6 6 6阶所有非同构的无向树。阶所有非同构的无向树。(1)1，1，1，1，1，5(2)1，1，1，1，2，4(3)1，1，1，1，3，3(4)1，1，1，2，2，3 两种两种(5)1，1，2，2，2，2解：解：设设T T是是6 6阶无向树，阶无向树，T T的边数的边数mm5 5 5 5，由握手定理可知，由握手定理可知，d d(v v)10101010，且，且(T)(T)1111，(T)(T)5555。故。故T T T T的度数列必为以下情况之一：的度数列必为以下情况之一：树第20页/共22页2023/3/2321树第21页/共22页2023/3/23离散数学22谢谢大家观赏！第22页/共22页