离散数学讲义之图论.pdf
《离散数学讲义之图论.pdf》由会员分享,可在线阅读,更多相关《离散数学讲义之图论.pdf(124页珍藏版)》请在咨信网上搜索。
1、离散数学讲义之图论主讲:熊焕亮图论简介图论(g ra p h the o ry)是研究节点和边组成的图 形的数学理论和方法,为离散数学的一个重要分 支。图论的基本元素是节点和边(也称线、弧、枝),用节点表示所研究的对象,用边表示研究 对象之间的某种特定关系。因此,图论可用节点 和边组成的图形及其有关的理论和方法来描述、分析和解决各种实际问题,已广泛地应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、管理科学、社会科学等几乎 所有学科领域的有关问题。图论与组合数学、线 性规划、群论、矩阵论、概率论、数值分析等数 学分支有密切的关系。J J J 2图论简介图论中的图是由若干给
2、定的点及连接两点的线所构成的图形,这种图 形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连 接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学 的一部份,因此,历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在瑞士数学家欧拉(Le o n ha rd Eul a r)1736年的论文中,解决了著名的哥尼斯保七桥问题。因此通常认为欧 拉是图论的创始人。1845年,德国物理学家基尔霍夫为了解决一类线性联立方程组而创建“树”理论。他把电网络和其中的电阻、电容和电感等抽象化,用一 个只有点和边组成的组合结构来代替电网络,而不指明每条边所代表 的电器元件种类
3、,这样就可以方便地对方程组进行求解。1852年,格思里在对地图着色时发现,无论多么复杂的地图,只要用四 种颜色就能将相邻区域区分开来。这就是所谓“四色猜想”。经过百 余年的努力,直到1976年才由阿佩尔和赫肯借助电子计算机证明了四 色定理。t S3图论简介 1856年,哈密顿在给格雷夫斯的信中提出一个游戏:用正十二面体 上20个顶点表示20个城市,要求游戏者沿着各边行走,走遍每个城 市一次且仅一次,最后回到原出发城市。这个游戏促使人们研究如 何判断一个图有无这一性质,如果有,则又如何确定这样的路径,即称之为哈密顿图。这是一个至今尚未完全解决的问题。1962年,中国数学家管梅谷提出一个所谓“中国
4、邮路问题”:邮递员 带着邮件从邮局出发,走遍他所管辖的每一条街道,最后回到邮局,如何选择路线,使走的路程最短。1967年,埃德蒙兹给出中国邮路 问题一个好的解法。图论虽有200年的历史,但受计算机科学发展的刺激,发展极其迅速。上世纪60年代以来图论在各种学科领域中得到了广泛应用。图论在 理论上也得到了新的发展,如图特等发展了拟阵理论,贝尔热等发 展了超图理论,埃尔德什等发展了极图理论等。本书介绍图的基本概念、路与回路、图的矩阵表示、欧拉图与汉密 尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用、二 部图、匹配等。各章节主要知识点关联如图4.0.0所示。t S4图4.0.0第四部分各章节主
5、要知识点关联图I简单图平凡图相邻带权图匹配性欧拉通路I 欧拉回路哈密顿图最小生成树中序行遍法强连通图根树遍历二叉树前序行遍法边覆盖 集支配集带权图点独立 集点覆盖 集最优树 IHufftnan 算法后序行遍法欧I树生成树|.5图的基本概念目录第十一章图的基本概念11.1 图的概念11.1.2 简单图、多重图和同构图11.1.3 完全图和正则图11.1.4 几种特殊的图11.1.5 子图11.1.6 图的操作11.2 图的连通性11.2.1 通路与回路11.2.2 连通图11.2.3 二部图11.3 图的矩阵表示11.3.1 关联矩阵11.3.2 邻接矩阵11.3.3 可达矩阵11.4 图的运算
6、11.5 欧拉图11.5.1 欧拉通路和回路1L5.2半欧拉图和欧拉图11.5.3 哥尼斯堡七桥问题11.6 哈密顿图11.6.1 哈密顿图11.6.2 哈密顿图的充分条件11.7 带权图11.8 平面图11.8.1 平面图的基本概念及性质11.8.2 库拉托夫基定理11.8.3 平面图着色及应用11.8.4 边着色11.9 应用举例*11.9.1 中国邮路问题1L9.2冰箱分隔问题1L9.3排课表问题6第十一章图的基本概念 11.1图的概念现实世界中许多现象都可以用某种图形表示,这 些图形由一些点和连接两点间的连线所组成,点 表示事物,用点与点之间是否有连线表示事物之 间是否有某种联系,这样
7、构成的图形就是图论中 的图。711.1图的概念 11.L1无向图和有向图 定义1LL1 一个图是一个有序的二元组 匕石,记作G,其中(。/=匕,刈,一是有限非空集合,称为顶点集,其元素称为顶点o 屯:石工4,/4一,。是有限集合,称为边集,石中每个元素都有口中 的结点对与之对应,称为边。定义1L1.1中的边e既可以是有向的,也可以是无向的。有向边与有序 结点对 弟应,这时所为e的起点,历e的终点。无向边与无序结点舟。力对应,了称为e的两个端点。(3)将图的集合定义转化成图形表示之后,常用外表示图的遮,.),称顶点或边用字母标定的图为标定图,否则称为非标定图。(4)将有向图各有向边均改成无向边后
8、的无向图称为原有向图的基图。(5)若一条边连接同一个点,称其为圈。811.1图的概念(6)若1叩=,勾=。,则通常称它为(p,G图。夕称为图G的阶,(1,0)图称为平凡图。边集石为空集的图称为零图。顶点集/口边集E都是 有限集的图称为有限图。(7)若e=(,江,则称点与点讲目邻接。并说点与边行相关联,点与边 已相关联。向样,若边e和边用一个共同的端点,则也称边已和边讲目 邻接。没有边关联于它的顶点称为孤立点,不与其它任何边相邻接的 边称为孤立边。例11.1.1(1)给定无向图 G=,其中V=a,h.c.d,E=.o画出G与。的图形。911.1图的概念解图11.1.1中(a),(b)分别给出了无
9、向图阴口有向图。的图形表示。图11.1.1例11.1.1无向图篇口有向图。1011.1.2简单图、多重图和同构图11.1.2简单图、多重图和同构图定义11.1.2在无向图中,关联一对顶点的无向边如果多于1条,则称 这些边为平行边,平行边的条数称为重数。在有向图中,关联一对顶 点的有向边如果多于1条,并且这些边的始点与终点相同(也就是他 们的方向相同),称这些边为平行边。含平行边的图称为多重图,既 不含平行边也不含环的图称为简单图。在图H.1.1中,中丹是平行边,在(b)中立与甘是平行边;注意,与。不是平行边。和(b)两个都不是简不图。1111.1.2简单图、多重图和同构图定义11.1.3 设G
10、=匕石为一无向图,三片,称词乍为边的端点 次数之和为曲度数,简记为度,记作gC)在不发生混淆时,简记%”(y)。设。=匕石为看向图,Vv e f,称p作为边的抬点的次数之 和为用勺出度,记作W),简记为人”)。称p作为边的终点的次数之和 为的勺入度,记作W(y),简记为-(以 称2+。)+,。)为附勺度数,记 作 d(v)o _在无向图中,令A(G)=ma xt7(v)|v e 忆(G)5(G)=mind(v)v e P(G)称WG),/G)分别为G的最大度和最小度。在有向图。中,类似可定义 最大度A(G)和最小度3(G)。另外,令A+(G)=ma x+(v)|ve K(G)S+(G)=min
11、 d+(v)|v g K(G)A-(G)=ma x J-(v)|v g K(G)(G)=min|y K(G)分别称为。的最大出度,最小出度,最大入度,最小入度。以上记号可以I。1211.1.2简单图、多重图和同构图分别简记为另外,称度数为1的顶点为悬挂顶点,与它关联的边称为悬挂。度为偶数(奇数)的顶点称为偶度(奇度)顶点。在图11.1.1中,(a)的d(匕)=4(注意,环提供2度),a=4/=是悬 挂顶点,吃是悬挂边。(b)的d+(a)=4,d-=1(环q提供出度L提 供入度 1),d(a)=4+l=5.A=5=3,A+=4(在a点达到),S+=0(在b点 达到),A-=3(在b点达到),5=
12、1(在3和C点达到)。下面给出的定理是欧拉于1736年给出的,常称为握手定理,它是 图论中的基本定理。1311.1.2简单图、多重图和同构图定理 11.1.1 设 G=匕E 为任意图,V=,.-,vn,E=nZ(匕)=2m证 G中每条边(包括环)齿次两个端点,所以加上一条边就使得各结 点的度数之和增加2,因此结论成立。推论ILL 1 任何图(无向的或有向的)中,奇度顶点的个数为偶数。证设G=匕石为任意一图,令匕=y|y 忆a d。)为奇数V2=vv A d(v)为偶数则匕U%=匕匕0匕=(D,由握手定理可知2m=d(v)=(y)+(v)v e K veVx vg2由于2,Z-(v)均为偶数,所
13、以(v)为偶数,但因中顶点度数为奇数,v%veV1所以I匕必为偶数。1411.1.2简单图、多重图和同构图设G=匕为一个阶无向图,忆=22,山称火匕),,。2/(匕)为 G的度数列。对于顶点标定的无向图,它的度数列是相一的。反之,对于给定的非负整数列d=(九七,),若存在以联。为顶点 集的n阶无向图G使得火匕)=,则称d是可图化的。特别地,若所得 的图是简单图,则称d是可简单图化的。例11.1.2(1)(3,5,1,4),(1,2,3,4,5)能成为图的度 数列吗?为什么?(2)已知图G中有15条边,2个度数为4的结点,4个度数为3的结点,其余结点度数均小于等于2,问G中至少有多少个结点?为什
14、么?解(1)由于给定的两个度数列中奇度顶点个数均为奇数,由上述 推论可知,他们都不能成为图的度数列。(2)图中边数为15,由握手定理可知,G中所有结点度数和为30。除去2个度数为4的结点和4个度数为3的结点,还剩下10度。其余结 点度数小于等于2,假设均为2,则至少要5个结点,所以总共至少要1 1个结点。1511.1.2简单图、多重图和同构图定义11.1.4 设。=匕,耳,G2=%,当为两个无向图(两个有向图),若存在双射函数/:两手匕 D匕,匕e匕,(匕,匕)石1(匕,当在攸l)当(/(匕),/(匕)6心(/(匕),/(1彝里2),(匕,一)(匕,匕)与(/(匕),/(%)(匕).7“.)的
15、重数相同,则称G1与G2是同构的,记 作 Gi-。对于同构,形象地说,若图的结点可以任意挪动位置,而边是完全弹性的,只要在不拉断的条件下,一个图可以变形为另一个图,那么这 两个图是同构的。到目前为止,还没有找到判断两个图是否同构的有效方法,还只能根 据定义来判断。需要注意的是,不要将两个图同构的必要条件当成充 分条件。若。=G2,则他们的结点数相同,边数相同,度数列相同,等等,破坏这些必要条件中的任何一个,两个图就不会同构,但以上 列出的条件都满足,两个图也不一定同构。1611.1.2简单图、多重图和同构图例11.1.3证明图11.1.2中(a)和(b)是同构的,(c)和(d)是不同构的。图1
16、1.1.2同构图概念示意图例171L1.2简单图、多重图和同构图 证明:(a)(b)同构。构造结点之间的双射函数f如下:/=a,/(2)=b,/(3)=c,/(4)=d,/=e,/(6)=九/(7)=g,8)=3 容易验证,/满足同构的定义。(C)和(d)不同构。通常证明两图不同构,采用反证法。假设(C)和(d)同 构,并存在双射函数f,则有V和/W)的度数一定相同,因此有3)=d 即(c)中的3和(d)中的d对应。而(c)中的3与一个1度顶点6邻接,而(d)中的d与两个1度顶点邻接,故假设不成立。1811.1.3完全图和正则图 11.1.3完全图和正则图 定义11.1.5设G为n阶无向简单图
17、,若G中每个顶点均与其余的-1 个顶点相邻,则称G为n阶无向完全图,简称n阶完全图,记作k(心1).。设D为n阶有向简单图,若D中每个顶点均与其余的-1个顶点相邻,又邻接于其余的刘-1 个顶点,则称D是n阶有向完全图。设D为n阶有向简单图,若D的基图为n阶无向完全图K,则称D是n阶 竞赛图。在图11.1.3中,(a)为K5,(b)为3阶有向完全图,(c)为4阶竞赛图。图11.1.3无向完全图、有向完全图与竞赛图示意图例1911.1.3完全图和正则图 易知,n阶无向完全图,n阶有向完全图,n阶竞赛图的边数分别为 定义11.1.6设G为n阶无向简单图,若Dv(G),均有d3)=左,则称G 为后-正
18、则图。由定义可知,n阶零图是。-正则图,n阶无向完全图是5-D正则图,彼得松图是3-正则图。由握手定理可知,n阶k-正则图中,边数冽=,因而当k为奇数时,n必为偶数。22011.1.4几种特殊的图图11.1.4给出了几个特殊的图,图11.1.4(a)是星型图S值图 11.1.4(b)是环型图孰,图11.1.4(c)是轮型图叫。星型囱常 用,(22)表示,n是星型图中悬挂点的个数,所以邑的阶数是+1。环型图常用cd 表示,n即是环型图的阶数。轮型图常用”(3)表示,它被看作是在环型图。添加一个顶点,而且把这个新 顶点与。里n个顶点逐个连接后所得的图形,所以。的阶数是+1。这3种图形是局域网经常使
19、用的拓扑模型。使用星型拓扑的局域网,所有其他设备都连接到中央控制设备,消息通过中央控制设备进行传 送;使用环型拓扑的局域网,大家都围绕着环把消息从设备送到设备,直到抵达消息目的地为止;使用轮型拓扑的局域网是一种带冗余的局 域网,消息围绕着环或通过中央控制设备来传送。图11.1.4几种特殊的图2111.1.4几种特殊的图除掉这三个图形外,还有一个特殊图在并行计算的互联网络中经 常用到,它就是超立方体图(用2表示)。它具有2,个顶点,每个顶 点对应一个长度为的n位串,两个顶点相邻,当且仅当它们所表示的位串恰恰相差一位。的顶点数是2,图11.1.5对于=1,2,3的超立方体图22211.1.4几种特
20、殊的图对并行计算的超立方体网络来说,处理器数是 2的幕,而P=2。P个处理器标足成,.i,每 个处理器都有到n不其它处理器的双向连接,处理 器6与下标的二进制表示与i的二进制表示恰恰相 差1位的处理器相连。超立方体网络在每个顶点的 直接连接数与保证处理器通信的中间连接数之间 取得了平衡。已经用超立方体网络建造了许多巨 型计算机,而且用超立方体网络设计了许多并行 算法。2311.1.5子图定义11.1.7设G=匕。=/为两个图(同为无向图或同为有向 图),若/Z EIEyE,则称G是G的子图,G是G的母图,记作G,三G,又若Pu EO u E,则称G是G的真子图,若片=/,则称G是G 的生成子图
21、。设G=*讷一图,匕匚咱匕,称以匕为顶点集,以G中两个端 点都在匕中的边组成边集当的图为G的匕导出子图,记作G因。又 设%u 且&w,称以西为边集,以当中边关联的顶点为顶点集匕 的图为G的E导出的子图,记作,在图11.1.6中,设G如(a)中图表示,取匕=a,仇c,则匕的导出子 图G如(b)中图所示。取4=&-,则用的导出子图GWJ如(c)图 所示。2411.1.5子图(b)251L1.5子图定义11.1.8 设G=/为n阶无向简单图,以厂为顶点集,以所有使G成为完全图K的添加边组成的集合为 边集的图,称为的G补图,记作G o若图G=G,则称G是自补图。在图11.1.7中,(b)与(c)互为补
22、图,(a)是自补图。图11.1.7补图概念示意图例2611.1.6图的操作 定义11.1.9设G=为无向图。(1)设次4用G-e表示从G中去掉边e,称为删除边e。又设Eu E,用G-表示从G中删除中的所有边,称为删 除。(2)设v 匕用G-V表示从G中去掉v及所关联的一切边,称为删除顶点又设片=匕用G-片表示从G中删除中的所有边,称为删除广。(3)设边e=Q#)e及用G/e表示从G中删除e后,将的两个端点并用一个新的顶点。(或用y或硼充当)代替,使/关联e以外#关联 的所有边,称为边e的收缩。(4)设可能相邻,也可能不相邻),用GU3)(G+(#)或)表示在“,V之间加一条边(/V),称为加新
23、边。2711.1.6图的操作I叼图11.1.8图的操作概念示意图例在收缩边和加新边过程中可能产生环和平行边。在图11.1.8中,设中图为G,贝Mb)为G-%,(c)为Ge i,q,(d)为 GVs,(e)为GW,,而(f)为 G/牝。2811.2图的连通性 11.2.1通路与回路G中顶点与边的交替序列厂=%e力匕/e.v.e,匕,为町.的端点,=12,J V分别定义11.2.1设为G无向标定图,称为匕。到匕的通路,其中匕IzJ X V 0 m H J /、I rr-i 7&r/Q,H J J/、,7 7 7,z0 zz 八/j,j成为厂的始点与终点,厂中边的条数称为它的长度,若,=,则称-为简
24、单回路。若厂的所有顶点(除匕。与乙可能相同外)各异,所有边 也各异,则称为初级通路或路径,此时又若匕。=匕,则称,为初 级回路或圈。将长度为奇数的圈称为奇圈,长度为偶数大圈称为偶圈。注意,在初级通路与初级回路的定义中,若将初级回路看成初级通路(路径)的特殊情况,只是在应用中初级通路(路径)都是始点与终点不相 同的,长为1的圈只能由环生成,长为2的圈只能由平行边生成,因而 在简单无向图中,圈的长度至少为3。J j J 2911.2.1通路与回路 另外,若厂中有边重复出现,则称为复杂通路。又若匕。=匕贝口称r 为复杂向廨。在有2图中:通路、回路及分类的定义与无向图中非常类似,只是要 注意有向边方向
25、的一致性。在以上的定义中,将回路定义成通路的特殊情况,即回路也是通路,又初级通路(回路)是简单通路(回路),但反之不真。用顶点与边的交替序列定义了通路与回路,但还可以用更简单的表示 法表示通路与回路。(1)只用边的序列表示通路(回路)。定义11.2中的可以表示成eJ0 eje力。(2)在笥单图中也可以只用顶点序列表示通路(回路)。定义中的.也可以表不成匕匕。(3)为了写出非标定图中的通路(回路),可以先将非标定图标成标定图,再写出通路与回路。3011.2.1通路与回路 定理11.2.1在n阶图G中,若顶点匕到。(匕,匕)存在通路,则从匕到 匕存在长度小于或等于(-1)的通路。证 设厂二%配色V
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 讲义
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【曲****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【曲****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。