离散数学讲义之图论.pdf

离散数学讲义之图论主讲:熊焕亮图论简介图论(g ra p h the o ry)是研究节点和边组成的图 形的数学理论和方法，为离散数学的一个重要分 支。图论的基本元素是节点和边(也称线、弧、枝)，用节点表示所研究的对象，用边表示研究 对象之间的某种特定关系。因此，图论可用节点 和边组成的图形及其有关的理论和方法来描述、分析和解决各种实际问题，已广泛地应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、管理科学、社会科学等几乎 所有学科领域的有关问题。图论与组合数学、线 性规划、群论、矩阵论、概率论、数值分析等数 学分支有密切的关系。J J J 2图论简介图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图 形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连 接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学 的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在瑞士数学家欧拉(Le o n ha rd Eul a r)1736年的论文中，解决了著名的哥尼斯保七桥问题。因此通常认为欧 拉是图论的创始人。1845年，德国物理学家基尔霍夫为了解决一类线性联立方程组而创建“树”理论。他把电网络和其中的电阻、电容和电感等抽象化，用一 个只有点和边组成的组合结构来代替电网络，而不指明每条边所代表 的电器元件种类，这样就可以方便地对方程组进行求解。1852年，格思里在对地图着色时发现，无论多么复杂的地图，只要用四 种颜色就能将相邻区域区分开来。这就是所谓“四色猜想”。经过百 余年的努力，直到1976年才由阿佩尔和赫肯借助电子计算机证明了四 色定理。t S3图论简介 1856年，哈密顿在给格雷夫斯的信中提出一个游戏：用正十二面体 上20个顶点表示20个城市，要求游戏者沿着各边行走，走遍每个城 市一次且仅一次，最后回到原出发城市。这个游戏促使人们研究如 何判断一个图有无这一性质，如果有，则又如何确定这样的路径，即称之为哈密顿图。这是一个至今尚未完全解决的问题。1962年，中国数学家管梅谷提出一个所谓“中国邮路问题”：邮递员 带着邮件从邮局出发，走遍他所管辖的每一条街道，最后回到邮局,如何选择路线，使走的路程最短。1967年，埃德蒙兹给出中国邮路 问题一个好的解法。图论虽有200年的历史,但受计算机科学发展的刺激，发展极其迅速。上世纪60年代以来图论在各种学科领域中得到了广泛应用。图论在 理论上也得到了新的发展，如图特等发展了拟阵理论，贝尔热等发 展了超图理论，埃尔德什等发展了极图理论等。本书介绍图的基本概念、路与回路、图的矩阵表示、欧拉图与汉密 尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用、二 部图、匹配等。各章节主要知识点关联如图4.0.0所示。t S4图4.0.0第四部分各章节主要知识点关联图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 图的运算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图的概念现实世界中许多现象都可以用某种图形表示，这 些图形由一些点和连接两点间的连线所组成，点 表示事物，用点与点之间是否有连线表示事物之 间是否有某种联系，这样构成的图形就是图论中 的图。711.1图的概念 11.L1无向图和有向图 定义1LL1 一个图是一个有序的二元组 匕石，记作G,其中(。/=匕,刈,一是有限非空集合，称为顶点集，其元素称为顶点o 屯：石工4，/4一，。是有限集合，称为边集，石中每个元素都有口中 的结点对与之对应，称为边。定义1L1.1中的边e既可以是有向的，也可以是无向的。有向边与有序 结点对 弟应,这时所为e的起点，历e的终点。无向边与无序结点舟。力对应，了称为e的两个端点。(3)将图的集合定义转化成图形表示之后，常用外表示图的遮,.),称顶点或边用字母标定的图为标定图，否则称为非标定图。(4)将有向图各有向边均改成无向边后的无向图称为原有向图的基图。(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)分别给出了无向图阴口有向图。的图形表示。图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=匕石为一无向图，三片，称词乍为边的端点 次数之和为曲度数，简记为度，记作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 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=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)均为偶数，所以(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中至少有多少个结点？为什么？解(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“.）的重数相同，则称G1与G2是同构的，记 作 Gi-。对于同构，形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，一个图可以变形为另一个图，那么这 两个图是同构的。到目前为止，还没有找到判断两个图是否同构的有效方法，还只能根 据定义来判断。需要注意的是，不要将两个图同构的必要条件当成充 分条件。若。=G2,则他们的结点数相同，边数相同，度数列相同，等等，破坏这些必要条件中的任何一个，两个图就不会同构，但以上 列出的条件都满足，两个图也不一定同构。1611.1.2简单图、多重图和同构图例11.1.3证明图11.1.2中(a)和(b)是同构的，(c)和(d)是不同构的。图11.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阶无向简单图，若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 为后-正则图。由定义可知，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种图形是局域网经常使用的拓扑模型。使用星型拓扑的局域网，所有其他设备都连接到中央控制设备，消息通过中央控制设备进行传 送；使用环型拓扑的局域网，大家都围绕着环把消息从设备送到设备，直到抵达消息目的地为止；使用轮型拓扑的局域网是一种带冗余的局 域网，消息围绕着环或通过中央控制设备来传送。图11.1.4几种特殊的图2111.1.4几种特殊的图除掉这三个图形外，还有一个特殊图在并行计算的互联网络中经 常用到，它就是超立方体图（用2表示）。它具有2,个顶点，每个顶 点对应一个长度为的n位串，两个顶点相邻，当且仅当它们所表示的位串恰恰相差一位。的顶点数是2，图11.1.5对于=1,2,3的超立方体图22211.1.4几种特殊的图对并行计算的超立方体网络来说，处理器数是 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 的生成子图。设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）互为补图，（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),称为加新边。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成为厂的始点与终点，厂中边的条数称为它的长度，若，=，则称-为简单回路。若厂的所有顶点（除匕。与乙可能相同外）各异，所有边 也各异，则称为初级通路或路径，此时又若匕。=匕，则称,为初 级回路或圈。将长度为奇数的圈称为奇圈，长度为偶数大圈称为偶圈。注意，在初级通路与初级回路的定义中，若将初级回路看成初级通路（路径）的特殊情况，只是在应用中初级通路（路径）都是始点与终点不相 同的，长为1的圈只能由环生成，长为2的圈只能由平行边生成，因而 在简单无向图中，圈的长度至少为3。J j J 2911.2.1通路与回路 另外，若厂中有边重复出现，则称为复杂通路。又若匕。=匕贝口称r 为复杂向廨。在有2图中:通路、回路及分类的定义与无向图中非常类似，只是要 注意有向边方向的一致性。在以上的定义中，将回路定义成通路的特殊情况，即回路也是通路，又初级通路（回路）是简单通路（回路），但反之不真。用顶点与边的交替序列定义了通路与回路，但还可以用更简单的表示 法表示通路与回路。（1）只用边的序列表示通路（回路）。定义11.2中的可以表示成eJ0 eje力。（2）在笥单图中也可以只用顶点序列表示通路（回路）。定义中的.也可以表不成匕匕。（3）为了写出非标定图中的通路（回路），可以先将非标定图标成标定图,再写出通路与回路。3011.2.1通路与回路 定理11.2.1在n阶图G中，若顶点匕到。（匕，匕）存在通路，则从匕到 匕存在长度小于或等于（-1）的通路。证 设厂二%配色V（%=匕，匕=匕）为G中一条长度为/的通路，若1,则满足要求，否则必有/+金，即厂上的顶点数大于G中 的顶点数，于是必存在左/,0 Ws 使得匕=。，即在厂上存在匕到 自身的回路 盘上的一切边及除匕外的一切顶点,，得厂二v0elvle2-vkes+l-vlel 厂任为匕。到匕的通路，且长度至少比厂减少1.若万还不满足要求，则重 复上述过程，由于G是有限图。经过有限步后，必得到匕。到匕长度小 于或等于-1的通路。推论1121在n阶图G中，若存在匕到%（匕一）存在通路,则匕到,一定存在长度小于或等于-1的初级通路（路径）。定理1L2.2在一个n阶图G中，若存在匕到自身的回路,则一定存在匕 到自身长度小于或等于n的回路。推论11.2.2在一个n阶图G中，若存在匕到自身的简单回路，则一定 存在长度小于或等于n的初级回路。J J J 3111.2.1通路与回路 例1121无向完全图K（3）中有几种非同构的圈？解长度相同的圈都是同构的，因而只有长度不同的圈才是非同构的，易知KG 2 3）中含长度为3,4,，的圈，所以陌（心3）中有-2种非同构 的圈。例11.2.2 无向完全图&的顶点依次标定为在定义意义下K3中有多少个不同的圈？解在同构意义下，&中只有一个长度为3的圈。但在定义意义下，不 同起点（终点）的圈是不同的，顶点间排列顺序不同的圈也看成是不同 的，因而K3中有6个不同的长为3的圈：反。由bca仇 如果只考虑起点（终点）的差异，而不考虑顺时针逆时针的差异，应该 有3种不同的圈，当然它们的长度都是3。3211.2.2连通图 1122连通图 定义1122设无向图G=J若,v之间存在通路，贝IJ 称u,v是连通的，记作M y,VvgK,规定M y。由定义不难看出，无向图中顶点之间的连通关系=U,V G/且M与y之间有通路,显然是自反的，对称的，传递的，因而是口上的等价关系。定义11.2.3若无向图G是平凡图或G中任何两个顶点都是连通的，则 称G为连通图，否则称G为非连通图或分离图。易知，完全图显(之1)都是连通图，而零图孤(2 2)都是分离图。定义11.2.4设无向图G=,关于顶点之间的连通关系的商 集/二化,修，,右,匕为等价类，称导出子图G叩”1,2,肉为G的 连通分支，连通分支数左常记为MG).。由定义可知，若G为连通图，则P(G)=1,若G为非连通图，则口3)22 在所有的n阶无向图中，n阶零图是连通分支最多的，p(M)=。3311.2.2连通图例11.2.2判断图11.2.1中图Gi和G2的连通性，并求其连通分支数。图11.2.1例11.2.2示意图解：容易看出。是连通图，所以P（。）=1,G?是非连通图，连通关系的 受着奥（IV解微vV5,匕#8,%，%（），它们的导由的子图为 2的33411.2.2连通图 定义11.2.5设。=匕石,为一个有向图，产匕若从匕到存 在通路，则称匕可达匕，记作匕-V规定匕总是可达自身的，即匕f vz.。若匕匕且匕.匕，则球V.与V,是相互可达的，记 作匕一匕，规定匕妗匕。与一都是厂上的二元关系，并且不难看出一是厂上的等价关系。定义11.2.6设。=匕为一个有向图，若。的基图是连通图，则称 是。弱连通图，简称为连通图，若Dv/j 匕匕匕与匕一匕至少 成立其一，则称。是单向连通图，若均有匕，则称。是强连通图。3511.2.2连通图 在图11.2.2中，（a）为强连通图，（b）为单向连通图，（c）为弱连通图。由定义可知，强连通图一定是单向连通图，单向连通图一定是弱连通 图。下面给出强连通图与单向连通图的判别定理。定理11.2.3设有向图。=,厂=，匕.。是强连通图当且仅当。中存在经过每个顶点至少一次回路。证 充分性显然。下面证明必要性。由的强连通性可知匕-匕+1，=1,21设为匕到匕+i的通路。又因为匕-%,设 为乙到匕的通路,则4 所围成的回路经过刀中每个顶点至少一次。3611.2.2连通图 定理11.2.4设O是n阶有向图，。是单向连通图当且仅当。中存在经 过每个顶点至少一次的通路。下面介绍一种证明方法，叫“扩大路径法”。设6=匕为11阶无向图，石*协,设乙为G中的一条路径，若此路径 的始点或终点与通路外的顶点相邻，就将它们扩到通路中来，继续这 一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止,设最后得到的路径为（抬度为的路径扩大成了长度为 的路径），称/为“极大路径”，称使用此种方法证明问题的方法为“扩 大路径法”。3711.2.2连通图 例11.2.3设G为(4)阶无向简单图，况G)2 3,证明G中存在长度大于 或等于4的圈。证不妨设G是连通图，否则，因为G的各连通分支的最小度也都大 于或等于3,因为可对它的某个连通分支进行讨论。设并为G中任意 两个顶点，由G是连通图，因而力之间存在通路，由定理11.2.4的推 论可知，#之间存在路径，用“扩大路径法”扩大这条路径，设最 后得到的“极大路径T为%匕，易郑.。若与相领则心，匕)为长度大于或等于4的圈。否则，由于(%)2 5(G)2 3,因而除与口上 的匕相邻外,还存在厂/上的顶点也(左W1)和匕(左)与相邻，则%以匕为一个圈且长度大于或等于4,见图11.2.3。3811.2.2连通图图11.2.3例11.2.3示意图定义1127设图G=匕石,若存在七瓦且E w。，使得p(g*)p(g)而对于任意的石u Z,均有p(G-尸)=p(G),则称E是G的边割集,简 称为割集。若为单元集，即E=e,则称e为割边或桥。3911.2.3 二部图 11.2.3 二部图 定义1126设G=匕石为一个无向图，若能将卜分成匕和匕(匕U%=使得G中的每条边的两个端点都是一个属于匕，另一个属于右,则称G为二部图(或称二分图，偶图等)，称匕和为互 补顶点子集，常将二部图G记为匕匕1,又若G是简单的二部图，匕 中每个顶点均与匕中所有顶点相邻，则称G为完全二部图，记为K其/=|匕|,s=|七|.注意，阶零图为二部图。,在图11.2.4中所示各图都是二部图，其中，(a),(b),(c)为K6的子图，(c)为完全二部图3,常将犬3,3画成与其同构的(e)的形式，犬3,3是下文 中经常遇到的图。(d)是凤的子图，它是完全二部图K2,3,3常画成(f)的形状。4011.2.3 二部图11.2.3 二部图 一个图是否为二部图，可由下面定理判别。定理11.2.5 一个无向图g=,是二部图当且仅当G中无奇数长度 的回路。证 必要性。若G中无回路，结论显然成立。若G中有回路，只需证 明G中无奇圈。设C为G中任意一圈，令。=匕/匕,匕，易知/N2.不妨设匕匕，则必有匕忆-匕=匕,而/必为偶数，于是C为偶圈，由C的任意性可知结论成立。充分性，不妨设G为连通图，否则可对每个连通分支进行讨论，设/为G中任意一个顶点，令匕=小 K(G)a d(%#)为偶数%=v|v P(G)a(#)为奇数4211.2.3 二部图 易知，匕匕n%=a匕u%=/（g）.。下面只要证明匕中任意两 顶点不相邻，匕中任意两顶点也不相邻。若存在匕,金匕相邻，令（匕，为）=e，设到匕，匕的短程线分别为乙,G，则它们的长度，都是陶数）乎是0，匕）中一定含削圈U/与已知矛盾，类似可证，中也不存在相邻的顶点，于是g为二部图。由定理11.2.5可知，图11.2.4中各图都是二部图，这比用定义判断更 方便。4311.3图的矩阵表示在学习中常常需要分析图并在图上执行各种过程和算法，有时必须用 计算机来执行这些算法，因此必须把图的结点和边输入给计算机，由于 集合与图形都不适合计算机处理，所以要找到一种新的表示图的方法，这就是图的矩阵表示。I 11.3.1关联矩阵 定义1131 设无向图G=匕石,/=匕#2，：匕，=但1，62，一，一,令m.为顶点匕与ej 作Mg。为G的关联矩阵，记边的关联次数，则称（加，曲图11.3.1图例441131关联矩阵图11.3.1所示无向图的关联矩阵为(2M(G)=(01110、110 0 0 0 110 0 0 00不难看出，关联矩阵M(G)有以下性质:4511.3.1关联矩阵n(1)=2()=1,2,，办即M(G)每列元素之和均为2,这正说明每条边关联两个顶点(环所关联的两个端点重合)。百=(匕)，即M(G)第i行元素之和为匕的度数1=1,2,，几 f n m m n m(3)2：=2m,这个结果正是握手定理的内容，即各顶点而度数乏相等于力数的2倍。(4)第j列与第k列相同，当且仅当边J与4是平行边，m(5)Z爪=。当且仅当匕是孤立点。4611.3.1关联矩阵定义11.3.2 令设有向图G=中无环，展匕心#.，石=k，2，,：分，L，为的始点 m.=0,匕与e 7.不关联 IJ I J11，？.是？的终点 I J J 则称（mij）nxm4711.3.1关联矩阵图11.3.2所示图D的关联矩阵为(-1 1 0 0 0、0 1 1 1M(D)有如下各条性质：X1 Y m n(1)2%=。，/=1，2,“从而EZ吗=。，这说明M0)中所有元素之和为O 曰(2)(D)中，负1的个数等于正1的个数，都等于边数m,这正是有向图握手定理的内容。(3)第行中，正1的个数等于二(匕)，负1的个数等于*(匕).。(4)平行边所对应的列相同。4811.3.2邻接矩阵 11.3.2邻接矩阵定义1L3.3 设有向图G=,，=4#2,#=%电，/，令端）为定点匕邻接到定点匕边的条数，称（*）访D的邻接矩阵，记作43,或简记为.A。图1L3.3图例4911.3.2邻接矩阵图11.3.3所示有向图D的邻接矩阵为有向图的邻接矩阵有以下性质:A=勺210、0010000101b却+（匕），于是沼*=J（匕）=私类似地1小 而士宜*这也正反赧了有向图握手定理的内容。=。一（匕），）=1,2,.肃（1）不嘘看出，4。）中所有元素之和为D中长度为1的通路数，而七成）为D中长度为1的回路（环）的个数。i=l 现在要求讨论的问题是，如何利用4。）计算出D中长度为/的通路数和回路数。在这里通路是定义意义下的概念，不同起点的通路都看成是不同的，并且回路看成是通路 的特殊情况。为了解决提出的问题，要计算/（。）的幕，把/次幕记作4（。）或简记 作/。设4=（城限（/之2）,其中元素犷4，则端为顶点匕至心长度为/的通路数,当 怕/即 力的崖对角线上的元素）为 到 张度为 的通路总数，其中，为D中的长度为/的回路总数，从以上分析可得出下面定理和推论。501132邻接矩阵定理11.3.1设A为有向图D的邻接矩阵，展%,%,一 为D的顶点集，则A的/次幕卬（和1）中元素端）为D 中匕到匕长度为i的通路数，其中球为匕到自身长 度为/的回路数，而窈*为D中长度为/的通路总 数，其中沙为D中长度为/的回路总数。推论11.3.1设氏一+1+/仆1），则%中元素窈斗为 D中长度小于或等于/的通路数，其中疑为D中长 度小于或等于的/回路数 1511132邻接矩阵前面已经计算出图11.3.3所示有向图D的邻接矩阵A,下面给出 a2,a3,a4.：IA2,0 0 2 1、0 0 0 10 0 110 0 12/(0 0 13、A4,0 0 3 4、0 0 120 0 2 30 0 3 5,(0 0 2 3J从/I/4不难看出，D中V2到！长度为1,2,3,4 的通路分别为0,1,1,2条。匕到自身长度为L 2,3,4的回路分别为1,2,3,5条，其中有复 杂回路。D中长度小于或等于4的通路53条，其中 有15条为回路。1 d5211.3.3可达矩阵定义11.3.4设。=为有向图，联,叫，令1,匕可达V.Pi j=1o,否则称（Pij）nxn为D的可达矩阵，记作户（。），简记为P。由于V匕匕匕一匕，所以尸（。）主对角线上的元素全为l o记图1132和图1133所示有向图可达矩阵分别为月和6,则rl 1 0 PU 1 1 1、110 10 111尸 1=舄=0 0 110 0 11(0 0 0 1,(0 0 11,由定理1124和定理11.3的推理给出的名可知，只要计算出8_1，由中的元素（；/=1,24一,且/）是否为0就可以写出有向图Z）的可达矩阵，不过见 总为 1（力=1,2,川,它不由6俨的值确定。5311.4图的运算定义11.4.1设d=,G2=为两个图。若匕=。,则称Gi与G2 不交的，g n52=。,则称d与g.是边不交的或边不重的。I 由定义可知，不交的图，必然是边不交的，但反之不真。定义11.4.2设G1=,G2=为不含孤立点的两个图(它们同为无向 图或同为有向图)。J(1)耳11石2为边集，以g U2中边关联的顶点组成的集合为顶点集的图为G1与G2的并图，记作G1UG2。(2)与-4为边集，以与-当中边关联的顶点组成的集合为顶点集的图为Gi与G21 的差图，记作GG2。(3)g n 2为边集，以与0石2中边关联的顶点组成的集合为顶点集的图为Gi与的交图，记作G1DG2。(4)44(为集合之间的对称差运算)为边集，以4石2中边关联的顶点组成 的集合为顶点集的图为G1与G2的环和,记作g石2。)。5411.5欧拉图定义1L5.1设是无孤立结点的图，若存在一条通 路（回路），经过图中所有边一次且仅一次称为 欧拉通路（回路）。具有欧拉回路的图称为欧拉 图，具有欧拉通路而无欧拉回路的图称为半欧拉图O在这里做个规定,即平凡图是欧拉图。5511.5.1欧拉通路和回路图11.5.1欧拉图概念示意图例5611.5.1欧拉通路和回路在图11.5.1所示各图中,ee2e3e 5 为(a)中的欧拉回路,所以(a)图为欧拉图 o 色？3?4%为(b)市的欧拉通路，但图中不存在欧拉回路，所以(b)为半欧拉图。(c)中既没有欧拉回路，也没有欧拉通路，所以(c)不是 欧拉图，也不是半欧拉图。的24。4%(1)图中的欧斑 回路，所以(d)图为欧拉图。(e),(f)图中都既没有欧 拉回路，又没有欧拉通路。5711.5.2半欧拉图和欧拉图 定理11.5.1无向图G是欧拉图当且仅当是G连通 图，且G中没有奇度顶点。证若G为平凡图，结论是显然成立,下面设G为非平 凡图，设G是m条边的n阶无向图.并设的顶点 集-=%，%，匕 O 必要性。因为G为欧拉图，所以G中存在欧拉回路,设C为G中任意一条欧拉回路,一匕匕,匕都在C上，因而匕连通，所以G为连通图。又在C上 每出现一次获得2度,若出现k次就获得2k度，即（匕）=2左,所以G中无奇度顶点。1 s d5811.5.2半欧拉图和欧拉图充分性。由于G为非平凡的连通图可知，G中边数加21.对加作归纳法.(1)加=1时，由G的连通性及无奇度顶点可知，G只能是一个环，因而G为欧拉图.(2)设加4左(左21)时结论成立,要证明加二左+1时,结论也成立。由G的连通性及无 奇度顶点可知,5(G)22.无论G是否为简单图,都可以证明G中必含圈，设。为G中一个圈 删除C上的全部边，得G的生成子图G，设G有s个连通分支G；,G；,，每个连通分支 至多有左条边，且无奇度顶点,并且设G与。的公共顶点为匚，.由归纳假设可知，都是欧拉 Ji图,因而都存在欧拉回路C，1=1,2,S.。最后将。还原(即将删除的边重新加上)，并从C 上的某个点匕开始行遍，每遇到匕,就行遍G中的欧拉回路C,%=1,2,s,最后回到匕碧 到回路匕v：V：?；/匕，此回路经过G中每条边且一次且仅一次并行 r J1 h 72 72 Js Js rG中所有顶点，因而它是G中的欧拉回路(见示意图1152)，故G为欧拉图。5911.5.2半欧拉图和欧拉图图11.5.2图例由定理1151立刻可知，图1151中的三个无向图中，只 有（a）中无奇度顶点，因而（a）是欧拉图，而（b）,（c）都是奇度顶点，因而它们都不是欧拉图。136011.5.2半欧拉图和欧拉图定理11.5.2无向图G是半欧拉图当且仅当是G连通的，且G中恰有两个 奇度顶点。证必要性。设G是m条边的n阶无向图，因为为半欧拉图，因而G中存在 欧拉通路（但不存在欧拉回路），设厂二心%匚碎加“为中一条欧 拉通路，%若V不在厂的端点出现，显然4。）为偶数，若V在端点出现，则d3）为奇数，因为只有两个端点且不同，因而G中只有 两个奇度顶点。另外,G的连通性是显然的。充分性。设G的两个奇度顶点分别为。和%，对G加新边（劭,）,得GJGUQ。,%）,则G是连通且无奇度顶点的图,由定理U51可知，G 为欧拉图，因而存在欧拉回路。，而C=C-（劭，）为中一条欧拉通路，所 以为半欧拉图。由定理11.5.2立即可知，图11.5.1中（b）是半欧拉图，但（c）不是半欧拉 图。6111.5.2半欧拉图和欧拉图 定理11.5.3有向图D是欧拉图当月仅当D是强连通 的且每个顶点的入度都等于出度。定理11.5.4有向图D半欧拉图当且仅当D是单向 连通的，且D中恰有两个奇度顶点，其中一个的入度 比出度大L另一个的出度比入度大L而其余顶点的 入度都等于出度。由定理1153和1154立即可知，图1151中所示 三个有向图中只有（d）是欧拉图，没有半欧拉图.6211.5.2半欧拉图和欧拉图(a)(b)(c)图11.5.3图例I 由定理H.5.1立即可知图11.5.3(a)为欧拉图，本图既可以看成圈匕丫2y，v2v3v4v2,匕y5 y6 V4#6 y7 y8匕之并(为清晰起见,将四个圈画在S)中)，也可看成圈匕匕匕匕5 y6 y7%与圈V2 y4 V6 V8 V2之并(两个圈画在(。)中)。将(。)分解成若干个边不重的圈的并不是(a)图特有性质,任何欧拉图都有这个性质。h*-I 6311.5.2半欧拉图和欧拉图 定理11.5.5G是非平凡的欧拉图当且仅当G是连通 的且为若干个边不重的圈的并。本定理的证明可用归纳法。例11.5.1设G是非平凡的且非环的欧拉图，证明：(1)2(G)2o(2)对于G中任意两个不同顶点，匕都存在简单 回路C含u和V。6411.5.2半欧拉图和欧拉图证(1)由定理11.5.5可知。Ve e(G),存在圈C,e在。中，因而夕(G e)二?(G),故e不是桥。由e的任