08一些特殊的图.ppt

6/26/20236/26/20231 1离散数学离散数学二部图二部图二部图二部图(偶图偶图偶图偶图)：若无向图若无向图若无向图若无向图G=G=的顶点集的顶点集的顶点集的顶点集V V能划能划能划能划 分成两个子集分成两个子集分成两个子集分成两个子集V V1 1和和和和V V2 2，使得使得使得使得G G中任何一条边的中任何一条边的中任何一条边的中任何一条边的 两个端点一个属于两个端点一个属于两个端点一个属于两个端点一个属于V V1 1，另一个属于另一个属于另一个属于另一个属于V V2 2，则称则称则称则称G G 为二部图为二部图为二部图为二部图(偶图偶图偶图偶图)。V V1 1,V V2 2称为互补顶点子集。称为互补顶点子集。称为互补顶点子集。称为互补顶点子集。8.1 8.1 二部图二部图完全二部图完全二部图完全二部图完全二部图(完全偶图完全偶图完全偶图完全偶图)：若若若若V V1 1中任一中任一中任一中任一顶点与顶点与顶点与顶点与V V2 2中每个中每个中每个中每个 顶点均有且仅有一条边相关联，则称顶点均有且仅有一条边相关联，则称顶点均有且仅有一条边相关联，则称顶点均有且仅有一条边相关联，则称G G为完全为完全为完全为完全 二部图二部图二部图二部图(完全偶图完全偶图完全偶图完全偶图)。若若若若|V V1 1|=n n，|V V2 2|=mm，则记完全二部图则记完全二部图则记完全二部图则记完全二部图G G为为为为K Kn n,m m6/26/20236/26/20232 2离散数学离散数学二部图（续）K K2,2,3 3K K3,3,3 3一个无向图一个无向图一个无向图一个无向图G=G=是二部图当且仅当是二部图当且仅当是二部图当且仅当是二部图当且仅当G G中无奇数长度的回路。中无奇数长度的回路。中无奇数长度的回路。中无奇数长度的回路。6/26/20236/26/20233 3离散数学离散数学二部图（续）例例例例1 1：判断下列图是否为二部图。：判断下列图是否为二部图。：判断下列图是否为二部图。：判断下列图是否为二部图。v v4 4v v3 3v v2 2v v1 1v v5 5v v6 6v v7 7v v8 8同构于同构于同构于同构于v v4 4v v3 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 66/26/20236/26/20234 4离散数学离散数学8.2 8.2 欧拉图欧拉图哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题6/26/20236/26/20235 5离散数学离散数学欧拉通路欧拉通路欧拉通路欧拉通路(欧拉回路欧拉回路欧拉回路欧拉回路)：经过图中经过图中经过图中经过图中每条边每条边每条边每条边一次且仅一一次且仅一一次且仅一一次且仅一 次并且行遍次并且行遍次并且行遍次并且行遍每个顶点每个顶点每个顶点每个顶点的通路的通路的通路的通路(回路回路回路回路)，称为欧拉通路称为欧拉通路称为欧拉通路称为欧拉通路(欧拉回路欧拉回路欧拉回路欧拉回路)。欧拉图欧拉图欧拉图欧拉图：存在欧拉回路的图。存在欧拉回路的图。存在欧拉回路的图。存在欧拉回路的图。6/26/20236/26/20236 6离散数学离散数学欧拉图（续）(1)(1)无向图无向图无向图无向图G G具有具有具有具有欧拉通路欧拉通路欧拉通路欧拉通路当且仅当当且仅当当且仅当当且仅当G G是连通图且有是连通图且有是连通图且有是连通图且有 零个或两个零个或两个零个或两个零个或两个奇数度顶点。奇数度顶点。奇数度顶点。奇数度顶点。欧拉图的判定定理欧拉图的判定定理欧拉图的判定定理欧拉图的判定定理：(2)(2)无向图无向图无向图无向图G G是是是是欧拉图欧拉图欧拉图欧拉图(具有欧拉回路具有欧拉回路具有欧拉回路具有欧拉回路)当且仅当当且仅当当且仅当当且仅当G G是是是是 连通图且所有顶点的度数连通图且所有顶点的度数连通图且所有顶点的度数连通图且所有顶点的度数全为偶数全为偶数全为偶数全为偶数。6/26/20236/26/20237 7离散数学离散数学欧拉图（续）欧拉图的判定定理欧拉图的判定定理欧拉图的判定定理欧拉图的判定定理：(4)(4)有向图有向图有向图有向图D D是是是是欧拉图欧拉图欧拉图欧拉图(具有欧拉回路具有欧拉回路具有欧拉回路具有欧拉回路)当且仅当当且仅当当且仅当当且仅当D D是是是是 连通图，且所有顶点的连通图，且所有顶点的连通图，且所有顶点的连通图，且所有顶点的入度等于出度入度等于出度入度等于出度入度等于出度。(3)(3)有向图有向图有向图有向图D D具有具有具有具有欧拉通路欧拉通路欧拉通路欧拉通路当且仅当当且仅当当且仅当当且仅当D D是连通图，且是连通图，且是连通图，且是连通图，且 除了两个顶点外除了两个顶点外除了两个顶点外除了两个顶点外，其余顶点的，其余顶点的，其余顶点的，其余顶点的入度均等于出度入度均等于出度入度均等于出度入度均等于出度。这两个特殊的顶点中，一个顶点的入度比出度这两个特殊的顶点中，一个顶点的入度比出度这两个特殊的顶点中，一个顶点的入度比出度这两个特殊的顶点中，一个顶点的入度比出度 大大大大1 1，另一个顶点的出度比入度大，另一个顶点的出度比入度大，另一个顶点的出度比入度大，另一个顶点的出度比入度大1 1 1 1。6/26/20236/26/20238 8离散数学离散数学欧拉图（续）例例例例2 2：判断下列图是否为欧拉图：判断下列图是否为欧拉图：判断下列图是否为欧拉图：判断下列图是否为欧拉图。f fd db ba ae ec cg gh hi ij jd db ba ae ec cd db ba ae ec c是欧拉图是欧拉图是欧拉图是欧拉图不是欧拉图，不是欧拉图，不是欧拉图，不是欧拉图，但有欧拉通路但有欧拉通路但有欧拉通路但有欧拉通路是欧拉图是欧拉图是欧拉图是欧拉图6/26/20236/26/20239 9离散数学离散数学8.3 8.3 哈密尔顿图哈密尔顿图哈密尔顿通路哈密尔顿通路哈密尔顿通路哈密尔顿通路(哈密尔顿回路哈密尔顿回路哈密尔顿回路哈密尔顿回路)：经过图中每个顶点经过图中每个顶点经过图中每个顶点经过图中每个顶点 一次且仅一次的通路一次且仅一次的通路一次且仅一次的通路一次且仅一次的通路(回路回路回路回路)，称为哈密尔顿通路称为哈密尔顿通路称为哈密尔顿通路称为哈密尔顿通路(哈密尔顿回路哈密尔顿回路哈密尔顿回路哈密尔顿回路)。哈密尔顿图哈密尔顿图哈密尔顿图哈密尔顿图：存在哈密尔顿回路的图。存在哈密尔顿回路的图。存在哈密尔顿回路的图。存在哈密尔顿回路的图。d db ba ae ec cd db ba ae ec cd db ba ae ec cf f6/26/20236/26/20231010离散数学离散数学设设设设G G是是是是n n(n n 3)3)阶无向简单图，阶无向简单图，阶无向简单图，阶无向简单图，(1)(1)若若若若G G中任何一对不相邻的顶点的度数之和中任何一对不相邻的顶点的度数之和中任何一对不相邻的顶点的度数之和中任何一对不相邻的顶点的度数之和 都大于等于都大于等于都大于等于都大于等于n n-1-1，则，则，则，则G G中存在哈密尔顿通路。中存在哈密尔顿通路。中存在哈密尔顿通路。中存在哈密尔顿通路。(2)(2)若若若若G G中任何一对不相邻的顶点的度数之和中任何一对不相邻的顶点的度数之和中任何一对不相邻的顶点的度数之和中任何一对不相邻的顶点的度数之和 都大于等于都大于等于都大于等于都大于等于n n，则，则，则，则G G是哈密尔顿图。是哈密尔顿图。是哈密尔顿图。是哈密尔顿图。哈密尔顿图设无向图设无向图设无向图设无向图G=G=是哈密尔顿图，是哈密尔顿图，是哈密尔顿图，是哈密尔顿图，V V1 1是是是是V V的的的的任意非空子集，则任意非空子集，则任意非空子集，则任意非空子集，则p p(G G V V1 1)|V V1 1|。其中，其中，其中，其中，p p(G G V V1 1)为从为从为从为从G G中删除中删除中删除中删除V V1 1(删除删除删除删除V V1 1中各中各中各中各顶点及其关联的边顶点及其关联的边顶点及其关联的边顶点及其关联的边)后所得子图的连通分支数。后所得子图的连通分支数。后所得子图的连通分支数。后所得子图的连通分支数。6/26/20236/26/20231111离散数学离散数学哈密尔顿图例例例例3 3：判断下列图是否为哈密尔顿图：判断下列图是否为哈密尔顿图：判断下列图是否为哈密尔顿图：判断下列图是否为哈密尔顿图。d db ba ae ec cf fV V1 1=a a p p(G G V V1 1)=2)=2|V V1 1|=1|=1不满足必要条件；不满足必要条件；不满足必要条件；不满足必要条件；V V1 1=a a，b b p p(G G V V1 1)=3)=3|V V1 1|=2|=2不满足必要条件；不满足必要条件；不满足必要条件；不满足必要条件；a ab b6/26/20236/26/20231212离散数学离散数学8.4 8.4 平面图平面图平面图：平面图：平面图：平面图：图图图图G G若若若若能够以除顶点外没有边交叉的方式能够以除顶点外没有边交叉的方式能够以除顶点外没有边交叉的方式能够以除顶点外没有边交叉的方式 画在平面上，则称画在平面上，则称画在平面上，则称画在平面上，则称G G为平面图。为平面图。为平面图。为平面图。K K5 5K K3,33,3一、平面图的基本概念及性质画出的没有边交叉的图称为画出的没有边交叉的图称为画出的没有边交叉的图称为画出的没有边交叉的图称为G G的一个的一个的一个的一个平面嵌入平面嵌入平面嵌入平面嵌入。6/26/20236/26/20231313离散数学离散数学一、平面图的基本概念及性质（续）面：面：面：面：设设设设G G是一个连通的平面图是一个连通的平面图是一个连通的平面图是一个连通的平面图(G G的某个平面嵌入的某个平面嵌入的某个平面嵌入的某个平面嵌入)，G G的边将的边将的边将的边将G G所在的平面划分成若干个区域，所在的平面划分成若干个区域，所在的平面划分成若干个区域，所在的平面划分成若干个区域，每个区域称为的一个面。每个区域称为的一个面。每个区域称为的一个面。每个区域称为的一个面。其中面积无限的区域称为其中面积无限的区域称为其中面积无限的区域称为其中面积无限的区域称为无限面无限面无限面无限面(或外部面或外部面或外部面或外部面)，记，记，记，记R R0 0，面积有限的区域称为面积有限的区域称为面积有限的区域称为面积有限的区域称为有限面有限面有限面有限面(或内部面或内部面或内部面或内部面)。包围每个面的所有边所构成的回路称为该面的边界。包围每个面的所有边所构成的回路称为该面的边界。包围每个面的所有边所构成的回路称为该面的边界。包围每个面的所有边所构成的回路称为该面的边界。边界的长度称为该面的边界的长度称为该面的边界的长度称为该面的边界的长度称为该面的次数次数次数次数，R R的次数记为的次数记为的次数记为的次数记为degdeg(R R)。对于含对于含对于含对于含k k(k k 2 2)个连通分支的非连通的平面图，其个连通分支的非连通的平面图，其个连通分支的非连通的平面图，其个连通分支的非连通的平面图，其无限面无限面无限面无限面R R0 0的边界则由的边界则由的边界则由的边界则由k k个回路围成。个回路围成。个回路围成。个回路围成。6/26/20236/26/20231414离散数学离散数学一、平面图的基本概念及性质（续）v v1 1v v2 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 R0 0)=6)=6degdeg(R R2 2)=3)=3degdeg(R R0 0)=7)=76/26/20236/26/20231515离散数学离散数学一、平面图的基本概念及性质（续）在一个平面图在一个平面图在一个平面图在一个平面图G G中，所有面的次数之和都中，所有面的次数之和都中，所有面的次数之和都中，所有面的次数之和都等于边数等于边数等于边数等于边数mm的的的的2 2倍。倍。倍。倍。即即即即 ，其中，其中，其中，其中r r为面数。为面数。为面数。为面数。6/26/20236/26/20231616离散数学离散数学设设设设G G是任意的连通的平面图，是任意的连通的平面图，是任意的连通的平面图，是任意的连通的平面图，则有则有则有则有n n m m+r r=2=2成立。成立。成立。成立。其中：其中：其中：其中：n n为顶点数，为顶点数，为顶点数，为顶点数，mm为边数，为边数，为边数，为边数，r r为面数。为面数。为面数。为面数。设设设设G G是任意的连通分支为是任意的连通分支为是任意的连通分支为是任意的连通分支为p p(p p 2 2)的平面图，的平面图，的平面图，的平面图，则有则有则有则有n n m m+r r=p p+1+1成立。成立。成立。成立。其中：其中：其中：其中：n n为顶点数，为顶点数，为顶点数，为顶点数，mm为边数，为边数，为边数，为边数，r r为面数。为面数。为面数。为面数。一、平面图的基本概念及性质（续）6/26/20236/26/20231717离散数学离散数学8.5 8.5 树树树：树：树：树：连通而连通而连通而连通而不含回路不含回路不含回路不含回路的无向图称为的无向图称为的无向图称为的无向图称为无向树无向树无向树无向树，简称树简称树简称树简称树。常记做常记做常记做常记做T T。树叶：树叶：树叶：树叶：树中度数为树中度数为树中度数为树中度数为1 1的结点。的结点。的结点。的结点。分支点：分支点：分支点：分支点：树中度数大于树中度数大于树中度数大于树中度数大于1 1的结点。的结点。的结点。的结点。森林：森林：森林：森林：连通分支数大于等于连通分支数大于等于连通分支数大于等于连通分支数大于等于2,2,2,2,且每个连通分支都是树的且每个连通分支都是树的且每个连通分支都是树的且每个连通分支都是树的无向图。无向图。无向图。无向图。平凡树：平凡树：平凡树：平凡树：平凡图。平凡图。平凡图。平凡图。本章所指回路为简单回路或初级回路本章所指回路为简单回路或初级回路本章所指回路为简单回路或初级回路本章所指回路为简单回路或初级回路6/26/20236/26/20231818离散数学离散数学树6/26/20236/26/20231919离散数学离散数学 (1)(1)G G连通且不含回路；连通且不含回路；连通且不含回路；连通且不含回路；(2)(2)G G中无回路，且中无回路，且中无回路，且中无回路，且mm=n n-1-1，其中，其中，其中，其中mm为边，为边，为边，为边，n n为结点数；为结点数；为结点数；为结点数；(3)(3)G G是连通的，且是连通的，且是连通的，且是连通的，且mm=n n-1-1;(4)(4)G G中无回路，但在中无回路，但在中无回路，但在中无回路，但在G G中任意不相邻两结点之间增加一中任意不相邻两结点之间增加一中任意不相邻两结点之间增加一中任意不相邻两结点之间增加一条边，就得到唯一的一条初级回路；条边，就得到唯一的一条初级回路；条边，就得到唯一的一条初级回路；条边，就得到唯一的一条初级回路；(5)(5)G G是连通的且是连通的且是连通的且是连通的且G G中每条边都是桥；中每条边都是桥；中每条边都是桥；中每条边都是桥；(6)(6)G G中每一对结点之间有唯一的一条基本通路。中每一对结点之间有唯一的一条基本通路。中每一对结点之间有唯一的一条基本通路。中每一对结点之间有唯一的一条基本通路。任意非平凡树任意非平凡树任意非平凡树任意非平凡树T(T(n n,mm)至少有两片树叶。至少有两片树叶。至少有两片树叶。至少有两片树叶。树6/26/20236/26/20232020离散数学离散数学例：例：例：例：画出画出画出画出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)1 1 1 1，(T)(T)5 5 5 5。故故故故T T T T的度数列必为以下情况之一：的度数列必为以下情况之一：的度数列必为以下情况之一：的度数列必为以下情况之一：树6/26/20236/26/20232121离散数学离散数学树6/26/20236/26/20232222离散数学离散数学