08一些特殊的图

2020/2/12离散数学1第八章一些特殊的图§8.1二部图§8.2欧拉图§8.3哈密尔顿图§8.4平面图§8.5树2020/2/12离散数学2二部图(偶图)：若无向图G=V,E的顶点集V能划分成两个子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图(偶图)。V1,V2称为互补顶点子集。§8.1二部图完全二部图(完全偶图)：若V1中任一顶点与V2中每个顶点均有且仅有一条边相关联，则称G为完全二部图(完全偶图)。若|V1|=n，|V2|=m，则记完全二部图G为Kn,m2020/2/12离散数学3二部图（续）K2,3K3,3一个无向图G=V,E是二部图当且仅当G中无奇数长度的回路。二部图判定定理2020/2/12离散数学4二部图（续）例1：判断下列图是否为二部图。v4v3v2v1v5v6v7v8同构于v4v3v2v1v5v6同构于v6v4v3v2v1v5v7v8v4v3v2v1v5v62020/2/12离散数学5§8.2欧拉图哥尼斯堡七桥问题2020/2/12离散数学6欧拉通路(欧拉回路)：经过图中每条边一次且仅一次并且行遍每个顶点的通路(回路)，称为欧拉通路(欧拉回路)。欧拉图：存在欧拉回路的图。2020/2/12离散数学7欧拉图（续）(1)无向图G具有欧拉通路当且仅当G是连通图且有零个或两个奇数度顶点。欧拉图的判定定理：(2)无向图G是欧拉图(具有欧拉回路)当且仅当G是连通图且所有顶点的度数全为偶数。2020/2/12离散数学8欧拉图（续）欧拉图的判定定理：(4)有向图D是欧拉图(具有欧拉回路)当且仅当D是连通图，且所有顶点的入度等于出度。(3)有向图D具有欧拉通路当且仅当D是连通图，且除了两个顶点外，其余顶点的入度均等于出度。这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的出度比入度大1。2020/2/12离散数学9欧拉图（续）例2：判断下列图是否为欧拉图。fdbaecghijdbaecdbaec是欧拉图不是欧拉图，但有欧拉通路是欧拉图2020/2/12离散数学10§8.3哈密尔顿图哈密尔顿通路(哈密尔顿回路)：经过图中每个顶点一次且仅一次的通路(回路)，称为哈密尔顿通路(哈密尔顿回路)。哈密尔顿图：存在哈密尔顿回路的图。dbaecdbaecdbaecf2020/2/12离散数学11设G是n(n3)阶无向简单图，(1)若G中任何一对不相邻的顶点的度数之和都大于等于n-1，则G中存在哈密尔顿通路。(2)若G中任何一对不相邻的顶点的度数之和都大于等于n，则G是哈密尔顿图。哈密尔顿图设无向图G=V,E是哈密尔顿图，V1是V的任意非空子集，则p(G–V1)|V1|。其中，p(G–V1)为从G中删除V1(删除V1中各顶点及其关联的边)后所得子图的连通分支数。必要条件充分条件2020/2/12离散数学12哈密尔顿图例3：判断下列图是否为哈密尔顿图。dbaecfV1={a}p(G–V1)=2|V1|=1不满足必要条件；V1={a，b}p(G–V1)=3|V1|=2不满足必要条件；ab2020/2/12离散数学13§8.4平面图平面图：图G若能够以除顶点外没有边交叉的方式画在平面上，则称G为平面图。K5K3,3一、平面图的基本概念及性质画出的没有边交叉的图称为G的一个平面嵌入。2020/2/12离散数学14一、平面图的基本概念及性质（续）面：设G是一个连通的平面图(G的某个平面嵌入)，G的边将G所在的平面划分成若干个区域，每个区域称为的一个面。其中面积无限的区域称为无限面(或外部面)，记R0，面积有限的区域称为有限面(或内部面)。包围每个面的所有边所构成的回路称为该面的边界。边界的长度称为该面的次数，R的次数记为deg(R)。对于含k(k2)个连通分支的非连通的平面图，其无限面R0的边界则由k个回路围成。2020/2/12离散数学15一、平面图的基本概念及性质（续）v1v2v4v3v5v6R0R1R2v1v2v4v3v5R0R1R2R3v1v2v4v3v5R0R1R2v6v7deg(R1)=3deg(R1)=4deg(R1)=4deg(R2)=3deg(R0)=8deg(R2)=3deg(R3)=1deg(R0)=6deg(R2)=3deg(R0)=72020/2/12离散数学16一、平面图的基本概念及性质（续）定理在一个平面图G中，所有面的次数之和都等于边数m的2倍。即，其中r为面数。riimR12)deg(2020/2/12离散数学17设G是任意的连通的平面图，则有n–m+r=2成立。其中：n为顶点数，m为边数，r为面数。欧拉公式推广设G是任意的连通分支为p(p2)的平面图，则有n–m+r=p+1成立。其中：n为顶点数，m为边数，r为面数。一、平面图的基本概念及性质（续）2020/2/12离散数学18§8.5树树：连通而不含回路的无向图称为无向树，简称树。常记做T。树叶：树中度数为1的结点。分支点：树中度数大于1的结点。森林：连通分支数大于等于2,且每个连通分支都是树的无向图。平凡树：平凡图。本章所指回路为简单回路或初级回路2020/2/12离散数学19树2020/2/12离散数学20(1)G连通且不含回路；(2)G中无回路，且m=n-1，其中m为边，n为结点数；(3)G是连通的，且m=n-1;(4)G中无回路，但在G中任意不相邻两结点之间增加一条边，就得到唯一的一条初级回路；(5)G是连通的且G中每条边都是桥；(6)G中每一对结点之间有唯一的一条基本通路。树的等价定义任意非平凡树T(n,m)至少有两片树叶。定理树2020/2/12离散数学21例：画出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是6阶无向树，T的边数m＝5，由握手定理可知，∑d(v)＝10，且δ(T)≥1，△(T)≤5。故T的度数列必为以下情况之一：树2020/2/12离散数学22树