图的基本概念

《离散数学》——第七章图论7-1

图的基本概念7-2路与回路7-3图的矩阵表示7-4欧拉图与哈密尔顿图7-5平面图7-6对偶图与着色7-7树与生成树7-8根树及其应用绪论图论的诞生——哥尼斯堡七桥问题

从任意一点出发，经过每座桥恰好一次，再回到原点。1736年，欧拉（Euler）解决了该问题——图论诞生。

几个有名的图论问题四色猜想莫比乌斯（Möbius）于1840年提出：

对地图上的每个国家着色，使得任意相邻的两个国家着不同的颜色，猜想：只需要四种颜。

阿佩尔和哈肯（Appel，Haken）于1976借助计算机花费1200小时证明了该猜想。中国邮递员问题管梅谷与1960年提出：一个邮递员，每次送信必须从邮局出发，走遍他所投递的区域内的所有街道，最终回到邮局。问：怎样使他所走的路最短。哥尼斯堡七桥问题：每条边走恰好一次；中国邮递员问题：每条边可以走多次。哈密尔顿图戏)

求解问题

1859年爱尔兰数学家威廉·哈密尔顿（SirWilliamHamilton）发明了一个小游戏玩具：一个木刻的正十二面体，每面系正五角形，三面交于一角，共有20个角，每角标有世界上一个重要城市。哈密尔顿提出一个问题：要求沿正十二面体的边寻找一条路通过20个城市，而每个城市只通过一次，最后返回原地。哈密尔顿将此问题称为周游世界问题。游 抽象为图论问题

哈密尔顿给出了肯定回答，该问题的解是存在的哈密尔顿回路(圈)哈密尔顿图运筹学、计算机科学和编码理论中的很多问题都可以化为哈密尔顿图问题

旅行售货员问题给出城市之间的距离，一位售货员从某一城市出发，经过每个城市恰好一次，然后回到出发的城市，要求他所走的路经最短。美国数学家威特涅与1934年在普林斯顿的一个讨论班上提出。该问题在理论和应用上都很有价值，迄今有很多论文研究该问题。图论及其在计算机科学中的应用例子

图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用。在计算机科学领域，如数据结构、语言、算法、数据库、操作系统、人工智能、网络理论、开关理论等方面，图论扮演着重要的角色。如：数据结构中的图、树数据库中的网状模型计算机网络中的环网络、星形网络等算法设计与分析、人工智能…并行计算机中的多处理器互连网络（MultiprocessorInterconnectionNetwork）无线传感器网络（WirelessSensorNetwork）……多处理器互连网络一个多处理器互连网络可用一个图G=（V，E）表示，其中V中的每个顶点v表示一个处理器，E中的每条边表示处理器之间的链路（Hard-link）。应用：并行计算机中若干个处理器连接的方式。例：n维超立方体Q_n=(V,E):V中每个顶点表示为一个长度为n的二进制串，E中两个顶点之间有一条边当且仅当它们只有一位不同。顶点个数2n，边数：n2n-1。超立方体性并行机：CM-2，nCUBE，IPSC-860，SGIOrigin2000。IBM的蓝色基因/L（Bluegene/L）：65536个处理器，Torus网络结构运算速度：2005年IBM的蓝色基因以每秒钟计算280万亿次浮点运算；2007年每秒钟计算一千万亿次浮点运算每秒蝉联冠军宝座(Roadrunner)。超级计算机的应用：石油勘探、天气、天文、生物等方面。第七章图论--绪论图论起源于智力游戏的难题研究，如哥尼斯堡七桥问题、迷宫问题、匿门博奕问题、四色猜想问题、汉密尔顿（环游世界）、棋盘上马的行走线路问题等。图论的第一篇论文1736年欧拉发表的，阐述了解决哥尼斯堡七桥问题的思想。欧拉享有“图论之父”之称。1847年克希霍夫利用图论分析电路网络中的电流问题。图论起源图论应用于工程技术问题的首篇论文7-1图的基本概念一、图的定义二、图的分类无向图有向图混合图三、几个基本概念四、结点度数的几个基本定理五、子图与补图六、图的同构第七章图论7-1图的基本概念--定义图的定义（定义7-1.1）

一个图是一个三元组<V(G),E(G),φG>，其中V(G)是一个非空的结点集合，E(G)是边集合,φG是从边集合E到结点无序偶（或有序偶）集合上的函数。例1无向图例2有向图例3混合图若把图中的边ei看作总是与两个结点关联，那么一个图亦可记为G=<V，E>，其中V是非空结点集，E是连接结点的边集。7-1图的基本概念目录若边ei与结点无序偶(vj,vk)相关联，则称该边为无向边。若边ei与结点有序偶<vj,vk>相关联，则称该边为有向边，其中yj为起点，yk为终点。e2e3abcde1e4e5e6例1G=<V(G),E(G),φG>，其中V(G)={a,b,c,d},E(G)={e1,e2,e3,e4,e5,e6},φG(e1)=(a,b),φG(e2)=(a,c),φG(e3)=(b,d),φG(e4)=(b,c),φG(e5)=(d,c),G(e6)=(a,d)。返回无向图----图中每一条边为无向边。7-1图的基本概念--定义例2G=<V(G),E(G),φG>，其中V(G)={a,b,c,d},E(G)={e1,e2,e3,e4,e5,e6},φG(e1)=<a,b>,φG(e2)=<a,c>,φG(e3)=<b,d>,φG(e4)=<b,c>,φG(e5)=<d,c>,φG(e6)=<a,d>。e2e3abcde1e4e5e6返回有向图----图中每一条边为有向边。(一般地：<a,b>≠<b,a>)7-1图的基本概念--定义返回e2e3abcde1e4e5e6混合帝图--血--图中腾一些来边为尘有向晓边，晓一些闭边为野无向微边。例37-危1哭图的轿基本化概念巨--渔定义7-休1捕图吨的基杜本概感念-拒--厚几个佣基本喷概念边与两喷个结路点关联图的分类无向图有向图混合图邻接题点无向趟边有向芬边平行灰边邻接忙边环（原或自锦回路）简单妙图多重掩图完全害图孤立元结点店零图台平汤凡图结点储的度夸数7-领1图的遣基本占概念若φG条(e)=睛(a,筋b),或φG睡(e)坟=<a,脂b>,则称粒边e与两埋个结饥点a,例b关联体。例如仰，e1关联匠于结谈点a，b，e2关联师于结加点v1，v2。邻接冈点--由一瘦条有弓向（晚或无迈向）衣边关玻联的于结点霞称为岭邻接钞点。煎如图订，a，b互为辜邻接场点，v1与v2邻接恰。abe1v1v2e2环或自回交路--纸-关联溉于同神一结薪点的型一条絮边。孤立尽结点--在一薪个图栽中不各与任夫何结卸点相承邻接恭的结婚点。零图—仅由犬孤立管结点铸组成种的图客称为逝零图遵。平凡隶图—仅由一御个孤陕立结般点构皮成的穿图称绑为平培凡图殊。几个早基本悦概念7-蛾1万图蛋的基达本概膊念-离--雹几个驻基本利概念邻接象边--关联蜡于同刺一结累点的多条边。品例如壳，e1,e2,e6互为傅邻接纸边。e1e2e6abcd平行吴边--连接于以同一箱对结惩点间腾的多会条边苏称为日平行团边。陵如果森是有急向边王要求阅方向受一致挣。多重国图--含有平杂行边旗的图渡称为袜多重度图。简单督图—不含平吴行边泳和环愤的图帝。abc几个娱基本木概念7-傅1晨图腰的基庭本概库念-贝--希几个迟基本息概念完全浮图(无向准图)--在简渔单图肆中，吹若每是一对撇不同医结点泼间都村有边逮相连恼，则结称该强图为族完全那图。心有n个结刮点的剩无向蔑完全返图记流作Kn。如帅果在Kn中，屈给每速条边半任意撤确定激一个纯方向铜，就腿称该载图为n个结叉点的有向椒完全尚图。7-会1饼图外的基稳本概惯念-图--鸭几个款基本私概念几个史基概敬念完全佩图的摊性质（定理7-澡1.吸4）n个结俘点的姜无向图完全察图Kn的边咬数为号：n(汪n-娇1)/2。定理7-蔬1.逢4证明荒：结点某的度数（定用义7-渐1.晋2）在图G=炸<V，E>，与结喉点v关联迟的边编数，挺称作毙是该结点拼的度碎数，恋记作de虎g(叼v)。图G=纽奉<V，E>的最科大度Δ(姥G)存=m骡ax毕{d僵eg覆(v旦)|坡v∈塘V(鉴G)爱},图G=符<V，E>的最葬小度δ(肝G)悉=m源in新{d毙eg招(v词)|推v∈黑V(中G)揉}。有向披图中盒结点算的度袜数（胳定义7-剃1.探3）在有色向图亮中，呆射入加一个摩结点子的边迷数称乖为该俯结点迟的入度，由词一个诱结点生射出勤的边在数称获为该窑结点视的出度。结孕点的豪出度些与入遗度之剧和就兄是该结点宅的度数。7-材1阶图牢的基析本概倦念-已--认几个单基本个概念定理7-商1.东1（握里手定寇理）点每防个图岛中，趣所有魔结点盛度数悄的总狂和等过于边兵数的缠两倍替，即∑de叶g(v)揭=林2|E|v∈V证明：因为括每条冰边必男关联杜两个蒙结点发，而婆一条质边给行于关联弄的每呆个结请点的供度数刃为1。因名此在箭一个漫图中询，结点度链数的穿度数吵的总呜和等沾于边钻数的握两倍夫。返回位几个角定理7-塔1昆图似的基净本概望念-心--沿几个倚定理定理7-冬1.侍2在任阴何图角中，驶度数桑为奇训数的景结点钓必定氏为偶借数个期。证明：设V1和V2分别排是G中奇宪数和东偶数昌度数庆的结缘瑞点集予，则慨由定理7-甜1.填1，有∑de醉g(v)法+∑de毒g(v)孙=∑de膝g(v)砖=璃2|E|v∈舅V1v∈套V2v∈星V由于∑de燃g(姥v)是偶殖数之高和，肆必为徐偶数舒，而2|E|是偶赚数，v∈显V2故得∑de近g(v)是偶移数，星即|V1|是偶腿数。v∈男V1返回粘几个叙定理7-腊1凡图绕的基阳本概骨念-训--潮几个抵定理定理7-邮1.泉3在任泽何有救向图女中，众所有利结点伯的入硬度之立和等游于所有结浮点的罪出度考之和动。证明：因为蕉每一芒条有揪向边页必对坑应一笼个入筋度和忧一个热出度绩，若一个拔结点长具有泰一个茫入度型或出毛度，验则必御关联毫一条纵有向萍边。所以宣，有芽向图什中各伯结点偏入度骄之和考等于津边数站，各点结点灾出度之和即也等侦于边氧数，先因此叛，任稼何有蒜向图浑中，姻入度守之和登等于出度泊之和比。返回间几个汽定理7-仇1施图胖的基证本概艇念-跨--树几个论定理定理7-络1.薯4n个结兴点的那无向钢完全举图Kn的边贷数为n(n-1钳)/2。证明：在Kn中，源任意识两个命结点旧间都惩有边咳相连普，n个结训点中任取灾两点图的组犬合数恒为：Cn2=n(n-1郑)/2故Kn的边数关为：|E瞎|=n(n-1员)/2。返回7-凯1技图饿的基奏本概浴念-勤--鞋几个席定理子图（定义7-亩1.立7）设图G=只<V，E>，若椒有一播个图G’箭=<蔽V’友,E膀’>满足V’V且E’E,则称G’为G的子芦图。例如:下图销中(b冠)，(c漂)都是(a披)的子理图。(a)(b)(c)7-瓦1去图凯的基卡本概归念-效--倘子图返回图G相对首于完枣全图喂的补桌图（定义7-液1.贯6）给定勒一个寸图G，由G中所押有结宜点和潮所有慨能使G成为参完全图的酱添加自边组流成的准图，仪称为G的相禾对于校完全啊图的贼补图但，或简称如为G的补陡图，烧记作G。例如茂：子图G’的相仁对于恨图G的补伞图（定义7-神1.隔8）设G’魔=<快V’柜,E途’>是G=狡<V院,E银>的一律个子晶图，张若给挪定另醒外一千个图G”馅=<始V”惭,E罗”>使得E”滩=E稳-E废’，且V”中仅包紧含E”的边毕所关窜联的腿结点黄，则样称G”是子图G’的相对静于图G的补帅图。例如能：7-朋1远图芬的基密本概仇念-拉--行补图返回7-年1图G相对偏于完阵全图燃的补膜图(定义7-错1.齿6)给定晕一个杆图G，由G中所猪有结仪点和鸡所有旅能使G称为棚完全图的闪添加格边组甘成的陪图，殊称为G的相晨对于茅完全窑图的深补图段，或简称解为G的补核图，料记作G。例如昼：(a)(b)(c)7-腥1洗图殃的基女本概芹念-叹--咏补图返回子图G’的相锁对于顿图G的补胁图（定义7-涉1.台8）设G’遥=<期V’姻,E破’>是图G=娱<G蛇,E乐>的子图，缩慧若给剖定另漏外一好个图G”概=<毯V”们,E蜘”>使得E”稻=E赛-E娱’，且V”中仅包赖含E”的边惹所关拥联的友结点彻，则巨称G”是子源图G’的相对核于图G的补拣图。例如他：图(c躲)是图(b裤)相对教于图(a吐)的补警图。锯图(b壶)不是图(c币)相对足于图(a帐)的补驻图。7-丹1榨图罗的基杏本概豪念-挑--愉补图返回图的意同构奥（定朋义7-唇1.辉9）设图G=刃<V敞,E耐>及图G’趋=<评G’战,E棵