(1.1)--离散数学离散数学.ppt

2024/1/202024/1/20离散数学离散数学1 12024/1/202024/1/20离散数学离散数学2 2第十章第十章 一些特殊的图一些特殊的图 10.110.1 二部图二部图二部图二部图 10.210.2 欧拉图欧拉图欧拉图欧拉图 10.310.3 哈密尔顿图哈密尔顿图哈密尔顿图哈密尔顿图 10.410.4 平面图平面图平面图平面图 2024/1/202024/1/20离散数学离散数学3 3 亚瑟国王的配婚问题：亚瑟国王的配婚问题：亚瑟国王的配婚问题：亚瑟国王的配婚问题：150150150150个卫士和个卫士和个卫士和个卫士和150150150150个宫女来个宫女来个宫女来个宫女来自不同的家族，有的家族之间有历史恩怨，彼此不愿自不同的家族，有的家族之间有历史恩怨，彼此不愿自不同的家族，有的家族之间有历史恩怨，彼此不愿自不同的家族，有的家族之间有历史恩怨，彼此不愿意成婚。意成婚。意成婚。意成婚。亚瑟国王要求其一大臣将他们配对成婚，否则将亚瑟国王要求其一大臣将他们配对成婚，否则将亚瑟国王要求其一大臣将他们配对成婚，否则将亚瑟国王要求其一大臣将他们配对成婚，否则将把该大臣投入监狱。把该大臣投入监狱。把该大臣投入监狱。把该大臣投入监狱。大臣要求男女各站一边，彼此愿意成婚的举手，大臣要求男女各站一边，彼此愿意成婚的举手，大臣要求男女各站一边，彼此愿意成婚的举手，大臣要求男女各站一边，彼此愿意成婚的举手，结果大臣认为无法配对成婚。结果大臣认为无法配对成婚。结果大臣认为无法配对成婚。结果大臣认为无法配对成婚。但国王不理解他的解释，他的命运？但国王不理解他的解释，他的命运？但国王不理解他的解释，他的命运？但国王不理解他的解释，他的命运？2024/1/202024/1/20离散数学离散数学4 4用图表示卫士与宫女愿意成婚的关系：用图表示卫士与宫女愿意成婚的关系：卫士卫士宫女宫女2024/1/202024/1/20离散数学离散数学5 51994年全国大学生数学建模竞赛年全国大学生数学建模竞赛B题：题：锁具装箱问题锁具装箱问题 某厂生产一种弹子锁具某厂生产一种弹子锁具,每个锁具的钥匙有每个锁具的钥匙有 5 5 个槽个槽,每个槽的高度从每个槽的高度从 1,2,3,4,5,6 6 1,2,3,4,5,6 6 个数个数 (单位略单位略)中任取一数中任取一数.由于工艺及其它原因由于工艺及其它原因,制制造锁具时对造锁具时对 5 5 个槽的高度个槽的高度 还有两个限制还有两个限制:至少有至少有 3 3 个不同的数个不同的数;相邻两槽高度之差不能为相邻两槽高度之差不能为 5.5.满足满足以上条件制造以上条件制造 出来的所有互不相同的锁具称为一出来的所有互不相同的锁具称为一批批.出来的所有互不相同的锁具称为一批出来的所有互不相同的锁具称为一批.从顾客的利益出发从顾客的利益出发,自然希望在每批锁具中自然希望在每批锁具中 一把钥匙开一把锁一把钥匙开一把锁.2024/1/202024/1/20离散数学离散数学6 6 但是在当前工但是在当前工 艺条件下艺条件下,对于同一批中两个对于同一批中两个锁具是否能够互开锁具是否能够互开,有以下试验结果有以下试验结果:若二者相对若二者相对应的应的 5 5个个 槽的高度中有槽的高度中有 4 4个相同个相同,另一个的高度另一个的高度差为差为 1,1,则可能互开则可能互开;在其它情形下在其它情形下,不可能互开不可能互开.原来原来,销售部门在一批锁具中随意地取每销售部门在一批锁具中随意地取每 6060个装一箱出售个装一箱出售.团体顾客往往购买团体顾客往往购买 几箱到几十箱几箱到几十箱,他们抱怨购得的锁具会出现互相开的情形他们抱怨购得的锁具会出现互相开的情形.现聘聘请你为顾问现聘聘请你为顾问,回答并解回答并解 决以下问题决以下问题:2024/1/202024/1/20离散数学离散数学7 7 1)1)每一批锁具有多少个每一批锁具有多少个,装多少箱装多少箱.2)2)为销售部门提供一种方案为销售部门提供一种方案,包括如何装箱包括如何装箱(仍是仍是6060个锁具一箱个锁具一箱),),如何给箱子以标志如何给箱子以标志,出售出售时如何利用这些标志时如何利用这些标志,使团体顾客不再或减少抱使团体顾客不再或减少抱怨怨.3)3)采取你提出的方案采取你提出的方案,团体顾客的购买量不团体顾客的购买量不超过多少箱超过多少箱,就可以保证一定不会出现互就可以保证一定不会出现互 4)4)按照原来的装箱办法按照原来的装箱办法,如何定量地衡量团如何定量地衡量团体顾客抱怨互开的程度体顾客抱怨互开的程度 (试对购买一、二试对购买一、二 箱者箱者给出具体结果给出具体结果).).2024/1/202024/1/20离散数学离散数学8 8可以证明：可以证明：(1)槽高的和为奇数槽高的和为奇数(或偶数或偶数)的锁之间不能互开；的锁之间不能互开；(2)一批锁具中，槽高的和为奇数与偶数的各占一批锁具中，槽高的和为奇数与偶数的各占一半。一半。2024/1/202024/1/20离散数学离散数学9 9此问题涉及到此问题涉及到“互开互开”关系，用图表示这种互开关关系，用图表示这种互开关系：系：奇奇偶偶以上两个问题对应图有什么特点？以上两个问题对应图有什么特点？2024/1/202024/1/20离散数学离散数学1010二部图二部图(偶图偶图)：若无向图若无向图G=的顶点集的顶点集V能能划分成两个子集划分成两个子集V1和和V2，使得，使得G中任何一条边的中任何一条边的 两个端点一个属于两个端点一个属于V1，另一个属于，另一个属于V2，则称，则称G为为二部图二部图(偶图偶图)。V1,V2称为互补顶点子集。称为互补顶点子集。10.1 10.1 二部图二部图完全二部图完全二部图(完全偶图完全偶图)：若若V1中任一顶点与中任一顶点与V2中中每个顶点均有且仅有一条边相关联，则称每个顶点均有且仅有一条边相关联，则称G为完为完全二部图全二部图(完全偶图完全偶图)。2024/1/202024/1/20离散数学离散数学1111K K2,2,3 3K K3,3,3 3一个无向图一个无向图G=是二部图当且仅是二部图当且仅当当G中无奇数长度的回路。中无奇数长度的回路。若若若若|V V1 1|=|=n n，|V V2 2|=|=mm，则记完全二部图，则记完全二部图，则记完全二部图，则记完全二部图G G为为为为K Kn n,m m圈的长度都是偶数圈的长度都是偶数2024/1/202024/1/20离散数学离散数学1212例例例例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 62024/1/202024/1/20离散数学离散数学1313匹配：匹配：设设E是图是图G=(V,E)的边集的子集，如果的边集的子集，如果E中的边是相互不相邻的，则称中的边是相互不相邻的，则称E是是G的一个匹配。的一个匹配。v v4 4v v3 3v v2 2v v1 1v v5 5v v6 62024/1/202024/1/20离散数学离散数学1414设设M是是G的一个匹配，的一个匹配，v是是G的一个点，如果的一个点，如果v是是M中某边的端点，则称中某边的端点，则称v为为M饱和饱和的。的。如果如果G中所有点都是中所有点都是M饱和的，则称饱和的，则称M为为完美匹配完美匹配。v v4 4v v3 3v v2 2v v1 1v v5 5v v6 62024/1/202024/1/20离散数学离散数学1515最大匹配最大匹配：边数最多的匹配。：边数最多的匹配。匹配数匹配数：最大匹配中元素的个数。：最大匹配中元素的个数。亚瑟王的配婚问题，就是寻找完美匹配。亚瑟王的配婚问题，就是寻找完美匹配。锁具装箱问题要求匹配数。锁具装箱问题要求匹配数。有关图的完美匹配的存在性的判断：有关图的完美匹配的存在性的判断：(1)Hall定理（二部图）；定理（二部图）；(2)Tutte定理（一般情况）。定理（一般情况）。2024/1/202024/1/20离散数学离散数学1616图论中的第一个问题：图论中的第一个问题：哥尼斯堡七桥问题哥尼斯堡七桥问题ABCDABCD欧拉欧拉欧拉欧拉于于于于17361736年解决了此年解决了此年解决了此年解决了此问题，从而使他成了图论问题，从而使他成了图论问题，从而使他成了图论问题，从而使他成了图论和拓扑学的创始人。和拓扑学的创始人。和拓扑学的创始人。和拓扑学的创始人。2024/1/202024/1/20离散数学离散数学1717欧拉通路欧拉通路欧拉通路欧拉通路(欧拉回路欧拉回路欧拉回路欧拉回路)：经过图中每条边一次且仅一经过图中每条边一次且仅一经过图中每条边一次且仅一经过图中每条边一次且仅一 次并且行遍每个顶点的通路次并且行遍每个顶点的通路次并且行遍每个顶点的通路次并且行遍每个顶点的通路(回路回路回路回路)，称为欧拉通路称为欧拉通路称为欧拉通路称为欧拉通路(欧拉回路欧拉回路欧拉回路欧拉回路)。10.2 10.2 欧拉图欧拉图欧拉图欧拉图 （一笔画问题一笔画问题一笔画问题一笔画问题）欧拉图：欧拉图：欧拉图：欧拉图：存在欧拉回路的图。存在欧拉回路的图。存在欧拉回路的图。存在欧拉回路的图。2024/1/202024/1/20离散数学离散数学1818(1)(1)无向图无向图无向图无向图G G具有具有具有具有欧拉通路欧拉通路欧拉通路欧拉通路当且仅当当且仅当当且仅当当且仅当G G是连通图且有是连通图且有是连通图且有是连通图且有零个或两个零个或两个零个或两个零个或两个奇数度顶点。奇数度顶点。奇数度顶点。奇数度顶点。欧拉图的判定定理欧拉图的判定定理欧拉图的判定定理欧拉图的判定定理：(2)(2)无向图无向图无向图无向图G G是是是是欧拉图欧拉图欧拉图欧拉图(具有欧拉回路具有欧拉回路具有欧拉回路具有欧拉回路)当且仅当当且仅当当且仅当当且仅当G G是是是是连通图且所有顶点的度数连通图且所有顶点的度数连通图且所有顶点的度数连通图且所有顶点的度数全为偶数全为偶数全为偶数全为偶数。？2024/1/202024/1/20离散数学离散数学1919欧拉图（续）欧拉图的判定定理：欧拉图的判定定理：欧拉图的判定定理：欧拉图的判定定理：(4)(4)有向图有向图有向图有向图D D是是是是欧拉图欧拉图欧拉图欧拉图(具有欧拉回路具有欧拉回路具有欧拉回路具有欧拉回路)当且仅当当且仅当当且仅当当且仅当D D是是是是连通图，且所有顶点的连通图，且所有顶点的连通图，且所有顶点的连通图，且所有顶点的入度等于出度入度等于出度入度等于出度入度等于出度。(3)(3)有向图有向图有向图有向图D D具有具有具有具有欧拉通路欧拉通路欧拉通路欧拉通路当且仅当当且仅当当且仅当当且仅当D D是连通图，且是连通图，且是连通图，且是连通图，且除了两个顶点外除了两个顶点外除了两个顶点外除了两个顶点外，其余顶点的，其余顶点的，其余顶点的，其余顶点的入度均等于出度入度均等于出度入度均等于出度入度均等于出度。这两个特殊的顶点中，一个顶点的入度比出度这两个特殊的顶点中，一个顶点的入度比出度这两个特殊的顶点中，一个顶点的入度比出度这两个特殊的顶点中，一个顶点的入度比出度大大大大1 1，另一个顶点的出度比入度大，另一个顶点的出度比入度大，另一个顶点的出度比入度大，另一个顶点的出度比入度大1 1 1 1。2024/1/202024/1/20离散数学离散数学2020例例例例2 2：判断下列图是否为欧拉图。：判断下列图是否为欧拉图。：判断下列图是否为欧拉图。：判断下列图是否为欧拉图。f fd db ba ae ec cg gh hi ij jd db ba ae ec cd db ba ae ec c是欧拉图是欧拉图是欧拉图是欧拉图不是欧拉图，不是欧拉图，不是欧拉图，不是欧拉图，但有欧拉通路但有欧拉通路但有欧拉通路但有欧拉通路是欧拉图是欧拉图是欧拉图是欧拉图2024/1/202024/1/20离散数学离散数学2121一笔画问题的条件：一个图可一笔画当且仅当一笔画问题的条件：一个图可一笔画当且仅当图中图中(1)所有点都是偶点；所有点都是偶点；或或(2)恰好有两个奇点。恰好有两个奇点。2024/1/202024/1/20离散数学离散数学2222哈密顿环游世界游戏哈密顿环游世界游戏哈密顿是哈密顿是18世纪英国的一位爵士世纪英国的一位爵士,他发明了一个环他发明了一个环游世界的游戏游世界的游戏,该游戏以该游戏以5英镑卖给了一个经销商英镑卖给了一个经销商.正十二面体正十二面体点表示世界点表示世界的的20个城市个城市边表示路线边表示路线是否存在是否存在从一城市从一城市出发经过出发经过每个城市每个城市恰好一次恰好一次有回到出有回到出发城市的发城市的旅游路线旅游路线?一个图如果存在这样的路线一个图如果存在这样的路线,称为称为哈密顿图哈密顿图.2024/1/202024/1/20离散数学离散数学232310.3 10.3 哈密尔顿图哈密尔顿图哈密尔顿通路哈密尔顿通路哈密尔顿通路哈密尔顿通路(哈密尔顿回路哈密尔顿回路哈密尔顿回路哈密尔顿回路)：经过图中每个顶点经过图中每个顶点经过图中每个顶点经过图中每个顶点 一次且仅一次的通路一次且仅一次的通路一次且仅一次的通路一次且仅一次的通路(回路回路回路回路)，称为哈密尔顿通路称为哈密尔顿通路称为哈密尔顿通路称为哈密尔顿通路(哈密尔顿回路哈密尔顿回路哈密尔顿回路哈密尔顿回路)。哈密尔顿图：哈密尔顿图：哈密尔顿图：哈密尔顿图：存在哈密尔顿回路的图。存在哈密尔顿回路的图。存在哈密尔顿回路的图。存在哈密尔顿回路的图。d db ba ae ec cd db ba ae ec cd db ba ae ec cf f2024/1/202024/1/20离散数学离散数学2424哈密尔顿图（续）设无向图设无向图设无向图设无向图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 V11(删除删除删除删除V V1 1中各中各中各中各顶点及其关联的边顶点及其关联的边顶点及其关联的边顶点及其关联的边)后所得子图的连通分支数。后所得子图的连通分支数。后所得子图的连通分支数。后所得子图的连通分支数。2024/1/202024/1/20离散数学离散数学2525哈密尔顿图（续）例例例例3 3：判断下列图是否为哈密尔顿图。：判断下列图是否为哈密尔顿图。：判断下列图是否为哈密尔顿图。：判断下列图是否为哈密尔顿图。都不是都不是哈密尔顿图哈密尔顿图哈密尔顿图哈密尔顿图2024/1/202024/1/20离散数学离散数学2626设设设设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是哈密尔顿图。是哈密尔顿图。是哈密尔顿图。是哈密尔顿图。(1)若对若对 uv E(G)，d(u)+d(v)n-1，则，则G G中存在中存在中存在中存在哈哈密密尔顿通路。尔顿通路。尔顿通路。尔顿通路。(2)(2)(2)(2)若对若对 uv E(G)，d(u)+d(v)n，则，则G G是是是是哈密哈密尔尔尔尔顿图。顿图。顿图。顿图。2024/1/202024/1/20离散数学离散数学27272024/1/202024/1/20离散数学离散数学2828该条件不是必要条件，如下图：该条件不是必要条件，如下图：2024/1/202024/1/20离散数学离散数学2929n n(n n 3)3)阶有向完全图是哈密尔顿图。阶有向完全图是哈密尔顿图。阶有向完全图是哈密尔顿图。阶有向完全图是哈密尔顿图。哈密尔顿图（续）在在在在n n(n n 2)2)阶有向图阶有向图阶有向图阶有向图D=D=中，如果所有中，如果所有中，如果所有中，如果所有有向边均用无向边代替，所得无向图中含生有向边均用无向边代替，所得无向图中含生有向边均用无向边代替，所得无向图中含生有向边均用无向边代替，所得无向图中含生成子图成子图成子图成子图K Kn n，则有向图，则有向图，则有向图，则有向图D D中存在中存在中存在中存在哈密尔顿通路。哈密尔顿通路。哈密尔顿通路。哈密尔顿通路。2024/1/202024/1/20离散数学离散数学303010.4 10.4 平面图平面图平面图：平面图：平面图：平面图：图图图图G G若若若若能够以除顶点外没有边交叉的方式能够以除顶点外没有边交叉的方式能够以除顶点外没有边交叉的方式能够以除顶点外没有边交叉的方式 画在平面上，则称画在平面上，则称画在平面上，则称画在平面上，则称G G为平面图。为平面图。为平面图。为平面图。K K5 5K K3,33,3一、平面图的基本概念及性质画出的没有边交叉的图称为画出的没有边交叉的图称为画出的没有边交叉的图称为画出的没有边交叉的图称为G G的一个的一个的一个的一个平面嵌入平面嵌入平面嵌入平面嵌入。2024/1/202024/1/20离散数学离散数学3131面：面：面：面：设设设设G G是一个连通的平面图是一个连通的平面图是一个连通的平面图是一个连通的平面图(G G的某个平面嵌入的某个平面嵌入的某个平面嵌入的某个平面嵌入)，G G的边将的边将的边将的边将G G所在的平面划分成若干个所在的平面划分成若干个所在的平面划分成若干个所在的平面划分成若干个区域区域区域区域，每个区域称为的一个面。每个区域称为的一个面。每个区域称为的一个面。每个区域称为的一个面。其中面积无限的区域称为其中面积无限的区域称为其中面积无限的区域称为其中面积无限的区域称为无限面无限面无限面无限面(或外部面或外部面或外部面或外部面)，记，记，记，记R R0 0，面积有限的区域称为面积有限的区域称为面积有限的区域称为面积有限的区域称为有限面有限面有限面有限面(或内部面或内部面或内部面或内部面)。2024/1/202024/1/20离散数学离散数学3232包围每个面的所有边所构成的回路称为该面的包围每个面的所有边所构成的回路称为该面的包围每个面的所有边所构成的回路称为该面的包围每个面的所有边所构成的回路称为该面的边界边界边界边界。边界的长度称为该面的边界的长度称为该面的边界的长度称为该面的边界的长度称为该面的次数次数次数次数，R R的次数记为的次数记为的次数记为的次数记为degdeg(R R)。对于含对于含对于含对于含k k(k k 2 2)个连通分支的非连通的平面图，个连通分支的非连通的平面图，个连通分支的非连通的平面图，个连通分支的非连通的平面图，其无限面其无限面其无限面其无限面R R0 0的边界则由的边界则由的边界则由的边界则由k k个回路个回路个回路个回路围成。围成。围成。围成。2024/1/202024/1/20离散数学离散数学3333v 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)=72024/1/202024/1/20离散数学离散数学3434在一个平面图在一个平面图在一个平面图在一个平面图G G中，所有面的次数之和都中，所有面的次数之和都中，所有面的次数之和都中，所有面的次数之和都等于边数等于边数等于边数等于边数mm的的的的2 2倍。倍。倍。倍。即即即即 ，其中，其中，其中，其中r r为面数。为面数。为面数。为面数。2024/1/202024/1/20离散数学离散数学3535极大平面图：极大平面图：极大平面图：极大平面图：设设设设G G是一个简单平面图，如果在是一个简单平面图，如果在是一个简单平面图，如果在是一个简单平面图，如果在G G中中中中 任意不相邻的两个顶点之间再加一条边，任意不相邻的两个顶点之间再加一条边，任意不相邻的两个顶点之间再加一条边，任意不相邻的两个顶点之间再加一条边，所得图为非平面图，则称所得图为非平面图，则称所得图为非平面图，则称所得图为非平面图，则称G G为极大平面图。为极大平面图。为极大平面图。为极大平面图。一个极一个极大平面大平面图图非极大非极大平面图平面图结论：结论：若若G是一个是一个(p,q)极大平面图，则每个有限面是极大平面图，则每个有限面是一个三角形，且一个三角形，且q=3p-6。2024/1/202024/1/20离散数学离散数学3636极小非平面图：极小非平面图：极小非平面图：极小非平面图：若在非平面图若在非平面图若在非平面图若在非平面图G G中任意删除一条边，中任意删除一条边，中任意删除一条边，中任意删除一条边，所得图为平面图，则称所得图为平面图，则称所得图为平面图，则称所得图为平面图，则称G G为极小非平面图。为极小非平面图。为极小非平面图。为极小非平面图。两个极小非平面图两个极小非平面图2024/1/202024/1/20离散数学离散数学3737极大平面图的性质极大平面图的性质极大平面图的性质极大平面图的性质：(1)(1)极大平面图是连通的；极大平面图是连通的；极大平面图是连通的；极大平面图是连通的；(2)(2)任何任何任何任何n n(n n 3 3)阶极大平面图每个面的次数均为阶极大平面图每个面的次数均为阶极大平面图每个面的次数均为阶极大平面图每个面的次数均为3 3；(3)(3)任何任何任何任何n n(n n 4 4)阶极大平面图阶极大平面图阶极大平面图阶极大平面图G G均有均有均有均有 (G G)3 3。2024/1/202024/1/20离散数学离散数学3838设设设设G G是任意的连通的平面图，是任意的连通的平面图，是任意的连通的平面图，是任意的连通的平面图，则有则有则有则有V V E E+F F=2=2成立。成立。成立。成立。其中：其中：其中：其中：V V为顶点数，为顶点数，为顶点数，为顶点数，E E为边数，为边数，为边数，为边数，F F为面数。为面数。为面数。为面数。设设设设G G是任意的连通分支为是任意的连通分支为是任意的连通分支为是任意的连通分支为k k(k k 2 2)的平面图，的平面图，的平面图，的平面图，则有则有则有则有V V E E+F F=k k+1+1成立。成立。成立。成立。其中：其中：其中：其中：V V为顶点数，为顶点数，为顶点数，为顶点数，E E为边数，为边数，为边数，为边数，F F为面数。为面数。为面数。为面数。例例.已知一个连通的平面图有已知一个连通的平面图有10个点，个点，12个面，问该个面，问该平面图有多少条边？平面图有多少条边？E=V+F-2=10+12-2=202024/1/202024/1/20离散数学离散数学3939设设设设G G是连通的平面图，且每个面的次数是连通的平面图，且每个面的次数是连通的平面图，且每个面的次数是连通的平面图，且每个面的次数至少为至少为至少为至少为l l(l l 3 3)，则则则则 。设设设设G G是连通分支为是连通分支为是连通分支为是连通分支为p p(p p 2 2)的平面图，每个面的平面图，每个面的平面图，每个面的平面图，每个面的次数至少为的次数至少为的次数至少为的次数至少为l l(l l 3 3)，则则则则 。设设设设G G是简单平面图，则是简单平面图，则是简单平面图，则是简单平面图，则mm 3 3n n66。2024/1/202024/1/20离散数学离散数学4040初等收缩：初等收缩：初等收缩：初等收缩：图图图图G G中相邻顶点中相邻顶点中相邻顶点中相邻顶点u u,v v间的收缩，即删除间的收缩，即删除间的收缩，即删除间的收缩，即删除 边边边边(u u,v v),),以新的顶点以新的顶点以新的顶点以新的顶点w w取代取代取代取代u u,v v，使，使，使，使w w关关关关联联联联u u,v v的一切边的一切边的一切边的一切边(除除除除(u u,v v)外外外外)。二、平面图的判定同胚：同胚：同胚：同胚：如果两个图如果两个图如果两个图如果两个图G G1 1和和和和G G2 2同构，或经过反复插入同构，或经过反复插入同构，或经过反复插入同构，或经过反复插入 或消去或消去或消去或消去2 2度顶点后同构，则称度顶点后同构，则称度顶点后同构，则称度顶点后同构，则称G G1 1与与与与G G2 2同胚。同胚。同胚。同胚。u uv vw wu uv va ab bc cd de ef fb bc cd de ef fg ga ab bc cd da aw wd d2024/1/202024/1/20离散数学离散数学4141一个图是平面图当且仅当它不含与一个图是平面图当且仅当它不含与一个图是平面图当且仅当它不含与一个图是平面图当且仅当它不含与K K5 5同胚同胚同胚同胚子图，也不含与子图，也不含与子图，也不含与子图，也不含与K K3,33,3同胚子图。同胚子图。同胚子图。同胚子图。一个图是平面图当且仅当它没有可以收缩一个图是平面图当且仅当它没有可以收缩一个图是平面图当且仅当它没有可以收缩一个图是平面图当且仅当它没有可以收缩到到到到K K5 5的子图，也没有收缩到的子图，也没有收缩到的子图，也没有收缩到的子图，也没有收缩到K K3,33,3的子图。的子图。的子图。的子图。2024/1/202024/1/20离散数学离散数学4242本章小结：本章小结：1.二部图、欧拉图、哈密顿图、平面图的概念与二部图、欧拉图、哈密顿图、平面图的概念与判断判断2.平面图的欧拉公式平面图的欧拉公式2024/1/202024/1/20离散数学离散数学4343第十一章第十一章树树问题的背景问题的背景问题的背景问题的背景:某地要在城镇之间建公路网某地要在城镇之间建公路网某地要在城镇之间建公路网某地要在城镇之间建公路网,如图所如图所如图所如图所示示示示.应如何修建应如何修建应如何修建应如何修建,才能使各城镇之间能够连通才能使各城镇之间能够连通才能使各城镇之间能够连通才能使各城镇之间能够连通?7324345726412树的特征？树的特征？2024/1/202024/1/20离散数学离散数学4444树树:一个连通的无圈图称为树一个连通的无圈图称为树.树具有如下特性树具有如下特性:(相互等价相互等价)设设T是树是树,则则(1)T中任意两顶点间恰有一条路中任意两顶点间恰有一条路;(2)T中无圈中无圈,且且2024/1/202024/1/20离散数学离散数学4545最小树问题实际上就是在已知的线路图中最小树问题实际上就是在已知的线路图中寻找一棵树寻找一棵树,使树的总权最小使树的总权最小.方法一方法一:(避圈法避圈法)73243457264122024/1/202024/1/20离散数学离散数学4646方法二方法二:(破圈法破圈法)73243457264122024/1/202024/1/20离散数学离散数学4747Huffman树树1.问题问题：给字符系统设计编码，由于每一个字符出：给字符系统设计编码，由于每一个字符出现的频率（概率）不同，通常我们希望常用的字符现的频率（概率）不同，通常我们希望常用的字符的编码更短些，的编码更短些，问：如何设计最佳的编码问：如何设计最佳的编码？一个最佳的编码的标准：设一个最佳的编码的标准：设li 是第是第i个字符的编码的个字符的编码的长度（码长），长度（码长），pi 是第是第i个字符出现的频率，最佳的个字符出现的频率，最佳的标准是使码长的期望达到最小：标准是使码长的期望达到最小：2024/1/202024/1/20离散数学离散数学48482.编码编码与二元树与二元树编码编码二元树二元树最佳编码最佳编码最佳二元树最佳二元树（Huffman树树）码长码长叶子到树根的长度叶子到树根的长度设计最佳编码问题转化为找一最佳二元树，使得设计最佳编码问题转化为找一最佳二元树，使得2024/1/202024/1/20离散数学离散数学4949设设p1p2 pk1.设设T是带权是带权p1，p2，pk的最佳二元树，则的最佳二元树，则p1的码长的码长l1最大。最大。证：证：(1)若所有编码概率相等，则若所有编码概率相等，则l1就是最大的；就是最大的；(2)若不是所有的编码的概率都相等，且若不是所有的编码的概率都相等，且l1不是最大不是最大.不妨设不妨设p1 pt，且且l1lt，则如下改变码长分别为：，则如下改变码长分别为：只是只是l1与与lt交换交换2024/1/202024/1/20离散数学离散数学5050注意到注意到则则这与这与T为最佳二元树矛盾。为最佳二元树矛盾。综上所述，得到结论。综上所述，得到结论。2024/1/202024/1/20离散数学离散数学5151设设p1p2pk2.设设T是带权是带权p1，p2，pk的最佳二元树，则的最佳二元树，则p1必有兄弟。必有兄弟。否则，只要令改变为否则，只要令改变为p1的父亲带权的父亲带权p1，即可得到更小，即可得到更小的二元树，如下图：的二元树，如下图：p1p2p3p1p2p32024/1/202024/1/20离散数学离散数学5252设设p1p2pk3.设设T是带权是带权p1，p2，pk的最佳二元树，则的最佳二元树，则p1，p2是一对兄弟。不妨设是一对兄弟。不妨设p1p2p3，则交换，则交换p2，p3的码长，得到的二元树更小（证明类同上面）。的码长，得到的二元树更小（证明类同上面）。p1p2p4p3p1p3p4p22024/1/202024/1/20离散数学离散数学53534.图的两种变换图的两种变换p1p2p3p4p1+p2p3p4由权由权p1，p2，pk的最佳二元树得到权的最佳二元树得到权p1+p2p3，pk的二元树的二元树2024/1/202024/1/20离散数学离散数学5454p1p2p3p4p1+p2p3p4由权由权p1p2，p3，pk的最佳二元树得到权的最佳二元树得到权p1，p2，pk的二元树的二元树2024/1/202024/1/20离散数学离散数学5555则则又由于又由于T是最佳二元树，则是最佳二元树，则故故因此：因此：(1)由权由权p1，p2，pk的最佳二元树得到权的最佳二元树得到权p1+p2p3，pk的二元树仍然是最佳的；的二元树仍然是最佳的；(2)由权由权p1p2，p3，pk的最佳二元树得到权的最佳二元树得到权p1，p2，pk的二元树仍然是最佳的。的二元树仍然是最佳的。2024/1/202024/1/20离散数学离散数学5656例：求带权例：求带权1,2,3,5的最佳二元树。的最佳二元树。步骤：（注意：按从小到大顺序排列权）步骤：（注意：按从小到大顺序排列权）3,5123512336512336112024/1/202024/1/20离散数学离散数学5757例：求带权例：求带权1,2,2,2,3,4,5,5,8的最佳二元树。的最佳二元树。步骤：（注意：按从小到大顺序排列权）步骤：（注意：按从小到大顺序排列权）2,2,3,4,5,5,81233,4,5,5,81232242024/1/202024/1/20离散数学离散数学58584,5,5,8224336125,5,833612448222024/1/202024/1/20离散数学离散数学5959833612448225510833612448225510142024/1/202024/1/20离散数学离散数学606044822551083361214182024/1/202024/1/20离散数学离散数学61614482255108336121418322024/1/202024/1/20离散数学离散数学6262例例.求下图的可达矩阵，判断它是否为强连通图？求下图的可达矩阵，判断它是否为强连通图？V1V4V2V3V5解：解：1.写出邻接矩阵写出邻接矩阵2024/1/202024/1/20离散数学离散数学63632.计算计算A2,A3,A4,A5.2024/1/202024/1/20离散数学离散数学64643.计算计算B=A+A2+A3+A4+A5,并求出并求出2024/1/202024/1/20离散数学离散数学6565例例.下列图哪些为欧拉图：下列图哪些为欧拉图：(1)(2)(3)(4)