(1.1)--离散数学离散数学.ppt
《(1.1)--离散数学离散数学.ppt》由会员分享,可在线阅读,更多相关《(1.1)--离散数学离散数学.ppt(65页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、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个宫女来个宫女来个宫女来个宫女来
2、自不同的家族,有的家族之间有历史恩怨,彼此不愿自不同的家族,有的家族之间有历史恩怨,彼此不愿自不同的家族,有的家族之间有历史恩怨,彼此不愿自不同的家族,有的家族之间有历史恩怨,彼此不愿意成婚。意成婚。意成婚。意成婚。亚瑟国王要求其一大臣将他们配对成婚,否则将亚瑟国王要求其一大臣将他们配对成婚,否则将亚瑟国王要求其一大臣将他们配对成婚,否则将亚瑟国王要求其一大臣将他们配对成婚,否则将把该大臣投入监狱。把该大臣投入监狱。把该大臣投入监狱。把该大臣投入监狱。大臣要求男女各站一边,彼此愿意成婚的举手,大臣要求男女各站一边,彼此愿意成婚的举手,大臣要求男女各站一边,彼此愿意成婚的举手,大臣要求男女各站一
3、边,彼此愿意成婚的举手,结果大臣认为无法配对成婚。结果大臣认为无法配对成婚。结果大臣认为无法配对成婚。结果大臣认为无法配对成婚。但国王不理解他的解释,他的命运?但国王不理解他的解释,他的命运?但国王不理解他的解释,他的命运?但国王不理解他的解释,他的命运?2024/1/202024/1/20离散数学离散数学4 4用图表示卫士与宫女愿意成婚的关系:用图表示卫士与宫女愿意成婚的关系:卫士卫士宫女宫女2024/1/202024/1/20离散数学离散数学5 51994年全国大学生数学建模竞赛年全国大学生数学建模竞赛B题:题:锁具装箱问题锁具装箱问题 某厂生产一种弹子锁具某厂生产一种弹子锁具,每个锁具的
4、钥匙有每个锁具的钥匙有 5 5 个槽个槽,每个槽的高度从每个槽的高度从 1,2,3,4,5,6 6 1,2,3,4,5,6 6 个数个数 (单位略单位略)中任取一数中任取一数.由于工艺及其它原因由于工艺及其它原因,制制造锁具时对造锁具时对 5 5 个槽的高度个槽的高度 还有两个限制还有两个限制:至少有至少有 3 3 个不同的数个不同的数;相邻两槽高度之差不能为相邻两槽高度之差不能为 5.5.满足满足以上条件制造以上条件制造 出来的所有互不相同的锁具称为一出来的所有互不相同的锁具称为一批批.出来的所有互不相同的锁具称为一批出来的所有互不相同的锁具称为一批.从顾客的利益出发从顾客的利益出发,自然希
5、望在每批锁具中自然希望在每批锁具中 一把钥匙开一把锁一把钥匙开一把锁.2024/1/202024/1/20离散数学离散数学6 6 但是在当前工但是在当前工 艺条件下艺条件下,对于同一批中两个对于同一批中两个锁具是否能够互开锁具是否能够互开,有以下试验结果有以下试验结果:若二者相对若二者相对应的应的 5 5个个 槽的高度中有槽的高度中有 4 4个相同个相同,另一个的高度另一个的高度差为差为 1,1,则可能互开则可能互开;在其它情形下在其它情形下,不可能互开不可能互开.原来原来,销售部门在一批锁具中随意地取每销售部门在一批锁具中随意地取每 6060个装一箱出售个装一箱出售.团体顾客往往购买团体顾客
6、往往购买 几箱到几十箱几箱到几十箱,他们抱怨购得的锁具会出现互相开的情形他们抱怨购得的锁具会出现互相开的情形.现聘聘请你为顾问现聘聘请你为顾问,回答并解回答并解 决以下问题决以下问题:2024/1/202024/1/20离散数学离散数学7 7 1)1)每一批锁具有多少个每一批锁具有多少个,装多少箱装多少箱.2)2)为销售部门提供一种方案为销售部门提供一种方案,包括如何装箱包括如何装箱(仍是仍是6060个锁具一箱个锁具一箱),),如何给箱子以标志如何给箱子以标志,出售出售时如何利用这些标志时如何利用这些标志,使团体顾客不再或减少抱使团体顾客不再或减少抱怨怨.3)3)采取你提出的方案采取你提出的方
7、案,团体顾客的购买量不团体顾客的购买量不超过多少箱超过多少箱,就可以保证一定不会出现互就可以保证一定不会出现互 4)4)按照原来的装箱办法按照原来的装箱办法,如何定量地衡量团如何定量地衡量团体顾客抱怨互开的程度体顾客抱怨互开的程度 (试对购买一、二试对购买一、二 箱者箱者给出具体结果给出具体结果).).2024/1/202024/1/20离散数学离散数学8 8可以证明:可以证明:(1)槽高的和为奇数槽高的和为奇数(或偶数或偶数)的锁之间不能互开;的锁之间不能互开;(2)一批锁具中,槽高的和为奇数与偶数的各占一批锁具中,槽高的和为奇数与偶数的各占一半。一半。2024/1/202024/1/20离
8、散数学离散数学9 9此问题涉及到此问题涉及到“互开互开”关系,用图表示这种互开关关系,用图表示这种互开关系:系:奇奇偶偶以上两个问题对应图有什么特点?以上两个问题对应图有什么特点?2024/1/202024/1/20离散数学离散数学1010二部图二部图(偶图偶图):若无向图若无向图G=的顶点集的顶点集V能能划分成两个子集划分成两个子集V1和和V2,使得,使得G中任何一条边的中任何一条边的 两个端点一个属于两个端点一个属于V1,另一个属于,另一个属于V2,则称,则称G为为二部图二部图(偶图偶图)。V1,V2称为互补顶点子集。称为互补顶点子集。10.1 10.1 二部图二部图完全二部图完全二部图(
9、完全偶图完全偶图):若若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/
10、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匹配:
11、匹配:设设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/2
12、02024/1/20离散数学离散数学1515最大匹配最大匹配:边数最多的匹配。:边数最多的匹配。匹配数匹配数:最大匹配中元素的个数。:最大匹配中元素的个数。亚瑟王的配婚问题,就是寻找完美匹配。亚瑟王的配婚问题,就是寻找完美匹配。锁具装箱问题要求匹配数。锁具装箱问题要求匹配数。有关图的完美匹配的存在性的判断:有关图的完美匹配的存在性的判断:(1)Hall定理(二部图);定理(二部图);(2)Tutte定理(一般情况)。定理(一般情况)。2024/1/202024/1/20离散数学离散数学1616图论中的第一个问题:图论中的第一个问题:哥尼斯堡七桥问题哥尼斯堡七桥问题ABCDABCD欧拉欧拉欧拉欧
13、拉于于于于17361736年解决了此年解决了此年解决了此年解决了此问题,从而使他成了图论问题,从而使他成了图论问题,从而使他成了图论问题,从而使他成了图论和拓扑学的创始人。和拓扑学的创始人。和拓扑学的创始人。和拓扑学的创始人。2024/1/202024/1/20离散数学离散数学1717欧拉通路欧拉通路欧拉通路欧拉通路(欧拉回路欧拉回路欧拉回路欧拉回路):经过图中每条边一次且仅一经过图中每条边一次且仅一经过图中每条边一次且仅一经过图中每条边一次且仅一 次并且行遍每个顶点的通路次并且行遍每个顶点的通路次并且行遍每个顶点的通路次并且行遍每个顶点的通路(回路回路回路回路),称为欧拉通路称为欧拉通路称为
14、欧拉通路称为欧拉通路(欧拉回路欧拉回路欧拉回路欧拉回路)。10.2 10.2 欧拉图欧拉图欧拉图欧拉图 (一笔画问题一笔画问题一笔画问题一笔画问题)欧拉图:欧拉图:欧拉图:欧拉图:存在欧拉回路的图。存在欧拉回路的图。存在欧拉回路的图。存在欧拉回路的图。2024/1/202024/1/20离散数学离散数学1818(1)(1)无向图无向图无向图无向图G G具有具有具有具有欧拉通路欧拉通路欧拉通路欧拉通路当且仅当当且仅当当且仅当当且仅当G G是连通图且有是连通图且有是连通图且有是连通图且有零个或两个零个或两个零个或两个零个或两个奇数度顶点。奇数度顶点。奇数度顶点。奇数度顶点。欧拉图的判定定理欧拉图的
15、判定定理欧拉图的判定定理欧拉图的判定定理:(2)(2)无向图无向图无向图无向图G G是是是是欧拉图欧拉图欧拉图欧拉图(具有欧拉回路具有欧拉回路具有欧拉回路具有欧拉回路)当且仅当当且仅当当且仅当当且仅当G G是是是是连通图且所有顶点的度数连通图且所有顶点的度数连通图且所有顶点的度数连通图且所有顶点的度数全为偶数全为偶数全为偶数全为偶数。?2024/1/202024/1/20离散数学离散数学1919欧拉图(续)欧拉图的判定定理:欧拉图的判定定理:欧拉图的判定定理:欧拉图的判定定理:(4)(4)有向图有向图有向图有向图D D是是是是欧拉图欧拉图欧拉图欧拉图(具有欧拉回路具有欧拉回路具有欧拉回路具有欧
16、拉回路)当且仅当当且仅当当且仅当当且仅当D D是是是是连通图,且所有顶点的连通图,且所有顶点的连通图,且所有顶点的连通图,且所有顶点的入度等于出度入度等于出度入度等于出度入度等于出度。(3)(3)有向图有向图有向图有向图D D具有具有具有具有欧拉通路欧拉通路欧拉通路欧拉通路当且仅当当且仅当当且仅当当且仅当D D是连通图,且是连通图,且是连通图,且是连通图,且除了两个顶点外除了两个顶点外除了两个顶点外除了两个顶点外,其余顶点的,其余顶点的,其余顶点的,其余顶点的入度均等于出度入度均等于出度入度均等于出度入度均等于出度。这两个特殊的顶点中,一个顶点的入度比出度这两个特殊的顶点中,一个顶点的入度比出
17、度这两个特殊的顶点中,一个顶点的入度比出度这两个特殊的顶点中,一个顶点的入度比出度大大大大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是欧拉图是欧拉图是欧拉图是欧拉图不是欧拉图,不是欧拉图,不是欧拉图,不是欧拉图,但有欧
18、拉通路但有欧拉通路但有欧拉通路但有欧拉通路是欧拉图是欧拉图是欧拉图是欧拉图2024/1/202024/1/20离散数学离散数学2121一笔画问题的条件:一个图可一笔画当且仅当一笔画问题的条件:一个图可一笔画当且仅当图中图中(1)所有点都是偶点;所有点都是偶点;或或(2)恰好有两个奇点。恰好有两个奇点。2024/1/202024/1/20离散数学离散数学2222哈密顿环游世界游戏哈密顿环游世界游戏哈密顿是哈密顿是18世纪英国的一位爵士世纪英国的一位爵士,他发明了一个环他发明了一个环游世界的游戏游世界的游戏,该游戏以该游戏以5英镑卖给了一个经销商英镑卖给了一个经销商.正十二面体正十二面体点表示世界
19、点表示世界的的20个城市个城市边表示路线边表示路线是否存在是否存在从一城市从一城市出发经过出发经过每个城市每个城市恰好一次恰好一次有回到出有回到出发城市的发城市的旅游路线旅游路线?一个图如果存在这样的路线一个图如果存在这样的路线,称为称为哈密顿图哈密顿图.2024/1/202024/1/20离散数学离散数学232310.3 10.3 哈密尔顿图哈密尔顿图哈密尔顿通路哈密尔顿通路哈密尔顿通路哈密尔顿通路(哈密尔顿回路哈密尔顿回路哈密尔顿回路哈密尔顿回路):经过图中每个顶点经过图中每个顶点经过图中每个顶点经过图中每个顶点 一次且仅一次的通路一次且仅一次的通路一次且仅一次的通路一次且仅一次的通路(回
20、路回路回路回路),称为哈密尔顿通路称为哈密尔顿通路称为哈密尔顿通路称为哈密尔顿通路(哈密尔顿回路哈密尔顿回路哈密尔顿回路哈密尔顿回路)。哈密尔顿图:哈密尔顿图:哈密尔顿图:哈密尔顿图:存在哈密尔顿回路的图。存在哈密尔顿回路的图。存在哈密尔顿回路的图。存在哈密尔顿回路的图。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的的的的任意非空子集,则任意非空子
21、集,则任意非空子集,则任意非空子集,则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:判断下列图是否为哈密尔顿图。:判断下列图是否为哈密尔顿图。:判断下列图是否为哈密尔顿图。:判断下列图是否
22、为哈密尔顿图。都不是都不是哈密尔顿图哈密尔顿图哈密尔顿图哈密尔顿图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中任何一对不相邻的顶点的度数之和中
23、任何一对不相邻的顶点的度数之和中任何一对不相邻的顶点的度数之和中任何一对不相邻的顶点的度数之和 都大于等于都大于等于都大于等于都大于等于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离散数学离
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 1.1 离散数学
限制150内