7208一些特殊的图

2020/2/10离散数学1第八章一些特殊的图§8.1二部图§8.2欧拉图§8.3哈密尔顿图§8.4平面图2020/2/10离散数学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/10离散数学3二部图（续）K2,3K3,3一个无向图G=V,E是二部图当且仅当G中无奇数长度的回路。二部图判定定理2020/2/10离散数学4二部图（续）例1：判断下列图是否为二部图。v4v3v2v1v5v6v7v8同构于v4v3v2v1v5v6同构于v6v4v3v2v1v5v7v8v4v3v2v1v5v62020/2/10离散数学5§8.2欧拉图哥尼斯堡七桥问题2020/2/10离散数学6欧拉通路(欧拉回路)：经过图中每条边一次且仅一次并且行遍每个顶点的通路(回路)，称为欧拉通路(欧拉回路)。欧拉图：存在欧拉回路的图。半欧拉图：具有欧拉通路而无欧拉回路的图。2020/2/10离散数学72020/2/10离散数学8欧拉图（续）(1)无向图G是欧拉图(具有欧拉回路)当且仅当G是连通图且无奇度顶点。欧拉图的判定定理：(2)无向图G是半欧拉图(具有欧拉通路)当且仅当G是连通图且两个奇度顶点。2020/2/10离散数学9欧拉图（续）欧拉图的判定定理：(4)有向图D是欧拉图(具有欧拉回路)当且仅当D是连通图，且所有顶点的入度等于出度。(3)有向图D是半欧拉图当且仅当D是连通图，且除了两个顶点外(奇度)，其余顶点的入度均等于出度。这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的出度比入度大1。2020/2/10离散数学10欧拉图（续）例2：判断下列图是否为欧拉图。fdbaecghijdbaecdbaec是欧拉图不是欧拉图，但有欧拉通路是欧拉图2020/2/10离散数学11中国邮递员问题著名图论问题之一。邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线?此问题由中国数学家管梅谷于1960年首先研究并给出算法，故名。2020/2/10离散数学12§8.3哈密尔顿图哈密尔顿通路(哈密尔顿回路)：经过图中每个顶点一次且仅一次的通路(回路)，称为哈密尔顿通路(哈密尔顿回路)。半哈密尔顿图：存在哈密尔顿通路而无哈密尔顿回路的图。dbaecdbaecdbaecf哈密尔顿图：存在哈密尔顿回路的图。(含平凡图)2020/2/10离散数学13设G是n(n3)阶无向简单图，(1)若G中任何一对不相邻的顶点的度数之和都大于等于n-1，则G中存在哈密尔顿通路。(2)若G中任何一对不相邻的顶点的度数之和都大于等于n，则G是哈密尔顿图。哈密尔顿图（续）设无向图G=V,E是哈密尔顿图，V1是V的任意非空子集，则p(G–V1)|V1|。peterson其中，p(G–V1)为从G中删除V1(删除V1中各顶点及其关联的边)后所得子图的连通分支数。必要条件充分条件2020/2/10离散数学14n(n3)阶有向完全图是哈密尔顿图。哈密尔顿图（续）在n(n2)阶有向图D=V,E中，如果所有有向边均用无向边代替，所得无向图中含生成子图Kn，则有向图D中存在哈密尔顿通路。充分条件推论2020/2/10离散数学15哈密尔顿图（续）例3：判断下列图是否为哈密尔顿图。2020/2/10离散数学16§8.4平面图平面图：图G若能够以除顶点外没有边交叉的方式画在平面上，则称G为平面图(可平面图)。K5K3,3一、平面图的基本概念及性质画出的没有边交叉的图称为G的一个平面嵌入。2020/2/10离散数学17一、平面图的基本概念及性质（续）面：设G是一个连通的平面图(G的某个平面嵌入)，G的边将G所在的平面划分成若干个区域，每个区域称为的一个面。其中面积无限的区域称为无限面(或外部面)，记R0，面积有限的区域称为有限面(或内部面)。包围每个面的所有边所构成的回路称为该面的边界。边界的长度称为该面的次数，R的次数记为deg(R)。对于含k(k2)个连通分支的非连通的平面图，其无限面R0的边界则由k个回路围成。2020/2/10离散数学18一、平面图的基本概念及性质（续）v1v2v4v3v5v6R0R1R2v1v2v4v3v5R0R1R2R3v1v2v4v3v5R0R1R2v6v7deg(R1)=3deg(R1)=4deg(R1)=4deg(R2)=3deg(R0)=8deg(R2)=3deg(R3)=1deg(R0)=6deg(R2)=3deg(R0)=72020/2/10离散数学19一、平面图的基本概念及性质（续）定理在一个平面图G中，所有面的次数之和都等于边数m的2倍。即，其中r为面数。riimR12)deg(2020/2/10离散数学20一、平面图的基本概念及性质（续）极大平面图：设G是一个简单平面图，如果在G中任意不相邻的两个顶点之间再加一条边，所得图为非平面图，则称G为极大平面图。极大平面图的性质：(1)极大平面图是连通的；(2)任何n(n3)阶极大平面图每个面的次数均为3；(3)任何n(n4)阶极大平面图G均有(G)3。极小非平面图：若在非平面图G中任意删除一条边，所得图为平面图，则称G为极小非平面图。2020/2/10离散数学21一、平面图的基本概念及性质（续）设G是任意的连通的平面图，则有n–m+r=2成立。其中：n为顶点数，m为边数，r为面数。欧拉公式设G是任意的连通分支为p(p2)的平面图，则有n–m+r=p+1成立。其中：n为顶点数，m为边数，r为面数。推广2020/2/10离散数学22一、平面图的基本概念及性质（续）定理推广设G是连通的平面图，且每个面的次数至少为l(l3)，则。K5不满足:10=3(5-2))2(2nllm设G是连通分支为p(p2)的平面图，每个面的次数至少为l(l3)，则。)1(2pnllm2020/2/10离散数学23初等收缩：图G中相邻顶点u,v间的收缩，即删除边(u,v),以新的顶点w取代u,v，使w关联u,v的一切边(除(u,v)外)。二、平面图的判定同胚：如果两个图G1和G2同构，或经过反复插入或消去2度顶点后同构，则称G1与G2同胚。uvwuvabcdefbcdefgabcdawd2020/2/10离散数学24二、平面图的判定（续）一个图是平面图当且仅当它不含与K5同胚子图，也不含与K3,3同胚子图。判定定理一个图是平面图当且仅当它没有可以收缩到K5的子图，也没有收缩到K3,3的子图。判定定理库拉图斯基定理: