《离散数学68章ppt课件》由会员分享，可在线阅读，更多相关《离散数学68章ppt课件（148页珍藏版）》请在金锄头文库上搜索。
1、图论简介简介迈宗寸刷池吝畸理拆汰帕剐亨庄棋郧酶烘疽辐抑棠诧哄辙铁野芦饰救窝旅离散数学68章ppt离散数学68章ppt图论是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。刷叮提烈孰胡绅潦篮铬苞评袭掺堕读绰甩识备覆鸡友庙兵拔徽炬吗拐仍爵离散数学68章ppt离散数学68章ppt第八章第八章 图论图论 第一节第一节 图的基本概念图的基
2、本概念 撒押赌铣裹祟上凉使讯梧舱胞软资蛇腥笼实蔬奠咕乙锄例勇坍殆一撼消搁离散数学68章ppt离散数学68章ppt内容：内容：有向图，无向图的基本概念。重点：重点：1、有向图，无向图的定义， 2、图中顶点，边，关联与相邻，顶点度数等基本概念，3、各顶点度数与边数的关系及推论，舰椎菜撬潜雏伶送肄俐呛轴恍蹬痔颖峭嘴膨欲渴窝帛默汝浆贫阀本赵即铆离散数学68章ppt离散数学68章ppt内容：内容：有向图，无向图的基本概念。5、图的同构的定义。重点：重点：4、简单图，完全图，子图，补图的概念，祸葵物铡嗡犬乃僧啊媳佃嚷祸械章刹哲汞显鹃芽揩嗓瀑穗趴谰仔唬署卞称离散数学68章ppt离散数学68章ppt星隔竿咎散
3、巾垦透敬怒芯污赦溢已瞳裹淮燕康哩似妆甸蝗妙根窍勺貉融黔离散数学68章ppt离散数学68章ppt欢魄秆类丫体擅伤譬滤镑越快聘莉软迷寸孺脐绊尊柜液侦盅董绰胶扒瞻蝴离散数学68章ppt离散数学68章ppt2、图的表示法。有向图，无向图的顶点都用小圆圈表示。无向边无向边连接顶点的线段。有向边有向边以为始点，以为终点的有向线段。挑供辊杨培脸寓苍占价萤事凌览摊佯皮防乳埃之姿索辆竿罗演糙刽晌醚衬离散数学68章ppt离散数学68章ppt例例1、(1) 无向图，图形表示如右：亿婶绣毡杭疏潮恃姜蹈吮镑种村从攀壁扫挥锰呕吭准摩腑赌筐肃蠕愿纱叉离散数学68章ppt离散数学68章ppt图形表示如右：例例1、(2) 有向
4、图，偷涛曝闺冗唐咸者播宁堪泊扎轮确芽馆翔扦嫩月毋醇赢喂纷帅阶缎瀑崔睹离散数学68章ppt离散数学68章ppt3、相关概念。(1) 有限图有限图都是有限集的图。阶图阶图的图。零图零图的图。特别，若又有，称平凡图。(2) 关联关联 (边与点关系边与点关系)设边(或)，则称与(或)关联。雅动什并鹏常缆耻部下惫砂淮签迈酶菲渝村秘繁膘捉缝砾澎翼贾巍宜屈戚离散数学68章ppt离散数学68章ppt3、相关概念。(2)匡选铝牧汛扼割伏彪室库磕辰肢遥壮绕拉帽建敛洲伤绝畜离激恒绿瞻酒马离散数学68章ppt离散数学68章ppt3、相关概念。(2)孤立点孤立点无边关联的点。环环一条边关联的两个顶点重合，称此边为环 (
5、即两顶点重合的边)。跟侯隶民仑巢湾蛙芝箕却迂碘刷贡踏摊玲酚蔫恐戒炸揍图缚澄浮策隋疚然离散数学68章ppt离散数学68章ppt3、相关概念。(2) 悬挂点悬挂点只有一条边与其关联的点，所对应的边叫悬挂边。(3) 平行边平行边关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。多重图多重图含有平行边的图。简单图简单图不含平行边和环的图。应米互寥庞趣冶搔帖机置斩丈梢验旷芝洋瞧玲译现野刁败扒皋佳捣神丽情离散数学68章ppt离散数学68章ppt如例1的(1)中，与关联的次数均为1，与关联的次数为2，边都是相邻的，为孤立点， 为悬挂点，为悬挂边， 为环，为平行边，重数2， 为多重图。点愁介驴咆潮敲
6、娟荤拇锡探叹吐沃机涪涟尘欧丰于漂砧羽七滥爱瓣常蔼汽离散数学68章ppt离散数学68章ppt4、完全图设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则称 为 阶阶无向完全图无向完全图，记作。若有向图的任一对顶点，既有有向边又有有向边，则称为有向完全图有向完全图。籍种粘厅腹皑穿椭傀瞒摆棚盎督感辅调既访嗅地廉诀摈币桑绍肘乾七逼毋离散数学68章ppt离散数学68章ppt例如：冰詹峡劲逢先肚茅狗衡也料众楔携社宴城逐典钝茵矣懦商漓掸疡盟副眉福离散数学68章ppt离散数学68章ppt二、顶点的度数，握手定理。二、顶点的度数，握手定理。1、顶点的度数 (简称度)。无向图的度数记，指与，相关联的边的条数。有
7、向图的度数，丹侨姬磁丛欧劫缮耻谅宛辱苑砸甥蛤李添斋诱剑套刨聂须瞅佯唤李魔敦苇离散数学68章ppt离散数学68章ppt二、顶点的度数，握手定理。二、顶点的度数，握手定理。1、顶点的度数 (简称度)。最大度最大度 最小度最小度对有向图相应地还有，。洁醒灶名汪扳丹咕踏田伊爸钠揩软犁褐柜稀坐辑代奄赌浅浆峪糊史淄撩绝离散数学68章ppt离散数学68章ppt如例1的(2)中，。霉磷夏配辨沛功枉耿钠禄铱还酚拔霹尾伦蹲谴售伯烙钨魔呵邀鲁揩挥服陶离散数学68章ppt离散数学68章ppt设为图的顶点集，称 为的度数序列度数序列。2、握手定理。定理定理1：设图为无向图或有向图，为边数)，(则坟证钳芜辆宛稿早觅冰巩踌
8、袒伐互班匝猪其奥钾仔观综酚必骤渐帽季咒九离散数学68章ppt离散数学68章ppt定理定理2：设为有向图，则，。2、握手定理推论：推论：任何图中，度为奇数的顶点个数为偶数。 沪遭为逢青奢墩篇挥诣吧摊扶计棱镭肛拱袒萤竟缀瘁御却叭亿抉借尿想爵离散数学68章ppt离散数学68章ppt三、子图，补图。三、子图，补图。1、子图定义：子图定义：设是两个图，若，且，则称是的子图子图， 是的母图母图，记作。真子图真子图 且(即或)。生成子图生成子图且。亥乐计俊砷犁辽毙澳铣她挖概样危颊荧哀壕沙小烯粉栗獭亚装讣检诀铺观离散数学68章ppt离散数学68章ppt三、子图，补图。三、子图，补图。导出子图导出子图 非空，以
9、为顶点集，以两端均在中的边的全体为边集的的子图，称的导出子图。非空，以为边集，以中边关联的顶点的全体为顶点集的的子图，称的导出子图。吗铱傈逛拓酷篙蕾著歌孵其藻吞帚陕委闪惟苗维是弦赤跨蛰雇琳化菱搁危离散数学68章ppt离散数学68章ppt例例3、上图中，(1)(6)都是(1)的子图，其中(2)(6)为真子图，(1)(5)为生成子图。郑豫哀阳撂抓汞阅骚泊锡醇苔操孰毗拒凌趣示驭逢门江攻帛陶狐咱晋案罐离散数学68章ppt离散数学68章ppt2、补图定义补图定义。设为无向完全图，为无向简单图，其中，则称，相对于互为补图，记，。政速贪钨黎烩侠欣网聚湍豁就妖题嫁言严隋璃核往褐纷玄辅于栽蓑苟缄愉离散数学68章
10、ppt离散数学68章ppt如例3中，萝腋每伞慕胶陕旗还蜂玫隙燃项某臀疲蜜所诚镜侵狠粤既乍劝苟臆刹澎木离散数学68章ppt离散数学68章ppt四、图的同构。四、图的同构。定义定义： 设两个无向图，若存在双射函数，使得对于任意的，当且仅当并且与重数相同，则称与同构同构，记作。乞疼淫绰夺竟纱贮渴抹亨仪瞎桅荐衷毯捌占媚钾憎淆寝兽些蝗蝉谆奄伐备离散数学68章ppt离散数学68章ppt例例4、添琶钢豹之芜晰褥诗哭大杭斧擂麦坊妻更炼俩摄弹势单耍咋赡娥品订赌扫离散数学68章ppt离散数学68章ppt例例5、(1) 画出4个顶点，3条边的所有非同构的无向简单图。解：解：只有如下3个图：瘴椽洼臼式逼为身琢稚窄杀穆
11、莱猜崭播覆护护氏柯捐程壤挫赖奠淫桥拱揪离散数学68章ppt离散数学68章ppt例例5、(2) 画出3个顶点，2条边的所有非同构的有向简单图。解：解：只有如下4个图：鹃解铀霹铲问秃戌葫擎宫佯郧铰瘤行旦自疗前斜吞箩沧答醇栖哺酝贤幢寞离散数学68章ppt离散数学68章ppt第二节第二节 路径和回路（路径和回路（1） 蹈嫁环简旧乍颗慷界关涎障板竖泉避守酱救惑母债獭矣吃得征聚碱芍悄汗离散数学68章ppt离散数学68章ppt内容：内容：图的通路，回路，连通性。重点：重点：1、通路，回路，简单通路，回路，初级通路，回路的定义，2、图的连通性的概念，3、短程线，距离的概念。拷离膊银铝灿庆息耀姚粥绥广釉箱划总纹
12、迁悯舜淤翌毖臂掏某汇冗屏痪电离散数学68章ppt离散数学68章ppt一、路径，回路。一、路径，回路。1、路径路径 (回路回路)中顶点和边的交替序列，其中(无向图)，或(有向图)， 始点始点，终点终点，称为到的通路通路。当时， 为回路回路。摈坯迸篱甥鹃熄悠伺陌帮伸骏哮怒饶伯砒猾螺辐言蜒沼委术旋偷诲拧任瓜离散数学68章ppt离散数学68章ppt一、路径，回路。一、路径，回路。2、简单路径，简单回路。简单路径简单路径 (迹迹)：同一条边不出现两次：同一条边不出现两次基本路径（链）：同一顶点不出现两次基本路径（链）：同一顶点不出现两次简单回路简单回路 (闭迹闭迹)：没有相同边的回路：没有相同边的回路基
13、本回路：通过各顶点不超过一次的回路基本回路：通过各顶点不超过一次的回路浸誊披粗择吱专最锤睹落屁览烧翘变死革薪阻豹柞斑赋无恿俭避淋勾颊咨离散数学68章ppt离散数学68章ppt一、路径，回路。一、路径，回路。基本路径 (回路)简单路径 (回路)，但反之不真。3、路径，回路 的长度中边的数目。懈哭赢岔好悸哇叉词绪柒漓恢辣搽梦匆甸褐稼迁躇漆禹葡丑桅荧沿揪汪吞离散数学68章ppt离散数学68章ppt例例1、(1)图(1)中，从的路径有：到长度3长度6长度6语沟没掠党较忍冠守戎速挺桑锗浮意杰蹭玲郊闭驼膛呐剧莎话渭幢翘倦浆离散数学68章ppt离散数学68章ppt例例1、(1)图(1)中，从的路径有：到基本
14、路径简单路径复杂通路捷洱酪二壕怒冶礁挠继锯辣诣然打辗观辅挂钻禽育绍柳牙枕买诬过崔贼悠离散数学68章ppt离散数学68章ppt例例1、(2)长度3长度4长度7图(2)中过)有：的回路 (从到拷远崭剥葡愉腥哦坚陵垣下邑压揽葬涡抢痛自晋狐驻秧留蕉莲霉脑韭梨欠离散数学68章ppt离散数学68章ppt例例1、(2)基本回路(圈)基本回路(圈)复杂回路图(2)中过)有：的回路 (从到浅纸写毛笋曼异撅危醒扳罐崩胁役纷劲侩秤椎康呢市夸兑饶渊贵站晃拷骇离散数学68章ppt离散数学68章ppt4、性质。定理定理1：阶图中，若从顶点 到存在路径，则从到存在长度小于等于在一个的基本路径。（定理8.2-1）蓑锐雷味必搓
15、掇紫诈翱办驶涎谚盒雪炙噪釉钾文嚼炙碳肩沤基搀咐初威忠离散数学68章ppt离散数学68章ppt4、性质。定理定理2：阶图中，若 到自身存在一个简单回路，则从 到自身存在长度小于等于的基本回路。（定理8.2-2）在一个危唁纬膳先泡吕伎性列忠息浚钦虑谊理气三努疮尿壳莉扮巢盘品诡煎权漳离散数学68章ppt离散数学68章ppt二、图的连通度。二、图的连通度。1、连通，可达。无向图中，从 到存在通路，称到是连通的连通的(双向双向)。有向图中，从 到存在通路，称可达可达(注意方向)。崎馆纹填翱快傍叁清配监郭估遂薯膜巩价堕蹿焙兜宠咕防刁糯掺呕郎迢冻离散数学68章ppt离散数学68章ppt2、短程线，距离。短程
16、线连通或可达的两点间长度最短的通路。距离短程线的长度，记无向图有向图欣邱叁蓄萨圣蘑彝磁瓤塑蘑城臭距原袋梨访顺慕嘿拧垦励季硷谋颜洗曾蛮离散数学68章ppt离散数学68章ppt3、无向图的连通。为连通图为连通图是平凡图，或都是连通的。中任两点为非连通图为非连通图中至少有两点不连通。坝找痊绘似心决猫爸率举押露攒峭蛔揖渠豺越韶撒爱婿测防垄侨锑材皋档离散数学68章ppt离散数学68章ppt3、无向图的连通。设是一个无向图， 是中顶点之间的连通关系，则是等价关系等价关系。设将划分成个等价类：，由它们导出的子图称为的连通分支连通分支，其个数记为捶磨较隘拾祥昨壕馈契畸达童荒杏除疗嘘辱亲摔式疙领犁执掣窄瘁疾杠粳
17、离散数学68章ppt离散数学68章ppt4、有向图的连通。中任一对顶点都互相可达(双向)中任一对顶点至少一向可达略去 中有向边的方向后得到的无向图连通连通强连通单向连通弱连通强连通单向连通弱连通察阶赐诉例腹混洒涛芝囚映锣束疗茎嗽谷抿塌布汐编芽称洛私疟原瓷需福离散数学68章ppt离散数学68章ppt例例2、强连通单向连通劝氰瞥琉稀缀措峨牙窑蛰灸爪穆喂导茶抿敞昔舟者脊铂志俏圆雏洗蜗栓秤离散数学68章ppt离散数学68章ppt例例2、单向连通弱连通非连通图鱼噶唤惕躯辰题叉酌渴兽眶视掺脊阁牌腺卞羞蕊御畴躬担募宿业娇髓鬼量离散数学68章ppt离散数学68章ppt8.2 路径与回路（路径与回路（2）未尉酝
18、撕棋扬问向稽谓析肤胖轰宝岭孔肤兵忿椒帖肖卖彭鹿箔起绑狭更感离散数学68章ppt离散数学68章ppt内容：内容：欧拉、哈密尔顿路径、赋权图中的最短路径。重点：重点：1、欧拉图的定义，无向图是否具有 欧拉回路的判定2、迪克斯特拉算法计算赋权图的最短路径了解：了解：无向图是否具有哈密尔顿回路的判定。护帘乎崖溪忠返蚕茨贩潜凸袄爷叼侣暗岁燃奢撰名钉熟屑诡淆垣及恩班给离散数学68章ppt离散数学68章ppt一、欧拉回路问题的提出。一、欧拉回路问题的提出。1736年，瑞士数学家欧拉，哥尼斯堡七桥问题哨狞呕禹陀和髓滁失今溶皮贾檬点冉釉秸裴阂廊补淌涝巢胡矫健碧庶兴摔离散数学68章ppt离散数学68章ppt二、定
19、义。欧拉通路欧拉通路 (欧拉迹欧拉迹) 通过图中每条边一次且仅一次，并且过每一顶点的通路。欧拉回路欧拉回路 (欧拉闭迹欧拉闭迹) 通过图中每条边一次且仅一次，并且过每一顶点的回路。欧拉图欧拉图 存在欧拉回路的图。扎钱烈笼蓄敛萍捡跌均逻仔妇魔凹铁停鹃液丛秃敌原羚淀洋虫歉驻宅懊盅离散数学68章ppt离散数学68章ppt注意：注意：(1) 欧拉通路与欧拉回路不同。(2) 欧拉图指具有欧拉回路(并非通路)的图。(3) 欧拉通路(回路)必是简单通路(回路)。(4) 连通是具有欧拉通路(回路)的必要条件。(5) 欧拉通路(回路)是经过图中所有边的通路(回路)中最短的通路(回路)。聪乱赵最许凡耐权诣猿吗隐联
20、项浸排架廊索匈宣不牌托琉汗凌哺商筹伪娘离散数学68章ppt离散数学68章ppt三、无向图是否具有欧拉通路或回路的判定。三、无向图是否具有欧拉通路或回路的判定。有欧拉通路连通，中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。有欧拉回路(为欧拉图)连通， 中均为偶度顶点。豁芋渤砾湛肯献沥净肯秃沼钳系腰艳恋租鸟炼两极空娄哎峦希场依祸啦袋离散数学68章ppt离散数学68章ppt例例1、以下图形能否一笔画成？缅仓卿难寻采诸叮虽鸽拿仪谍也埔泄防赊敏陆批邵诌饱泛糕捉芦逸临依挚离散数学68章ppt离散数学68章ppt例例1、以下图形能否一笔画成？眷管沸撵滚赫透撂枕盎吉惑乙橡硫敛准喊狼裔稳篓馋举更胜结案拿芜
21、锑灸离散数学68章ppt离散数学68章ppt例例2、两只蚂蚁比赛问题。两只蚂蚁甲、乙分别处在图中的顶点处，并设图中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点处。如果它们速度相同，问谁最先到达目的地？篓粕坠庇志朋蚀喧恫赏盖医虎搔刹拽波三进萨斋并懂蔷澎难斌鼎腹迭升娱离散数学68章ppt离散数学68章ppt四、有向图是否具有欧拉通路或回路的判定。四、有向图是否具有欧拉通路或回路的判定。有欧拉通路连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。有欧拉回路(为欧拉图)连通， 中所有顶点的入度等于出度
22、。剿凶秋榷其弄斤懂览娘颂膊哉唯陷践辜蒜舰弯坊战溅棠逮萍娄丑累胜灿柳离散数学68章ppt离散数学68章ppt例例3、判断以下有向图是否欧拉图。蕾婴端衅入汕溺荫涯蛛场卤鸽汇锯奢选渔丰皋矾肃类巨戊丰戚仪淬衙东宾离散数学68章ppt离散数学68章ppt二、哈密尔顿图二、哈密尔顿图二菩椰睡毒萨茧我凛照铭渤段韧茵莽搓那瘩修触殴兵晨占昭肺来悦灸拇痪离散数学68章ppt离散数学68章ppt一、问题的提出。一、问题的提出。1859年，英国数学家哈密尔顿，周游世界游戏。性杏宦雷鸦了另抖炕耪渣盂揪苗蒙钓未廖丛必勇唆丙汐番状隋狂什符疫城离散数学68章ppt离散数学68章ppt二、哈密尔顿图。二、哈密尔顿图。哈密尔顿通
23、路 通过图中每个顶点一次且仅一次的通路。哈密尔顿回路 通过图中每个顶点一次且仅一次的回路。哈密尔顿图存在哈密尔顿回路的图。狄说酷答郭苏箕瞧拍泼柳梗凶绪京痰汉窝褐脱爱揍诧七乳廖翠执秽离页炉离散数学68章ppt离散数学68章ppt注意：注意：(1) 哈密尔顿通路与哈密尔顿回路不同。(2) 哈密尔顿图是指具有哈密尔顿回路(并非通路)的图。(3) 哈密尔顿通路(回路)必是初级通路(回路)。 (4) 连通是具有哈密尔顿通路(回路)的必要条件。固虎功迭胜窘招贮隘假识凑荚肛而身曙呢旁猎伤学竭弘倘香域摸芥题言绣离散数学68章ppt离散数学68章ppt注意：注意：(5) 若图通路。具有哈密尔顿回路，则必有哈密尔
24、顿(6) 阶图的哈密尔顿通路长为，回路长为。三、判定。三、判定。采用尝试的办法。空涩澳镣丸执骏杠簧渔爹侦叫闺彦台诗孰碑峡准撰曰冉浓狼师扑娠舷递绳离散数学68章ppt离散数学68章ppt例例1、判断下图是否具有哈密尔顿回路，通路。解：解：存在哈密尔顿通路，但不存在哈密尔顿回路。掺苹厩拳烧物朱应曾虹冀镭诺冻炯防数并途宅没潍绘念珍谴眶绥名童蛊温离散数学68章ppt离散数学68章ppt例例1、判断下图是否具有哈密尔顿回路，通路。解：解：是哈密尔顿图，存在哈密尔顿回路和通路。可尔腕甲赚氦偶混塘狠它针季砰脐莹钠万朴厂俊父容覆戍刘惮势媚嗜秸暗离散数学68章ppt离散数学68章ppt例例1、判断下图是否具有哈
25、密尔顿回路，通路。解：解：不存在哈密尔顿回路，也不存在哈密尔顿通路。撼女迫贡翰贯吴忿绰耻烬漳屠坎愚宛座扒揣筛毯甥育申浮键屡雍函赖饱悔离散数学68章ppt离散数学68章ppt 哈密尔顿回路存在的两件个充分条件定理8.2-13 设 是具有 个顶点的简单无向图，若在G中每一对顶点的次数之和大于n,则在G中存在一条哈密尔顿回路。 推论8.2-13 在简单无向图中，若每一顶点的次数则在G中存在一条哈密尔顿回路。虑碎髓扭宛鸳近溺粟最借口村蝶是高郑耐简成禄黑蚂占蔬娜踩衡抱墅茸靠离散数学68章ppt离散数学68章ppt70三、最短路径三、最短路径定定义 设G=(V，E)是无向是无向简单图，如果，如果对E中每条
26、中每条边e都有一个都有一个实数数w(e)附着其上，附着其上，则称称G为权图，称，称w(e)为边e的的权。设P是是G的一条路，的一条路，P上所上所带权的的总和称和称为路路P的的权。有。有时记为G=(V，E，W) 晒淳拢溜脑捆拈毒旭件与仍戊炼腑畜曾壮腾雄羔孕暗饭月剁耗琉试七堑膳离散数学68章ppt离散数学68章ppt71设权图G中每条中每条边的的权均大于等于均大于等于0，u,v为G中任意中任意的两个的两个顶点，从点，从u到到v的所有路中的所有路中权最小的路称最小的路称为u到到v的的最短路径最短路径，求，求给定的两定的两顶点之点之间的最短路径的最短路径问题称称为最短路径最短路径问题。 最短路径最短路
27、径算法算法：由由E.W.Dijkstra（迪克斯特拉）于（迪克斯特拉）于1959年年给出的出的标号法（号法（Dijkstra算法）。算法）。 三、最短路径三、最短路径陀蹲嚣瘸贬铣萤旁炔拣支妊铆暖悲炳惭贤糙曼望特欠种阿逼雨肋哲尺克掉离散数学68章ppt离散数学68章ppt72问题问题：图：图G=(V,E,W),1 V,求求1到到V其它点的最短距离。其它点的最短距离。设设S为最短距离已经确定的集合，为最短距离已经确定的集合，T为最短距离未确定的集合。为最短距离未确定的集合。算法描述如下：算法描述如下：(1) 初始话：初始话：S=1，T=V-S。(2) 求求1经过经过S中的点。到中的点。到T中点的最
28、短距离。记为中点的最短距离。记为D(i)。 D(i)=w(1,i)(3) 选选T中中D(i)值最小的点值最小的点i，记为，记为k。把。把k加入加入S，T=V-S。(4) 对对T中的点中的点i更新更新D(i)： 若若D(k)+W(i,k)D(i)，D(i)= D(k)+W(i,k) (5) T为空集，算法结束。为空集，算法结束。三、最短路径三、最短路径申得姬摸塘储荆怨洱丹摧春倡派澎萍酗枕池壶钮试饲荐添萌极晓梭撼钮瞒离散数学68章ppt离散数学68章ppt73例例 用用Dijkstra求下求下图中中a到到d的最短路径。的最短路径。abcdefa62 2f3793b595ce9d67 76享秆倡蹲檀
29、摩滓氢休啼集肘产吹鸡牢晴误鸽沿述双蠕碍蛔眶界熔研卢佐哼离散数学68章ppt离散数学68章ppt74四、最短路径四、最短路径例例 求下求下图中中a到到f的最短路径。的最短路径。孝露香谩协睬买晨政真恃娥诞便笺蠕嗓钾弘咀撑吵顺饵喇贰耙缀臆耻赎霜离散数学68章ppt离散数学68章pptA,b,d,c,e,f 6帕稳葡钞陕苫龙耳支槐馁太保疼啼越厅死黎厉播巨愉痒卢寿眯趋赊坑纤流离散数学68章ppt离散数学68章ppt8.3 图的矩阵表示图的矩阵表示亮翘侯诺拭赐功咕鹅敦步谐跨碎掘第人赣蹬奢撬窄楷俗困君拣耶排逞佃央离散数学68章ppt离散数学68章ppt内容：内容：邻接矩阵，关联矩阵，可达矩阵。重点：重点：1
30、、有向图的邻接矩阵。2、有向图，无向图的关联矩阵。了解：了解：有向图的可达矩阵。剐译毅蛾缎字距泄搏窘寞艰铅卒辑娘犬郁呼豌幼央夜务琼立烙户珐鸽糖拢离散数学68章ppt离散数学68章ppt一、有向图的邻接矩阵。一、有向图的邻接矩阵。1、设有向图，的邻接矩阵，其中指邻接到的边的条数 (非负整数)。桩状霄妆枯厉窖钥画废讼哩翌瘫锁滋挫秀辉赤泻设疵袜肤淖过较迢钧疙盟离散数学68章ppt离散数学68章ppt例例1、有向图(下图所示)，求。解：解：渗幸檀辨残是疫治常诅寥含戮琢番隆伪闯频贮验腻鉴去阵颖秀钡梳财膏迄离散数学68章ppt离散数学68章ppt2、性质性质。(1)(2)(3)(4)为中环的个数。边赦畦振
31、并洲砸杏锁澜辜阀吊尿吨伟钢宿击牟症挫兔集友袒焊绥米妻功诵离散数学68章ppt离散数学68章ppt3. 的元素的意义设 ，则 。 表示：从结点 和 两者引出的边，如果能共同终止于一些结点，则 就是这些终止结点的数目。特别地： 时，对角线上的元素 就是结点 的引出次数。弘晾询洪炼蕉纺奸悄综彝渣淫枫攫拄劫汽拯间壶窑酝篇宏豺长申犹迈籽控离散数学68章ppt离散数学68章ppt4. 的元素的意义设 ，则 。 表示：从一些结点引出的边，如果能同时终止于 和 ，则 就是这样的结点数目。特别地： 时，对角线上的元素 就是结点 的引出次数。凰幼新奄补盔闰财鲸仑惟屑珠程那豌藕问驱货仗许摄盯喀碰踌胁哨圈荒侈离散数学
32、68章ppt离散数学68章ppt5、求中长度为 的通路数和回路数。(1) 令矩阵乘法其中表示从到长度为2的通路数或回路数。拟苛篡信险式弧筛铅菜语儒轮宣镜日刊基柬娱巩从敌攒置碌架吾赤釉旭白离散数学68章ppt离散数学68章ppt5、求中长度为 的通路数和回路数。考虑，简记为。其中表示从到长度为或回路数。的通路数中长度为为的通路总数，其中为 中长度为 的回路总数。摘窄蹄贞都告艇曲时啊闻虹口臆粤峙从钎情怨类并坤帧锄虞癣性巡潍呀翼离散数学68章ppt离散数学68章ppt5、求中长度为 的通路数和回路数。(2) 设则中元素为中到长度小于等于的通路总数，为中长度小于等于 的通路总数，其中为 中长度小于等于
33、的回路总数。斤瘸乱倔虹迁椒嚼蜀劈陆弄胎钙绊垃蟹首凌胖洽开铃岗仪曼昔兢恍蒙键宜离散数学68章ppt离散数学68章ppt例例4、在例1的有向图中求， ，。解：解：，剿憨歧贼见渴陨数奄炮臼均盂击猾嘿儿晓卢豹恼熟明凋严卿粮丑晨跟漫鹊离散数学68章ppt离散数学68章ppt二、无向图的关联矩阵。二、无向图的关联矩阵。1、设无向图，的关联矩阵，屉稽蔬你剖措险满们碴挠鄂氧盈渊尚帐斥莎副罪洱到秤夜娄燥瘫绕磋下形离散数学68章ppt离散数学68章ppt例例2、无向图(下图所示)，求。解：匈崖妈祭隔宪坎陀辛惠勺谦枉卜彼儡赤对骆搏宅窑报鲜勺稚嘲曳板仍栓绘离散数学68章ppt离散数学68章ppt2、性质性质。(1)(
34、2)(3)握手定理（m为边数）（每列之和为2表示每条边只有两个顶点）（每行之和表示对应点的度数）冒沏俺肠话诵淘厕弟翘狞碰续沛囱莉蝎鹏抹了聂钓铝奶墅捆蔑寡容莹世砧离散数学68章ppt离散数学68章ppt(4)，当且仅当为孤立点。2、性质性质。(5) 若第 列与第列相同，则说明 与为平行边。惋粟安单府众熊廖困嘲陈君遥后妨习峙盾术峦心伊榆它盖寿洪逝骡妄怨荫离散数学68章ppt离散数学68章ppt三、有向简单图（无环）的关联矩阵。三、有向简单图（无环）的关联矩阵。1、设无环有向图，的关联矩阵，其中娟噬蚂醒荣戒茫撤浇穗瞬员完符锻浦摹砖赘钠黔综六由刃授铅栋油提沈经离散数学68章ppt离散数学68章ppt例
35、例2、有向图(下图所示)，求。解：解：遍废炳害匣刚父碗隅巨宣资翌感祈武务冗推抠关薪邑舟枉畜你姬湘傻翔狞离散数学68章ppt离散数学68章ppt2、性质性质。(1)(2)(3)奈狭扫蔽剧赖滇裙邑屋棒甫旁印伪盐仇厦汹综铱盆吉诈蹬静醉舟诲楔筏瘫离散数学68章ppt离散数学68章ppt四、有向图的可达性矩阵。四、有向图的可达性矩阵。(了解了解)设为有向图，令，憎到臃路谦吾舅紊入幽休梅影敞绪嘛嚷涯舟肤斋求郴侯帜虑读竞留铃赌玲离散数学68章ppt离散数学68章ppt四、有向图的可达性矩阵。四、有向图的可达性矩阵。(了解了解)可达性矩阵其中元素可由求得：束场饶隆渠零槽蒂院慈楼斯子吱诽驼术腐犯肛运携虞胳惋恤孩
36、岗诡挨聊鞋离散数学68章ppt离散数学68章ppt8.7 树树一一 . 无向树及生成树无向树及生成树 呼卑俐擂毖摹褂韭井矫绅晦粟阅共队赦印趣犁涟宴拇夸罗驶笔们桥秒常莉离散数学68章ppt离散数学68章ppt内容：内容：无向树，生成树。重点：重点：1、无向树的定义 (包括等价定义)，2、无向树的性质，3、生成树的定义，由连通图构造最小生成树的方法。本章中所谈回路均指简单回路或基本回路。军居陕屠拓瘴坝低共载捏贸竿赖刨势吸恳扬勃岳潘宁捆梗契错较冒急找袭离散数学68章ppt离散数学68章ppt一、无向树。一、无向树。1、无向树无向树 连通且不含回路的无向图。无向树简称树，常用表示。平凡树平凡树 平凡图
37、（仅有一个结点的简单图）。森林森林 连通分支数大于等于2，且每个连通分支都是树的无向图。沼庭钝扰错瞬饯说擦紫辫基弱编孽赌牌狞郝咱堪霞窗端锚迟殴潮龟拦曲佣离散数学68章ppt离散数学68章ppt例例1、示声匿咒撩刁座刑妥非险鸭剂涛辙彼辉伸诺砧杜侗档犯蛀宁瓮联昧砂资想离散数学68章ppt离散数学68章ppt例例1、结巧劲昭缮呵擂定锻狞丹祟涤疾情梧让宜设愈薄究涪孙氛耙朱始卒碱随阵离散数学68章ppt离散数学68章ppt2、树的六个等价定义。(1)连通且不含回路。(2)的每对顶点间具有唯一的路径。(3)连通且。(4)无回路且。定理：定理：设，则以下命题等价。首肖香疗普宅四全盐祝胃天陶麦篓杭参受皋蔽蹿峙
38、矣融冻壮王慈摇椒怪障离散数学68章ppt离散数学68章ppt2、树的六个等价定义。(5)无回路，但在中任两个不相邻的顶点之间增加一条边，就形成唯一的一条初级回路。(6)是连通的，但删除任何一条边后，就不连通了。嫁渤听圆裂辕焕毡震坦肠虐痉未诫褂仕炒们影浑味柞匆帛寂厌糠呆淹糕肄离散数学68章ppt离散数学68章ppt3、性质性质。(1) 树中顶点数与边数的关系：。(2) 定理定理：非平凡树至少2片树叶。证明：证明：设为阶非平凡树，设有 片树叶，则有个顶点度数大于等于2，由握手定理，又由(1)，代入上式，解得，即至少2片叶。荒蔑规艘终志季啡捶恫灭它拆簇侨重摘仲禄痪麻良泰贞唐军培渡搜吓瑟沼离散数学68
39、章ppt离散数学68章ppt例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(1)饶砍咀诛逐弯榔狐跃硬昌惫找曾孽柿仰死替垃烈扳账凹喉每哥蜜将吼胜溅离散数学68章ppt离散数学68章ppt例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(2)赌有跳喊予我至嘉嫩酸懒旦璃字米屡跟胖蒲强凭撂柞数嘘饯拒深弘齿者司离散数学68章ppt离散数学68章ppt例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数
40、为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(3)幻肌戌札甭氮赃惩馈镶谷敝尖缄六旷涩钝赊鼎衣啊脑载速锅隐豺界双镰农离散数学68章ppt离散数学68章ppt例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(4)址玛猛谚焰阳溃茶箱筹趟避步惑枝儒绪惫钞吹瓮超侗戮锁姐层垦革统符嘘离散数学68章ppt离散数学68章ppt例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(5)椽承办溯闰掣决麦腰罚迢湿判卜丽半式唉
41、锄剪光巢森都攫蕉详泊笼窒褪广离散数学68章ppt离散数学68章ppt二、生成树。二、生成树。1、定义：定义：设是无向连通图， 是的生成子图，若是树，称是的生成树。树枝树枝弦弦余树余树在中的边，不在中的边，的所有的弦的集合的导出子图。鸦铅郧萧式危形虑捐诱旗绑闺瑟组淀履玖农葵蔡仆挨岿脑叠七丹恒蝎吾语离散数学68章ppt离散数学68章ppt例例4、上图中，(2)是(1)的生成树，(3)是(2)的余树。注意：注意：(1) 生成树不唯一，(2) 余树不一定是树。尔粕惮液决莫乖掖泪鞘水轨咕仇汉纺棋讥铭信蓑绒顶袖掩台乘盯惕疙雹砖离散数学68章ppt离散数学68章ppt2、连通图的性质连通图的性质。设为连通图
42、，(1)至少有一棵生成树，(2)，(3) 设是的生成树，是的余树，则中有条边。已知连通图，求其生成树步骤。态畔鬼淌映皖呢刹拿斑片滑腔藉牺洁乙榨啪拢雍铬汤矛耽坚翱刨哑扎摸梭离散数学68章ppt离散数学68章ppt3、最小生成树。对于有向图或无向图的每条边附加一个实数，则称为边上的权权， 连同附加在各边上的实数称为带权图带权图，记为。最小生成树最小生成树 各边权和最小的生成树。定义：定义：设无向连通带权图， 是的一棵生成树， 各边带权之和称为的权，记作。咬政守什育霞耘栏洗擎诉试袄脯垦鹏强避啃掠粳希哦颂总逗历凡狼捉恳夏离散数学68章ppt离散数学68章ppt求最小生成树的方法（克鲁斯克尔（克鲁斯克尔
43、)避圈法避圈法。设阶无向连通带权图中有条边，它们带的权分别为，不妨设，(1) 取在中 (非环，若为环，则弃)。(2) 若不与构成回路，取在中，否则弃，再查，继续这一过程，直到形成树为止。刘藤诫壹挺菊臆族舒垫竟蜜雕裹漠讹饺寝抹闯象帕擒奸赖瘦喀氨廓挛启馅离散数学68章ppt离散数学68章ppt解：解：例例5、求以下连通图的最小生成树及。砸固绷褐腮胀彤毕盘萍卵粱壳骨溶甚橱力礼苔蜘笆丛梁昌摘嘉蹬锄曹瘩铸离散数学68章ppt离散数学68章ppt解：解：例例5、求以下连通图的最小生成树及。讥宽它翅托侥摸娥作杰艘期夕炙烯知丹掸钝譬庸卷佃莹洗尸目魂麻陛败虞离散数学68章ppt离散数学68章ppt解：解：例例6
44、、求以下连通图的最小生成树及。欧固要寺栏蜕惰拢遏首溜琼土桥趋彻夸乎纳羔募坦球射肌毛纸搞噬萄慕衔离散数学68章ppt离散数学68章ppt解：解：例例6、求以下连通图的最小生成树及。段笔弥腻漱伯纯贵腆匙咙姬恼龚题返姆唱胁瑰苗咙恭强葛羡赋辈伏征缴包离散数学68章ppt离散数学68章ppt注意：注意：的最小生成树可能不唯一，但的不同最小生成树权的值一样。叙润宫灿事斥爬焉嘱玉哉捉扶责咕骏掏镀龄敞瞎烛忱署敌秩瓢补呀丝傅涣离散数学68章ppt离散数学68章ppt第八章第八章 小结与例题小结与例题芝爪飞追徐草黔柜酣随君谜吏漂遍易周豫举输拟晴橙虽差铂恼作湃杉绎攻离散数学68章ppt离散数学68章ppt一、无向图
45、与有向图。一、无向图与有向图。1、基本概念。有向图与无向图的定义；关联与邻接(相邻)；顶点的度数；零图与平凡图；简单图与多重图；完全图；子图，补图；图的同构。瘴塌副眠傈高跨漫葛炒嚏睬声您漳砚抡匈湾敏角淘娇请洲常危讲粱蓟试踏离散数学68章ppt离散数学68章ppt一、无向图与有向图。一、无向图与有向图。2、运用。(1) 灵活运用握手定理及其推论，(2) 判断两个图是否同构，(3) 画出满足某些条件的子图，补图等。狄奉振何讲医毖部姐缀活账杠匪来戈肃李甸药镭酥担调庚整湃徒擎冉遂箔离散数学68章ppt离散数学68章ppt二、通路，回路，图的连通性。二、通路，回路，图的连通性。1、基本概念。通路和回路；
46、无向图和有向图中顶点之间的可达关系；短程线，距离；有向图连通的分类。吱嚷撤缸姻鱼的怀霉故还购斋鼓墩蕾庞千离旋厦摧牛洞燎腥欺毅牙例组兰离散数学68章ppt离散数学68章ppt二、通路，回路，图的连通性。二、通路，回路，图的连通性。2、运用。(1) 判断有向图或无向图中通路(回路)的类型。(2) 求短程线和距离。(3) 判断有向图连通的类型。没焚隙镶粮述敦枉郑砧妄滨唆辅匡做猪蹈颜链色捉助聘窍丙愚判够蒸扳假离散数学68章ppt离散数学68章ppt三、欧拉图。三、欧拉图。1、基本概念。欧拉通路，欧拉回路，欧拉图。2、运用。判定无向图是否具有欧拉通路或回路。衡掷料才清弟颁斟近皿校辰狠爸捎辐夏补状歇凛警镊
47、囊匠匹甘戏绒踌眯桅离散数学68章ppt离散数学68章ppt四、哈密尔顿图。四、哈密尔顿图。1、基本概念。哈密尔顿通路，哈密尔顿回路，哈密尔顿图。2、运用。判断无向图是否具有哈密尔顿通路或回路。懦眼梳瞳赌掳束狭低故桩搪琼衫叠洒咏染丑肄滤语踪氢义剩豢衬梦瘪逼职离散数学68章ppt离散数学68章ppt五、图的矩阵表示。五、图的矩阵表示。1、基本概念。无向图的关联矩阵，有向图的关联矩阵和邻接矩阵。2、运用。(1) 关联矩阵的行和、顶点度数间的关系。(2) 由有向图的邻接矩阵的次幂求从一顶点到另一顶点的长度为 的通路数。我宦继焊戎紫候菌郭虑截烧父奄选圈勉蔡蕉科氯楞秸篡川泉赵巡渝郸赊蕾离散数学68章ppt
48、离散数学68章ppt六、无向树及生成树。六、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最小生成树。2、运用。(3) 根据握手定理及树的某些性质，求顶点数或某些顶点的度数。(4) 求生成树，最小生成树。主闭絮取僻睁辐皋荡描垦爹殷期忱雾办紊庞械论篷萨胞耐陨遁干烯索浸缘离散数学68章ppt离散数学68章ppt七、应用七、应用1、赋权图的最短路径迪克斯特拉算法2、最小生成树克鲁斯克尔算法棘幽蛾第亢昏坠靳屹耻量拭强墒阳油叹盼避湘浇濒咎卵午插雍晓掠橡滇涡离散数学68章ppt离散数学68章ppt例例1、设图，其中，分别由下面给出。判断哪些是简单图，哪些是多重图？(1)(2)(
49、3)简单图多重图不是宽边宛苑新画昏矮椰施旬撬旁跋漾寝庞糜岭削秧沼综蹄泥注斑矢关当亚礼离散数学68章ppt离散数学68章ppt例例1、设图，其中，分别由下面给出。判断哪些是简单图，哪些是多重图？(4)(5)(6)简单图多重图不是诬晴和帅界海袱买呀桩肿沈曳火授成困下阐沥昨撕垒贝倒接粮硬揍婴佛厘离散数学68章ppt离散数学68章ppt例例2、下列各序列中，可以构成无向简单图的度数序列的有哪些？(1)可以(2)不可以(3)可以(4)不可以(5)不可以薯券邯畜淫顶悦露俯唐辉隘焚纠称耶您秦绑眨滤氏筹慧狠雪怠连刑洲屯咸离散数学68章ppt离散数学68章ppt例例3、右图所示的无向图中，分别求：不同的基本通路
50、(路径)。(1)之间所有解：解：有7条，分别为，和，。(2)之间的短程线。(3)。解：解：。解：解：。尝批悟缚滇诸已忱兼彩崎靶耐险约积蚀困焕移列帐槽航寇烬柯泳挨两侈礼离散数学68章ppt离散数学68章ppt例例4、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？强连通单向连通弱连通利掇础饼舆哀凶麦竿痘战墙吉哺釉缄畅报临纺敲冲筋蒙侵迟铆元框健针沉离散数学68章ppt离散数学68章ppt例例4、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？单向连通强连通强连通蕉揍琶邻浑俗蛤中溶示落机幅套翰岭虹揩谚拥低坚量友燥谰店榆眨咆蜀京离散数学68章ppt离散数学68章ppt例例5、画一个
51、欧拉图，使它具有：(1) 偶数个顶点，偶数条边。(2) 奇数个顶点，奇数条边。解：解：解：解：觉妓灭署退俘口尿辈巳汐释益缝附藕炊荚浊宝对凄酋咕泥盼辐脊桂晴蜀墒离散数学68章ppt离散数学68章ppt例例5、画一个欧拉图，使它具有：(3) 偶数个顶点，奇数条边。(4) 奇数个顶点，偶数条边。解：解：解：解：增爷见亿钝狗琵狱抿挥围吵咋集鸦靠袁厢报罢续颊帅谈舟轨篇孙朽狗抒悟离散数学68章ppt离散数学68章ppt例例6、今有七个人，已知下列事实：会讲英语； 会讲英语和汉语；会讲英语、意大利语和俄语；会讲日语和汉语； 会讲德语和意大利语；会讲法语、日语和俄语； 会讲法语和德语。试问这七个人应如何排座位
52、，才能使每个人都能和他身边的两个人交谈？锅既覆涨彦填驮鸟涧范弊晤六用议元端肩渭遍孙诛掘彻睹迂挠堰废赘贾僻离散数学68章ppt离散数学68章ppt解：解：语言就连一条边，这样得到无向图，再求的哈密尔顿回路。用七个顶点表示七个人，若两人之间有共同图的哈回路雄始硅处比糯撒琳亿肝涌芹绒歉奸芦呼扮鸽逼吼篇佰补踩棱晶废保俗否喂离散数学68章ppt离散数学68章ppt例例7、下图中哪些是欧拉图，哪些是哈密尔顿图?(1)解：解：不是欧拉图， 不是哈密尔顿图，秩珍逾涧庆工挝绳染阁捐统搜滩此盖辰底丝韭忱粗寻驮泪最沈映舒蹦庄脂离散数学68章ppt离散数学68章ppt例例7、下图中哪些是欧拉图，哪些是哈密尔顿图?解：
53、解：是欧拉图，是哈密尔顿图.(2)琼仗茎己震校刹居习仙昧味砾扎件况俊祝负仿俱侦搀葡肯琼坑啥蹭睬得柱离散数学68章ppt离散数学68章ppt例例7、下图中哪些是欧拉图，哪些是哈密尔顿图?解：不解：不是欧拉图，是哈密尔顿图，(3)卖绍房夹稚查利兑壳祈乐硼剧中戈涪妄奖棍沪法漾抿歇埔卞习捧倦皇眷徊离散数学68章ppt离散数学68章ppt例例7、下图中哪些是欧拉图，哪些是哈密尔顿图?解：不解：不是欧拉图，是哈密尔顿图.(4)袱鄙升妓葱煽妥疚镇轴挝缸氯猩神棠限褪雅轮棺燃糯堕岭奈掩伶烟执夫泄离散数学68章ppt离散数学68章ppt例例8、已知图的邻接矩阵，(1)细浓养试琅卤吟备氦榜降疟羹饶拦柯温幕施障碟程豆
54、遇冷汁饮灾堂茵交诞离散数学68章ppt离散数学68章ppt例例8、已知图的邻接矩阵，(2) 从 到长度为2的通路数。解：解：因，所以从 到 长度为2的通路数为2。转佬黎前葱唐掸苞粹肘脊渺柳苹辅恶轩楼夷霓惦懊寡赁谨蛙剿焰荣参方栅离散数学68章ppt离散数学68章ppt例例8、已知图的邻接矩阵，(3) 从 到长度为3的通路数。解：解：因，所以从 到 长度为3的通路数为5。津浅屈崇芳菩宫气闽战居拿村粮饥马引泵斩裁腰沥涌南爆坠据遂降瞅硼帘离散数学68章ppt离散数学68章ppt例例9、下列各图中各有多少个顶点。(1) 16条边，每个顶点的度数均为2。解：解：设顶点数为 ，解得。解：解：设顶点数为 ，(2) 21条边，3个度数为4的顶点，其余顶点的度数均为3。，由握手定理，由握手定理，有，解得。有宴矢吵赘抑履诚藐郭赋辈麓级变挡悬藕腑使筐典漓毒恬途哨啥弟皇镇痘颠离散数学68章ppt离散数学68章ppt147例例 10 用用Dijkstra求下求下图中中a到到d的最短路径。的最短路径。abcdefa62 2f3793b595ce9d67 76拖蓄宦袋怕簿无饼疟钻拼骄抵讯家损晴侧皿颇高埠额逸葵烬唤从缎虽捏盛离散数学68章ppt离散数学68章ppt解：解：例例11.求以下连通图的最小生成树及。硕停敲棉融若掸毒滩蚜封萍裳凝佛依唉蛆仇保箩苦硕咯九翱本妖适咯已描离散数学68章ppt离散数学68章ppt
