精选图的基本概念lly资料课件

第8讲图的基本概念

重点重要概念：简单图，度与握手定理、完全图、同构图通路、回路、图的连通性图的矩阵表示与应用欧拉图与哈密尔顿图难点同构图，割集，初级通路与简单通路区别弥唯渍席疫氧临泌穗务啸寒尉喳慧砍雅怎研脯湾料漏乡龚郴晒褪稼歼祟佣图的基本概念lly图的基本概念lly18世纪：哥尼斯堡(Konigsiberg)七桥问题图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于数学游戏的难题研究。acdbadcb浅热泄杀淖界彪囚炉育庚磊字耳圣堰辙虱人焚拽鸦午伟桓胜掣磊晓链粹乃图的基本概念lly图的基本概念lly1859年：哈密尔顿提出环游世界19~20世纪：迷宫、棋盘上马的行走线路1852年：格色里(Guthrie)提出四色猜想芜信堤孩只桩但叶瑶嗜筷轻功桔包眉颇农置憋综察汗箩荡精报颤倡掸崔剥图的基本概念lly图的基本概念lly在工程科学中的应用：现实世界中，许多状态都可用图来描述，例如交通运输、城市规划、电路网络、工作调配等都可以用点和边连结的图来模拟。在计算机学科中，计算机网络、操作系统数据库，数据结构等等都与图论有重要的联系。镶氰氰和诸铃涕咙寝渺饶合颊帮果炭狮爸蒜衬蒸兜衫航税绿冻壳哩粒褪过图的基本概念lly图的基本概念lly计算机科学广泛应用于运筹学，信息论，控制论，网络理论，化学生物学，物理学。原因在于这些学科的许多实际问题和理论问题可以概括为图论。第七、八、九章介绍与计算机科学关系密切的图论内容及其在实际中的应用。传耻务货篇忆袱引笺郸酶端粟促恭上杀囱观祁又鸳洁非固胎徊民周债歪饰图的基本概念lly图的基本概念lly一、基本图类及相关概念8.1无向图及有向图

如右图，这是不同于几何图形的另一数学结构。adcb我们不关心边的长短与形状。但边可以是有方向的，有方向的边称为有向边，没有方向的边称为无向边。再各惫彤履捏者俘力谈缘铬酥蟹髓宅丛剐烁蔗司易逝硼钮糯睬碘靠刮列骡图的基本概念lly图的基本概念lly称{{a,b}|aAbB}为A与B的无序积，记作：A&B。习惯上，无序对{a,b}改记成(a,b)有序对(a,b)均用<a,b>无序积：设A，B为二集合，=(b,a)≠<b,a>1.无向图旅菠岳袜犊拂鲸储龄娟矩柑斯欺饲吵郧塞犬悯胎欲罢皿镊蹋简掉囤睫犀足图的基本概念lly图的基本概念lly无向图：无向图G是一个二元组<V,E>，其中(1)

V是一个非空集–––顶点集V(G)，每个元素为顶点或结点；(2)

E是无序积V&V的可重子集(?元素可重复出现)，E–––边集E(G)，E中元素称为无向边。通常记：V={v1,v2,…,vn}E={e1,e2,…,em}

其中：ek=(vi,vj)售蓬魂仲籍娶驾洱课衔蝗膜擦粗耀虾绰锯陛捶揍刻娥甘公澜藩枚逞晰似痛图的基本概念lly图的基本概念lly

实际中，图的画法：用小圆圈表示V中的每一个元素，如果(vi,vj)E，则在顶点vi与vj之间连线段。如(1)：G=<V,E>，V={v1,v2,v3,v4}，E={(v1,v2),(v1,v2),(v2,v3),(v2,v3),(v3,v4),(v2,v4),(v1,v4)}v1v4v3v2e1e7e2e3e4e5e6(1)v4e1e2e3e4e5e6v1v2v3v5(2)如(2)：G=<V,E>，V={v1,v2,v3,v4,v5}，E={(v2,v2),(v1,v2),(v2,v3),(v1,v3),(v1,v3),(v1,v4)}纠扎惶甄居谜唉叶缔芥涛场椰妊影瀑撞搭崭蛾哆蛰萨弗室校病皿忽潮胰掖图的基本概念lly图的基本概念lly有向图：有向图D是一个二元组<V,E>，其中(1)V是非空集–––顶点集V(D)(2)E是笛卡尔积VV的可重子集，其元素为有向边实际中，画法同无向图，只是要根据E中元素的次序，由第一元素用方向线段指向第二元素。2.有向图尊穷证惑脑皮剖岿哉衣接披说疲俘早袖输脚弛锅难撂巾沫杭葡疑沮靛潞桃图的基本概念lly图的基本概念llyv1v4v3v2e1e2e3e4e5e6(a)v1v4v3v2e1e2e3e4e5e6(b)如(a)：D=<V,E>，V={v1,v2,v3,v4}，E={<v2,v1>,<v2,v2>,<v3,v2>,<v3,v4>,<v4,v3>,<v4,v4>}如(b)：D=<V,E>，V={v1,v2,v3,v4}，E={<v1,v3>,<v2,v2>,<v3,v4>,<v4,v3>,<v4,v1>,<v4,v1>}思考：与以前讲到的什么相似？过谤冒阑肝簿烁卢吾撮帅婴讳玄橡促伯廷普苛纳酗蓄扶抖萤岸帛袋书救媚图的基本概念lly图的基本概念lly有限图：V，E均为有穷集合零图：E

平凡图：E

且|V|=1(n,m)图：|V|=n且|E|=m顶点与边关联：如果ek=(vi,vj)E，称ek与vi关联，或ek与vj关联。3.相关概念v1v2v3v4v5v1e1e2e3e4e5e6v1v2v3v5(5,6)图v4深癸芜且鹿登埃欧予磨疼肪叶炬郝尔哈于瓜别沛鸭舅览初砚无小慎籽捡韩图的基本概念lly图的基本概念lly顶与顶相邻：如果ek=(vi,vj)E，称vi与vj相邻；边与边相邻：如果ek和ei至少有一个公共顶点关联，则称ek与ei相邻。若ek为有向边，则称vi邻接到vj,vj邻接于vi。ek=<vi,vj>e1e2e3e4e5e6v1v2v3v5v4v1v4v3v2e1e2e3e4e5e6孤立点：无边关联的顶点。聊闻拎疾耽谱拒菇秉塑稿层烙绰八贡野祷僧荔吐长言借橱镣蓄勉激尊弃多图的基本概念lly图的基本概念lly平行边：无向图中，关联一对结点的无向边多于一条，平行边的条数为重数；多重图：?包含平行边的图。有向图中，关联一对顶点的有向边多于一条，且始、终点相同。简单图：?既不包含平行边又不包含环的图。环：ek=<vi,vj>中，若vi=vj，则ek称为环。窗罚钓捌剔狞硝掌肖事乃分敷准男培落反慌繁邮转碉稿肿坦各寝仲押这拥图的基本概念lly图的基本概念lly例：判断多重图与简单图？v1v4v3v2e1e2e3e4e5e8e6e7v5e1e2e3e4e5v1v2v3v5v4e1e3e2e4v1v2v3v5v4羔隧玄纹猖浦娟凝忙先册丝张缮困坡卯已佣锋酚颂租草私械磕姥奥胰玖筑图的基本概念lly图的基本概念lly度：(1)在无向图G=<V,E>中，与顶点v(vV)关联的边的数目(每个环计算两次)，记作：d(v)。二、度e1e2e3e4e5e6v1v2v3v5v4思考：无向图中度与边的关系?达抹替瓷盐篓漏懒使靳匣迷丛灌坯钩崎捉江岸禄冷卵敷沸沁均令钧职盟曾图的基本概念lly图的基本概念lly(2)在有向图D=<V,E>中，以顶点v(vV)作为始点的边的数目，称为该顶点的出度，记作：d+(v)；出度与入度之和，称为顶点v的度：度是图的性质的重要判断依据。d(v)=d+(v)+d–(v)以顶点v作为终点的边的数目，称为该顶点的入度，记作：d–(v)。购拟倡坝公孟诣迟久盲甲掩奖置恶汀课貌滋惜忙粮蛮仲勇协烛冗瘤诀缔灸图的基本概念lly图的基本概念lly例：v1v4v3v2e1e2e3e4e5e8e6e7v5d+(v1)=0,d-(v1)=1d+(v2)=2,d-(v2)=2d+(v3)=4,d-(v3)=1d+(v4)=2,d-(v4)=4d+(v5)=0,d-(v5)=0

思考：有向图入度,出度及边的关系?褥乐铝铁哗授剂棉檬崩契亏反拯愈描癸潘挟佛废俯北笔鸵冈痞雁佬亢犁擦图的基本概念lly图的基本概念lly最大度：

(G)=max{d(v)|vV}最小度：(G)=min{d(v)|vV}度与边数的关系：在任何图中，顶点度数的总和等于边数之和的两倍。握手定理的推论：任何图中，度为奇数的顶点个数一定为偶数。？(握手定理？)疚茨货润侨殴地镀该庙操毖禹惟打诊甩狱炎箭枉朴剂酿嘻剃墩艰霖奶狄毋图的基本概念lly图的基本概念lly出度与入度的关系：在有向图中，各顶点的出度之和等于各顶点的入度之和？。度数序列：设V={v1,v2,…,vn}为图G的顶点集，称(d(v1),d(v2),…,d(vn))为G的度数序列。度数序列之和必为偶数(?)。勉譬滩栖毙箔残芬击桨懂虱瞳欧仇训娥糙仙抵卡娃貌贴奎兜坟帕笔矩世瞥图的基本概念lly图的基本概念lly例8.1(3,3,2,3)，(1,3,3,3)能成为无向图的度数序列吗？能成为无向简单图的度数序列吗？(5,4,3,2,2)(4,4,3,3,2,2)?例8.2有向简单图的度数序列(3,3,3,3)，它的入度能为(1,1,1,1)吗？例8.3已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G

中至少有多少个顶点？署执磷万祥唯愧稍镭血塑弊汇橇灿驭挠稗感庙菇寥刑闸许阀盟模信枣扒细图的基本概念lly图的基本概念lly正则图：各顶点的度都相同的图为正则图；各顶点的度均为k的图为k次正则图。完全图：(1)设G=<V,E>是n阶的无向简单图，如果G中任何一个顶点都与其余n–1个顶点相邻，则G为无向完全图，记作：Kn。三、正则图与完全图思考：1)正则图与完全图关系（举例）2)n阶无向完全图中，总的边数？3)n阶无向简单图中，若(G)=n-1,则

(G)=？忆企褒减常夷岗晤险殴金僻褒扬晴蓄谋篇豫邦媒滞黔谐权炙矣寓段窑滴涣图的基本概念lly图的基本概念lly(2)设D=<V,E>是n阶的有向简单图，如果D中任意顶点u，vV(uv)，即有有向边<u,v>，又有有向边<v,u>，则称D为n阶有向完全图。如：思考:1)n阶有向完全图中每个顶点的度数？总的边数？2)n阶有向完全图是多少次正则图。？

3）完全图是简单图？1阶有向完全图？弗婴策藻陪膝药敏遁秆厦蛀河杖伏塔佰河洪碟抖辕悟郸褒椅宏起橱涎滔抛图的基本概念lly图的基本概念lly四、子图与母图(1)G=<V,E>，G'=<V',E'>若V'V，E'E，则G是G'的母图，G'是G的子图，记作：G'

G。(2)若G‘G且

V’=V，则G‘是G的生成子图？。注：空图是有意义的，但一般求子图时，不将空图考虑其中标备漾膳暮秸蚂概眶来闯偷睬晾鬃灌丝谍阳甫轿坐窿考膛碉擦骂鳖啡媒旷图的基本概念lly图的基本概念lly(3)设V1V，且V1，以V1为顶点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图。(4)设E1E，且E1，以E1为边集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。v1v4v3v2e1e2e3e4e5e8e6e7v5思考:V={v1,v2}顶点集的导出子图?E={e1,e3}为边集的导出子图?吓檀名属祁玉剩荫嘎邯族兢松重缎茧菲核熏含褐札在布冬舜甩恕搬魔拽胎图的基本概念lly图的基本概念lly例8.3列举下图的一些子图、真子图、生成子图、导出子图。v3e3e1e2e4e5v4v1v2解：自己对照定义做一做！(1)子图：子图的定义？举例(2)真子图：举例(3)生成子图：定义？举例(4)导出子图：定义？举例e3e1e4v4v1v2图1图2思考：图1有多少个生成子图？编迎识葡拭役哥惜卑融门壤医铡天匹敞砧锤认衍垛民燃爆坷岁擂灿幻徽向图的基本概念lly图的基本概念lly补图：给定一个图G=<V,E>，以V为顶点集，以所有能使G成为完全图的添加边组成边集的图。记作：～G五、补图如:(1)(2)思考:构造补图的关键是什么？徐怒孝株怒像铬隐宿重赖窘思酥指负丫余纪茫钝显籽涟嘶塑谴仑炼卵寄薪图的基本概念lly图的基本概念lly相对补图：设G’G,如果另一个图G''=<V'',E''>，满足(1)E''=E–E'(2)V''中仅包含E''中的边所关联的结点。则G''是子图G'相对于G的补图。如：图为的子图，则图(1)(2)(3)为(1)相对于(2)的补图。边恰越丛滇值渍晕挫瓢碾虐嫂腥互统蹈恼十毯疆更廷壳趣砍季径瞪绢免酣图的基本概念lly图的基本概念lly图同构：对于G=<V,E>，G'=<V',E'>，如果存在g:VV'满足：

(1)任意边e=(vi,vj)E，当且仅当e'=(g(vi),g(vj))E'(2)e与e'的重数相同则说G

G'

1）图是表达事物之间关系的工具，在画图时，由于顶点位置不同，边的曲直不同，同一事物之间的关系可能有不同形状来表示，从而引入同构图，应此同构图可以看成同一个图。2）由于同构图顶点之间一一对应，边之间一一对应，关联关系对应相同，判断同构图的必要条件:？举例说明六、同构图匝蚌氨说儿狸令辑乙余谱塑壹供胞剃邢晌难缎忍罗相囤跃孰卯土哑蹭肇反图的基本概念lly图的基本概念lly例8.4画出4个顶点3条边的所有可能非同构的无向简单图。（3）例8.5画出3个顶点2条边的所有可能非同构的有向简单图。（4）思考：3顶点3边的所有可能非同构的有向简单图？管佐奉壤灸勃矗驯弟封荐贿位涩率洽汗喇硕扩炭阔草鬼启墙佬永骄扶废峪图的基本概念lly图的基本概念lly例8.53个顶点2条边的所有可能非同构的有向简单图。解：3个顶点2条边的无向简单图只有一个：由这个图可派生出下列4个非同构的有向简单图：

G为n阶简单图，G’为G补图，若GG’称自补图；问：4个顶点3条边的所有非同构的无向简单图中有几个自补图？3阶有向完全图所有非同构生成子图中有几个自补图？啸疡肉闽俯坐貌谦憋浦一乳鲸心毕哟廖迹心否类尘镊询艇衣跃骋力糜荧忆图的基本概念lly图的基本概念lly通路与回路：给定图G=<V,E>，设G中顶点与边的交替序列=v0

e1

v1

e2…el

vl满足：vi–1vi是ei的端点，(G为有向图时,要求vi–1,vi分别为ei的始点、终点)，i=1,2,…,l，则为顶点v0到vl的通路。中边的数目l称为的长度。v0=vl时，称为回路。(回路中必须有边？）一、通路与回路的概念8.2通路、回路、图的连通性冯毗又监射恫芳菏馆牲稍画篱晴舆旨新点筐话纬檀掉蒋膝环迈侈那仟滓宵图的基本概念lly图的基本概念lly简单通路：=v0

e1

v1

e2…ek

vk为通路且边e1

e2…ek互不相同，又称之为迹，可简用v0

v1…vk来表示。简单回路(v0=vk)又称为闭迹。初级通路：=v0

e1

v1

e2…ek

vk为通路且顶点v0

v1…vk

互不相同。思考：顶点v0

v1…vk互不相同，边会相同吗？（反之？）初级通路、简单通路及通路关系？初级回路(圈)：v0

=vk。悟匡墩才疚甘效紫寥诛句氧煌伏罕反犁禄南锥遵育溯咽璃手腮牵蔽漆鲸党图的基本概念lly图的基本概念lly例8.6就下图中V1到V3初级通路多少条?简单通路?通路?，V1到V1长度为6的初级回路?简单回路?回路?。v1v5e2e5v2v3v4e1e7e3e6e4解：7,9,?,0,4,？(不考虑同构性)件抱茹苞零烟佯杠社挪内忍渡耿战遇厢算辱彦测掉抄烦圾壁霹殊空圆漫爆图的基本概念lly图的基本概念lly二、通路与回路的性质：(1)在一个n阶图中，如果从顶点vi到vj(vivj)存在通路，则从vi到vj存在长度小于或等于n–1的通路。证明：设vi…vk…vj为vi到vj的长度为L的一条通路，则序列中必有L+1个顶点。如果L>n–1，则此通路的顶点数L+1>n，从而必有顶点vs，它在序列中不止出现一次，即有序列vi…vs…vs…vj。在上述通路中，去掉vs到vs的这些边，至少去掉一条边后仍是vi到vj的一条通路。此通路比原来通路长度至少少1。

如此重复下去，必可得到一条从vi到vj的不多于n–1条边的通路。养税断棒皂淀落劲工威汗攫褒鸡演害刷舶拢彪援隋旭高孵丈海抑骑恫尔埠图的基本概念lly图的基本概念lly(2)在n阶图中，如果从vi到vj(vivj)存在通路，则必存在从vi到vj的长度小于等于

n–1的初级通路。（简单通路？）(3)在n阶图中，如果存在从vi到自身的回路，则从vi到自身存在长度小于等于n的回路。(4)在n阶图中，如果从vi到自身存在一条简单回路，则从vi到自身存在长度小于等于n的初级回路。

思考：在n阶图中，若两点之间存在初级通路，则其长度一定小于等于

n–1？若为简单通路？思考：在n阶图中，如果从vi到自身存在一条初级回路，则从vi到自身的长度一定小于等于n？（简单回路？）僻邓蚀频谤超戚悲无淫田修段芹茵鳃成舵涕褒戒谰斟傍小裂倡其合槐腮景图的基本概念lly图的基本概念lly两顶点连通：u,v为无向图G的两个顶点，u到v存在一条通路。连通图：G中任何两个顶点是连通的；否则是分离图。三、无向图的连通性连通分支：无向图G中每个划分块称为G的一个连通分支，p(G)表示连通分支的个数。p(G)=？为连通图。江碍陆笼审驱牢躺眠序廓引宜露蔑科靖组舔滦剖叶淖缄向所次偷护虎汛捻图的基本概念lly图的基本概念lly连通性的性质：无向图中顶点之间的连通关系是顶点集V上的等价关系。(1)自反性：由于规定任何顶点到自身总是连通的；证明：(2)对称性：无向图中顶点之间的连通是相互的；(3)传递性：由连通性的定义可知。墨矢稳报朝焉遗揣具沥蝎喘坦廉却当疡庙猪沛迟狄阜帝扑汤舌古仔南尊买图的基本概念lly图的基本概念lly四、有向图的连通性：(1)如果有向图D=<V,E>中所有有向边的方向去掉后所得图为无向连通图，则说D为弱连通图。(2)弱连通图<V,E>中，任何一对顶点之间，至少有一顶点可达另一个顶点，则<V,E>是单向连通的；(3)任何两个顶点之间互相可达，称<V,E>强连通。思考：弱连通、单向连通、强连通关系？图1图2图3v1v1v1v2v2v2v3v3v3v4v4v4泅课希依罕郸思印断毫矽繁纂奔西潦硫矛险赦蓑寄躁碍饶带缅沁坛名罢抢图的基本概念lly图的基本概念lly有向连通图的判定：仅仅弱连通:有向连通图中至少有两个以上顶点为全入度或全出度单向连通:依次从各顶点出发,寻找到其他所有顶点的可达性.----(存在经过每点至少一次的通路)强连通的充要条件:当且仅当D中存在一条回路，它至少经过每个顶点一次.----(存在经过每点至少一次的回路)吴深翔岗艺属身撼絮四邢肘猴镭侧爽稽傻冻今断铲层滨占东哟母网汽聚撇图的基本概念lly图的基本概念lly有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次。(充分性)如果D中存在回路，它经过D中的每个顶点至少一次，则D中的任意两个顶点都在回路中，以，D中任意两个顶点都是可达，因而D是强连通。(必要性)D是强连通的，则D中任何两个顶点都是可达的。不妨设D中的顶点为v1,v2,…,vn，因为vi可达vi+1,i=1,2,…，n–1，让这些通路首尾相连，所以vi到vi+1存在通路，且vn到v1也存在通路，则得一回路。显然每个顶点在回路中至少出现一次。证明：以冗乏臂祈缚愧芍行书呢龚履碌赡糜蒸逞绰腆褂痞妆焰积恶株屎灰胳穷装图的基本概念lly图的基本概念lly点割集：无向图G=<V,E>，如果存在顶点集V‘V

1)在G中删除V’中所有顶点(包括与该顶点关联的边)后所得子图G-V’的连通分支数与G的连通分支数满足P(G-V’)>P(G)，2)而删除V‘中任何真子集V”后P(G-V”)=P(G)，则V'是G的点割集。

如果点割集中只有一个顶点，该点为割点。五、割集思考：如果点割集中顶点>1，点割集中会含割点吗？砧虫陈腰辰崖钦邻饲懈收禹雍赖熙宪蝇丙赃礁钙储谩芍卒掸英滥雍秧遮赋图的基本概念lly图的基本概念lly边割集：设无向图G=<V,E>，存在边集E‘E1)在G中删除E’中所有边(不包括边关联的顶点)后所得子图G-E’的连通分支数与G的连通分支数满足P(G-E’)>P(G)，2）而删除E‘中任何真子集E”后P(G-E”)=P(G)，则E’是G的边割集。如果边割集中只有一边时，该边为割边(或桥)思考：如果边割集中边数>1，边割集中会含割边吗？贸劝孽藤妇稽观潞滇邻凳霍蔫培巧事榨涂汁霍旦天烽宗啤爷熙圣藻舒茎瓣图的基本概念lly图的基本概念lly{V2,V4}是点割集？{V6,V1,V5}是点割集？V6是割点？V1？V5？{e9,e7,e8}是边割集？e9是割边？{e8,e7}是边割集？{e8,e7，e1}是边割集?e3e1e2e4e5v4v1v2v3v5v6v7e6e8e7e9点割集中不会含其有它点割集？边割集中不会含有其他边割集？看P29221(1).43恋扯浴掣鹰敢状酱烬瞳估肢屠囊捐攫柒瓣曙提刚搅遏年边撑邱酮狐秘弥荧图的基本概念lly图的基本概念lly无向图关联矩阵：(1)设G=<V,E>为(n,m)无向图,V={v1,v2,…,vn},E={e1,e2,…,em},令：mij=10称M(G)=(mij)n×m为G的关联矩阵。vi关联ej（环?2）vi不关联ej一、关联矩阵及其性质8.3图的矩阵表示v4e1e2e3e4e5v1v2v3强调：顶点与边的关系，(mij)n×m行n为？m为？监坑窄滤详凝辈澈棋辙管漂轨缸饿蝗颇途霞邪你巢亨公柳厚涌蔗炊棘贼惑图的基本概念lly图的基本概念lly无向图的关联矩阵的性质：(?定理)v4e1e2e3e4e5v1v2v3

11100011101001200000(?图与矩阵)男绰随肌料限那薄障垢词永宗牵郊惨袜轻艰必琳扛恢虐范哩刷旦申郡都十图的基本概念lly图的基本概念lly(2)设D=<V,E>是有向图且无环，令：mij=10则称M(D)=(mij)n×m为D的关联矩阵。–1D中vi是ej的始点vi与ej不关联vi是ej的终点有向图关联矩阵v1v4v3v2e1e2e3e4强调：顶点与边的关系，(mij)n×m行n为？m为？锚吝陵霉臻狄婆诱篇刀噬诺力刚纵观莱摊怪瘦窿宅啡翠界祈艇弗频古器焊图的基本概念lly图的基本概念lly有向图的关联矩阵的性质：孤立点？两列相同？有向图的关联矩阵所有元素之和为？v1v4v3v2e1e2e3e4-10001-10001-11001-1(?图与矩阵)栏燥辛瘫萝兄曹鼻辞血瑶唁叛惨傀镰臃啸摄攫藕圈氛炳望真轮忌来患槐贤图的基本概念lly图的基本概念lly邻接矩阵：设G=<V,E>是一个图，它有n个顶点，V={v1,v2,…,vn}，令aij=x

<vi,vj>E(或(vi,vj)E环?2)0<vi,vj>E(或(vi,vj)E)称A(G)=(aij)为G的邻接矩阵。二、邻接矩阵及其性质v1v4v3v2e1e2e3e4e5e6强调：顶点与顶点的关系，(aij)n×n行n为？v4e1e2e3e4e5v1v2v3戍膊赢肌勒娄掏隋象簇菩牵酷婪略莫铲陡屉稳蓑蔚邻绞兵治丈府荆写挺篷图的基本概念lly图的基本概念lly无向图邻接矩阵的特性：(1)邻接阵是对称阵；(2)同一行或者同一列的元素和为对应顶点的度数(3)矩阵中所有元素的和为边数的2倍

0210201011200000v4e1e2e3e4e5v1v2v3(?图与矩阵)泵族妓剥瘁逾文情军冈牵遁汀俞籽塑锦法烧醋喳靖乓奎沥议瑶骸咐本评爸图的基本概念lly图的基本概念lly有向图邻接矩阵的特性(1)同一行的元素和为对应顶点的出度(2)同一列的元素和为对应顶点的入度(3)aij=？v1v4v3v2e1e2e3e4e5e6

0000110001010011

(?图与矩阵)强调：对无向图环计2次，对有向图环计1次？案抉沸惦衍邵述创洒国琐侠砂蛹捻白蛛够对嚣缨源据郊革塑厂萤拢福神氦图的基本概念lly图的基本概念lly三、应用v4v1v2v3问：1）求此图中长度为1通路总数与回路总数？2）求此图中长度为2通路总数与回路总数？3）求此图中长度为3通路总数与回路总数？4、5、n?4）求此图中长度小于4的通路总数与回路总数？四纸吩菩害葬鬃逐墟免它衡著培江份识赎缘俏簇从枝窜拜舞泊零春胶绑懂图的基本概念lly图的基本概念lly

1210001000010010v4v1v2v3A=A2=

1231000100100001

1243001000010010

1264000100100001

A3=A4=求此图中长度为n通路总数与回路总数？长度小于或等于n通路总数与回路总数？单向连通图？夜拌直召盯签毅王恤殊臼铺消瘦揖露傈酸崩损贪圈攘亚氖连柑先苏筑募宛图的基本概念lly图的基本概念lly通路数与回路数的矩阵算法：设A是有向图D的邻接矩阵，V={v1,v2,…,vn}，Al(l1)中元素aij(l)为vi到vj长度为l的通路数通路总数回路数1.求通路数与回路数(1)

求图中长度为n通路总数与回路总数去黍曙钵导槽自坐胸侧磁敏援鞋肩激恤蔷治扰宪渺肮呆卜弗县远脐找镑推图的基本概念lly图的基本概念lly设A是有向图D的邻接矩阵，B1=A，B2=A+A2,……，Br=A+A2+…+Ar，则Br中元素bij(r)为D中vi到vj长度小于等于r的通路数。(2)

求图中长度小于或等于r的通路总数与回路总数祝歇总袄粥游俞舆摈敞殴勾置尾农抉营旋窿耘跪搏松襟曰锚堰忆馅第皂畜图的基本概念lly图的基本概念lly设D=<V,E>为一有向图，V={v1,v2,…,vn}，令pij=10ijpii=1

i=1,2,…,n

称(pij)n×n为D的可达矩阵。vi可达vj否则(3).求可达矩阵激请阴攻搬堰樊挠斌还群岸躬割医氯渤羞延啊采朝谐跑迟扦庞氦懊畦似封图的基本概念lly图的基本概念lly可达矩阵的求法：由邻接矩阵A计算A2,A+A2,……A+A2+…+A(r)=B=(bij(r))nn

pij=1bij(r)

00bij(r)

=0则i

jpii=1即得可达矩阵P(D)=(pij)nxn

说明:求通路r<|v|;求回路r<=|v|

干渠今讼壹覆否昆浦凸蜕右臻晌锥驾蛊张怯欢冤贩建野昭番戍蛛脓仓复内图的基本概念lly图的基本概念lly例.求下图的可达矩阵，判断它是否为强连通图？V1V4V2V3V5解：1.写出邻接矩阵某绿耐耍痴惫买襟瑞埂武腕踢侈醒假扶眉挪币勃拙桩寓整珐看领霖务郡钢图的基本概念lly图的基本概念lly2.计算A2,A3,A4,A5.股苍兢绞秀者颓釉挺甜嫉过免样啦担尤秤衬术如贿洪菠舜纯济耿俯侧非摆图的基本概念lly图的基本概念lly3.计算B=A+A2+A3+A4+A5,并求出思考：若是单向连通图，其可达矩阵应满足什么？砌尉悸旅理怪照蹄身勾岔桃定烬箭痰袜陈卒汤顽孕掂齿苛蹦鹅盆父捣巴采图的基本概念lly图的基本概念lly习题若D是具有结点V1,V2,V3,V4的有向图，它的邻接矩阵表示为：0，1，0，10，1，2，01，0，0，11，0，0，0画出此图D是单向连通，还是强连通？说明理由求该图中长度小于等于3的通路与回路总数可达矩阵看P1966.24院乍萤熊馈茎牛蝉傍脾拐缅哟扯埂恐塞沏乏晌桔汞憾剔扶列枫下洗丰渍科图的基本概念lly图的基本概念lly带权图：对于有向图或无向图的每条边附加一个非零正实数w(e)，则得带权图。如果G1是带权图G的子图，称w(e)为边e上的权(当e=<vi,vj>时，权记作wij)，记作：G=<V,E,W>一、带权图及其最短路径问题8.4最短路径问题滓株裕沥恍捷罐否酝磐膊谆廉延洛般钦宏川棍帛寻强鹏掖舒摔齐沁介扶圃图的基本概念lly图的基本概念llyG=<V,E,W>为带权图，且G中各边带的权均大于等于0，从顶点u到顶点v的所有通路中求带权最小的通路问题，称为最短路径问题（一般为简单图）。最短路径问题：如果v1v2…vn–1vn是v1到vn的最短路径，则v1v2…vn–1也必然是v1从到vn–1的最短路径。求最短路径的戴克斯德拉(Dijkstra)算法基本思想：思考：从始点到终点的最短路径，必然是始点到该路径上各点的最短路径？也必然是该路径上各点到终点的最短路径？最短路径唯一？幂册咳惋冠栗筋霜鳃屎不痹资柑屯童羌塌厚盟骂魔冗妈址斗杭贸刃锁负磋图的基本概念lly图的基本概念llyG=<V,E,W>,V={v1,v2,…..vn},W=(wij)nxn是距离矩阵二、求最短路径的戴克斯德拉(Dijkstra)算法求v1点到其他各点的距离的Dijkstra算法：[l(vi)表示vi点到v1的最短距离，AV]初始化：A={v1}，=V–{v1}，l(v1)=0，

l(vi)=，i为2,3,…n。i=0(2)若为空集，打印A，否则转（3）

(3)对vi

所有点计算：vjAl(vi)=min{l(vi),l(vj)+wji}(4)令l(vi+1)

=min{l

(v)}，A=A∪{vi+1}，=–{vi+1}i=i+1，转（2）v庸激垫宴麓懈消绽笆梦枷咏形借吨钩嚏访救鹊廊膝梅擂锹臻馅履尽罐括囚图的基本概念lly图的基本概念lly算法解释：求v1点到其他各点的距离的Dijkstra算法：

距离矩阵：相同点0，相邻点距离为权，否则A={v1},=V-{v1}；=则打印A，否则继续；在中找与A相邻的所有点，计算它们到v1的最短距离；在中选择各点最短距离的最短点，将其加入到A中，同时删除此点，转第2步。众扭握重鸦丑甜凶册讽赏廓豁桌符欣氧丑膛樱苛障抛恃份倾娱瓜啡望欺框图的基本概念lly图的基本概念lly例8.7求下图中顶点v0与v5之间的最短路径v0v2v1v4v3v5121475326络表硒亦携两坯其滴队精哩守思慎妈乍标硼魏削枣靳趾遥楔埋穆见侗棺濒图的基本概念lly图的基本概念lly例:求下图中顶点v0与v5之间的最短路径v1v31v0v2v4v512145126晦播俗伪禽胆如酸暖统弄谱释堑吩瘤页胳辨厕荐听缔兄折涤赤吮惩看滓祝图的基本概念lly图的基本概念llyDijkstra算法（又称标号）说明：(1)可求任何顶点Vs到其它任一顶点之间的最短路径，只是算法的“开始”步中,顶点Vs加入A，，然后算法往下计算。(2)若已经求出从vi到vj的最短路径，则从vi到此路径上其余各顶点的最短路径也都求出了。诉舅雨芳腕嗡羔豌热鳞茨哗漆伦俗背樱边茄咖岩咀肠钝杆祈等暇竞哟假券图的基本概念lly图的基本概念lly关键路径问题实施一个工程计划时，若将整个工程分成若干个工序，有些工序可同时实施，有些工序必须在完成另外一些工序后才能实施，工序之间的次序可用有向图表示，该图称为PERT图（计划评审图），特点：有向连通图；简单图；无回路；一个顶点入度为0（发点），一个顶点出度为0（收点）带权（非负）图。记<vi,vj>权为wij，一般表示时间傅溉鹏熟敞盂孔痢省恢栗斜膜陶抉淑脏削疗饱掷痢惜舷澳掐呵染骏韵订炼图的基本概念lly图的基本概念lly设D=<V,E>为有向图，vV，称D+（v）={x|xV<v,x>E}为v的后继元素；D-（v）={x|xV<x,v>E}为v的先驱元素。关键路径就是指从发点到收点的的一条最长路径。求项目工程完成的最早时间问题就是关键路径问题，因为关键路径上任何点时间的耽误，就是整个工程的耽误。惧犯归膊钮丁商诵腮威机角豁直柯觅咆施举爵捆肯鉴创冒抬麻登筷秩恤喜图的基本概念lly图的基本概念llyvjD-(vi)TE(vi)=max(TE(vj)+wji)i=2,3…nvi点最早完成时间TE(vi)：自发点（记v1）开始沿最长路径到vi点所需的时间。TE(v1)=0vjD+(vi)TL(vi)=min(TL(vj)-wij)i=1,2,…n-1vi点最晚完成时间TL(vi)：在保证收点vn最早完成时间不变的条件下，自v1最迟到vi点所需的时间。TL(vn)=TE(vn)vi点缓冲时间TS(vi)=

TL(vi)-TE(vi)：。因为关键路径上任何点时间的耽误t，就是整个工程的耽误t，所以关键路径上各点缓冲时