第一章(图论的基本概念)

任课教师:陈六新

chenliux@

答疑时间:星期三下午2:30-3:30;地点:数理学院3楼应用数学教学部建议参考书:图论及其算法殷剑宏吴开亚中科大出版社图论及其应用张清华等编清华大学出版社图论与网络流理论,高随祥,高教社通信网图论及应用,刘焕淋,陈勇,人民邮电电网络理论(图论，方程综合)周庭阳,张红岩;械工业出版社

图论导引，（美）DouglasB.West

译李建中，机械工业出版社

1.图论问题的起源

18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”SNAB七桥问题的分析

七桥问题看起来不难，很多人都想试一试，但没有人找到答案.后来有人写信告诉了当时的著名数学家欧拉.千百人的失败使欧拉猜想,也许那样的走法根本不可能.1876年,他证明了自己的猜想.Euler把南北两岸和两个岛抽象成四个点,将连接这些陆地的桥用连接相应两点的一条线来表示,就得到如下一个简图:BANS欧拉的结论欧拉指出:一个线图中存在通过每边一次仅一次回到出发点的路线的充要条件是:1)图是连通的,即任意两点可由图中的一些边连接起来;2)与图中每一顶点相连的边必须是偶数.由此得出结论:七桥问题无解.

欧拉由七桥问题所引发的研究论文是图论的开篇之作,因此称欧拉为图论之父.4.图的作用

图是一种表示工具,改变问题的描述方式,往往是创造性的启发式解决问题的手段.一种描述方式就好比我们站在一个位置和角度观察目标,有的东西被遮挡住了,但如果换一个位置和角度,原来隐藏着的东西就可能被发现.采用一种新的描述方式,可能会产生新思想.图论中的图提供了一种直观,清晰表达已知信息的方式.它有时就像小学数学应用题中的线段图一样,能使我们用语言描述时未显示的或不易观察到的特征、关系,直观地呈现在我们面前,帮助我们分析和思考问题,激发我们的灵感.5.图的广泛应用

图的应用是非常广泛的,在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络,如河道网、灌溉网、管道网、公路网、铁路网、电话线网、计算机通讯网、输电线网等等.还有许多看不见的网络,如各种关系网,像状态转移关系、事物的相互冲突关系、工序的时间先后次序关系等等,这些网络都可以归结为图论的研究对象—图.其中存在大量的网络优化问题需要我们解决.还有象生产计划、投资计划、设备更新等问题也可以转化为网络优化的问题.可化为最短路问题的多阶段决策问题6.基本的网络优化问题

基本的网络优化问题有:最短路径问题、最小生成树问题、最大流问题和最小费用问题.图论作为数学的一个分支,已经有有效的算法来解决这些问题.当然这当中的有些问题也可以建立线性规划的模型,但有时若变量特别多,约束也特别多,用线性规划的方法求解效率不高甚至不能在可忍受的时间内解决.而根据这些问题的特点,采用网络分析的方法去求解可能会非常有效.

例如,在1978年,美国财政部的税务分析部门在对卡特尔税制改革做评估的过程中,就有一个100,000个约束以上，25,000,000个变量的问题,若用普通的线性规划求解,预计要花7个月的时间.他们利用网络分析的方法,将其分解成6个子问题,利用特殊的网络计算机程序,花了大约7个小时问题就得到了解决.

由于后续学习的需要,我们补充离散数学中的一些基本内容:关系与函数.第一章图的基本概念(1)(1)定义1图G是一个三元组,记作其中称为图G的结点集.(2)或是G的边集合,其中或为边。若为称为端点的无向边。为以称为关联函数.若为称为起点，为以为终点的有向边。第一章图的基本概念(2)定义2.邻接结点:关联于同一条边的两个结点.孤立结点:不与任何结点相连接的结点.邻接边:关联于同一顶点的两条边.环:两端点相同的边称为环或自回路.平行边:两个结点间方向相同的若干条边称为平行边或重边.对称边:两端点相同但方向相反的两条有向边.第一章图的基本概念(3)定义3.

无向图:每条边都是无向边的图.有向图:每条边都是有向边的图.混合图:图中不全是有向边,也不全是无向边的图.平凡图:只有一个孤立结点的图.定义4.多重图:含有平行边的图.简单图:无环且无平行边的图.完全图:任何不同结点之间都有边相连的简单无向图.第一章图的基本概念(4)说明:(1)在简单图中,以x为起点y为终点的边至多有一条,因此,图中的边可直接用顶点对表示,而关联函数就可以直接表示在其边集中,故可简记为G=<V(G),E(G)>.(2)对无向图G,将G中的每条边用两条与e有相同端点对称边e和e’来代替后得到一个有向图D,这样得到的有向图D称为G的对称有向图.由此可见,无向图可视为特殊的有向图.(3)n个结点的完全图记为Kn,完全图Kn有条边.完全图的对称有向图称为完全有向图,记作.(4)图G的顶点个数称为图G的阶.(5)对于有向图D,去掉边上的方向得到的无向图G称为D的基础图.反之,任一个无向图G,将G的边指定一个方向得到一个有向图D,称D为G的一个定向图.例证明:在任意六个人的聚会上,要么三个曾相识,要么三个不曾相识.证明:用A,B,C,D,E,F代表这六个人,若两人曾相识,则在代表该两人的顶点间连一条红边;否则连一条蓝边.于是,原问题等价于证明所得图中必含有同色三角形.考察某一顶点,设为F.与F关联的边中必有三条同色,不妨设它们是三条红边FA,FB,FC.再看三角形ABC.若它有一条红边,设为AB,则FAB是红边三角形;若三角形ABC没有红边,则其本身就是蓝边三角形.第二节图的顶点度和图的同构(1)定义1设G是任意图,x为G的任意结点,与结点x关联的边数(一条环计算两次)称为x的度数.记作deg(x)或d(x).

设D是任意有向图，x为G的任一结点，以x为终点的边的条数称为x的入度，记作deg+(x)或d+(x).

以x为始点的边的条数称为x的出度，记作deg-(x)或d-(x).注意：有向图D中，结点x的度deg(x)=deg+(x)+deg-(x)。Δ(G)和δ(G)分别表示G的最大顶点度和最小顶点度，即Δ(G)=max{dG(x)|x∈V(G)};δ(G)=min{dG(x)|x∈V(G)}.有向图D中，记Δ+(G)=max{d+G(x)|x∈V(G)};δ+(G)=min{d+G(x)|x∈V(G)}.

Δ-(G)=max{d-G(x)|x∈V(G)};δ-(G)=min{d-G(x)|x∈V(G)}.第二节图的顶点度和图的同构(1)定义2

设G为无向图,对于G的每个结点x,若d(x)=K,则称G为K正则的无向图.设G为有向图,对于G的每个结点x,若d+(x)=d-(x),则称G为平衡有向图.在有向图G中,若则称G为K正则有向图.定理1(握手定理，图论基本定理)每个图中,结点度数的总和等于边数的二倍,即定理2每个图中,度数为奇数的结点必定是偶数个.第二节图的顶点度和图的同构(2)定理3在任何有向图中,所有结点入度之和等于所有结点出度之和.证明因为每条有向边必对应一个入度和出度,若一个结点具有一个入度或出度,则必关联一条有向边.因此,有向图中各结点的入度之和等于边数,各结点出度之和也等于边数.定义度序列若V(G)={v1,v2,…,vp},称非负整数序列(d(v1),d(v2),…,d(vp))为图G的度序列.第二节图的顶点度和图的同构(3)推论1非负整数序列是某个图的度序列当且仅当是偶数.证明:由定理1知必要性成立.对于充分性取p各相异顶点v1,v2,…,vp,若di是偶数,就在vi处作di/2个环;若di是奇数,在vi处作(di-1)/2个环,由于是偶数,故中由偶数个奇数顶点,从而将所有与奇数di相对应的顶点vi两两配对并连上一条边.最后所得的序列就是.第二节图的顶点度和图的同构(4)图序列:简单图的度序列.定理4非负整数序列是图序列当且仅当是偶数,并且对一切整数k,有定义3设G1=<V1,E1>和G2=<V2,E2>是简单图,若存在一个从V1到V2的双射函数f，且f具有这样的性质,对V1中的所有x和y,x和y在G1中相邻,当且仅当f(x)和f(y)在G2中相邻,就说G1和G2是同构的,记作G1∽G2.例1画出所有不同构的具有5个结点,3条边的简单无向图。例2是否可以画一个简单无向图,使各点度数与下列的序列一致:2,2,2,2,2,22,2,3,4,5,61,2,3,4,4,5第三节图的运算(一）定义1设与是任何两个图.若且是在上的限制,则称是G的子图,记作称G为G1的母图.

若且,则称是G的生成子图或支撑子图.

设,以V1为顶点,以两端点均在V1中的G的边的全体为边集的G的子图,称为V1的导出子图,记作G[V1].设,以E1为边集,以E1中的边关联的全部顶点集的G的子图,称为E1的导出子图,记作G[E1].特别,若,则以G-V1表示从G中删去V1内的所有点以及与这些顶点关联的边所得到的子图,若V1={v},常把G-{v}简记为G-v,类似地,设,G-E1表示在G中删去E1中所有边所得的子图,同样G-{e}简记为G-e.第三节图的运算(二）定义2设G＝<V，E>是n阶无向简单图,以V为顶点集,以所有能使G成为完全图Kn的添加边组成的集合为边集的图,称为G相对于完全图Kn补图,简称G的补图,记作.定义3设G1和G2都是图G的子图.G1和G2的并:仅由G1和G2中所有边组成的图.G1和G2的交G1∩G2:仅由G1和G2的公共边组成的图.G1和G2的差G1-G2:仅由G1中去掉G2中的边组成的图.G1和G2的环和

G1⊕G2:在G1和G2的并中去掉G1和G2的交所得到的图.(见p12)定义4.自补图:若简单图G同构于G的补图,则称G为自补图.(1)证明:自补图的阶数为n=4k或n=4k+1,k为某个自然数.(自己查阅)(2)找出所有4阶和5阶的自补图.例在一次舞会上,A,B两国留学生各n人,A国每个学生都与B国一些学生(不是所有)跳过舞.B国每个学生至少与A国一个学生跳过舞.证明一定可以找到A国两个学生a1,a2及B国两个学生b1,b2,使得a1和b1,a2和b2跳过舞,而a2和b1,a1和b2没有跳过舞.(自己思考)图的运算(三)定义四:设G1和G2是任两个无向图,G1和G2的笛卡儿积为图G=G1×G2,其中G满足:V(G)=V(G1)×V(G2);G中的两顶点<a,b>和<c,d>是邻接的当且仅当a=c且{b,d}∈E(G2)或者b=d且{a,c}∈E(G1).说明:(1)通过图的笛卡儿积运算,可归纳地定义一个重要的图类--n立方体Qn(n1):当n=1,Qn=K2;当n>1,Qn=Qn-1K2.(2)n立方体Qn也可以看作是用顶点表示2n个长度为n的位串图.两个顶点相邻当且仅当它们所表示的位串恰恰差一位.第四节路与连通图(一)定义1设u和v是任意图G的顶点,图G的一条u-v是有限的顶点和边交替序列u0e1u1e2…un-1enun(u=u0,v=un),其中与边ei(1in)相邻的两顶点ui-1和ui正好是ei的两个端点.数n(链中出现的边数)称为链的长度.u(或u0)和v(或un)称为链的端点,其余的顶点称为链的内部点.一条u-v链,当uv时,称它为开的,否则称为闭的.边互不相同的链称为迹,内部点互不相同的链称为路.注释1.(1)在一条链中,顶点和边可以重复.(2)若G是简单图,G中的链u0e1u1e2…un-1enun还可用结点序列u0u1…un-1un表示.(3)不含边的链(即长度为0)称为平凡链.(4)设W是有向图D中u-v链(迹,路),指定W的方向从u到v.若W中所有边的方向与此方向一致,则称W为D中从u到v的有向链(迹,路).第四节路与连通图(二)定义2两端点相同的迹(即闭集)称为回.两端点相同的路(即闭路)称为圈或回路.长度为K,奇数,偶数的回(圈)分别称为K,奇,偶回(圈).有向闭迹(闭路)称为有向回(有向圈).定理1.若简单图G中每个顶点的度数至少是k(k2),则G中必含有一个长度至少是k+1的圈.证明:在G的所有路中,取一条长度最长的路p,记p=v0v1…vt-1vt.则v0的所有邻接点全在p中,由于d(v0)k2,所以v0至少有k个邻接点,设所有邻接点为vi1,vi2,…,vis,1i1i2…ist,其中s=d(v0)k2,则C=v0v1v2…visv0就是G的一个长为is+1的圈,显然is+1k+1.第四节路与连通图(三).定理2

设简单图G中每个顶点的度数至少是3,则G中含有偶圈.证明:在G的所有路中,取一条长度最长的路p,记p=v0v1…vt-1vt.则v0的所有邻接点全在p中,设v0的所有邻接点为vi1,vi2,…,vis,1i1i2…ist,其中s=d(v0)3,在G中取三个圈c1=v0v1…vi2v0,c2=v0v1…visv0,c3=v0vi2vi2+1…visv0,它们的长度分别为i2+1,is+1和is-i2+2.这三个数中至少有一个是偶数.即c1,c2,c3中至少有一个是偶圈.定义3给定无向图G=<V(G),E(G),(G)>,x,y∈V(G),若图中存在连接x和y的路,称节点x和y是连通的.规定x到自身总是连通的.说明：容易验证,结点集V(G)上的顶点间的连通关系是V(G)上的一个等价关系,该等价关系确定V(G)的一个划分{V1,V2,…,Vm},使得当且仅当两个顶点x和y属于同一子集Vi时,x和y才是连通的.第四节路与连通图(四)Vi在G中的导出子图G[V1],G[V2],…,G[Vm]称为G的连通分支或分支,m称为G的连通分支数,记作W(G)=m.如下图有4个连通分支.定义4.如果无向图G中每一对不同的顶点x和y都有一条路,即W(G)=1,则称G是连通图,反之称为非连通图.[S,T]＝{e|e∈E(G),e的两个端点分别在S和T中}，其中T=V-S。引理1非平凡图G是连通图当且仅当对V(G)的每一个非空真子集S,[S,S’]≠Ф,S’=V-S.第四节路与连通图(五)定理3设G是P阶连通图,则证明:只需证明连通的简单图成立即可.设悬挂点:度数为1顶点.第四节路与连通图(六)定理4

设连通图G至少有两个顶点,其边数小于顶点数,则此图至少有一个悬挂点.证明:设图G是满足条件的P阶图.反设图G没有悬挂点,由于G是连通图,故每个顶点的度数至少为2,即对每个顶点v,d(v)2,故,与矛盾.定理5设简单图G的结点序列为.度数依次是d(v1)≤d(v2)≤…≤

d(vp),如果对任意的则G是连通图.证明:反设G不连通,令G1是G中不含vp的一个连通分支,而G2是G中含vp的一个连通分支,则G2至少有个顶点,且

第四节路与连通图(七)则由已知.若记则,则与矛盾.推论1设G是P阶简单图,每个顶点的度至少是[P/2],则G是连通图.定义5设是有向图,,若图D中存在x到y的有向路,称结点x可达结点y.

规定x到自身总是可达的.定义6

设G是有向图,任何结点间,至少有一个结点可达另一个结点,则称该有向图是单侧连通的.如果有向图D的任何一对结点间是相互可达的,则称该有向图是强连通的.若有向图G的基础图是连通的,则称该有向图D是弱连通的.定义7

设G是有向图,,G中所有从x到y的有向路的最小长度称为从x到y的距离.定义8

设G是无向图,,G中所有从x到y的路的最小长度称为从x到y的距离.称为图G的直径.

第五节连通图和二分图(1)定义1如果在图G中删去一个结点x后,图G连通分支数增加,即W(G-x)>W(G),则称结点x为G的割点.

如果在图G中删去一条边e后,图G的连通分支数增加,即W(G-e)>W(G),则称边e为G的割边.定义2没有割点的非平凡连通图称为块.G中不含割点的极大连通子图称为图G的块.定义3如果G的顶点集的一个真子集T满足G-T不连通或是平凡图，任意T的真子集T’,而G-T’是连通的,则称T为G的一个点割.如果图G的边集的一个真子集S满足G-S不连通或是平凡图，任意S的真子集S’满足G-S’是连通的,则称S为G的一个边割.定义4设G是连通图,称是G的点割}为G的点连通度或连通度;称是G的边割}为G的边连通度.定理1

对一个图G,有是图G的最小顶点度.(不证)证明:若G不连通,则结论成立.若G连通.(1)先证设x是G中度数最小的顶点,即.设所有与关联的边集为S(x),显然x是G-S(x)的一个孤立点.所以(2)再证当时,显然假设对所有的图G有设

S是H的一个边割,且若边易知故由假设知并设T是H-e的一个点割,且此时,就是H的一个点割,即

K(H)≤︱T∪{u}︱≤n+1=（H）.

再由归纳假设即知K(G)≤（G）结论成立.第五节连通图和二分图(3)定义5如果无向图G的连通度称图G是n连通的或G为n连通图.若称图G是n边连通的或G为n边连通图.定理2设图G是n连通的,则对(反证)定理3设G是2边连通图,则G有强连通的定向图.证明:设G是2边连通图,则G必含有圈.先取一个圈C1,定义G的连通子图序列G1,G2,…如下:G1=C1;若Gi(i=1,2,…)不是G的生成子图,设vi是在G中而不在Gi中的一个顶点,则存在从vi到Gi的边不重路Pi和Qi,定义由于该序列必终止于G的一个生成子图Gn.依次对每个Gi定向:首先让G1的定向图成为一个有向圈;对设已有定向图,让Pi成为以vi为始点的有向路,而Qi成为以vi为终点的有向路,得,即是强连通图i=1,2,…n.第五节连通图和二分图(4)

因此,最后的是强连通有向图.由于Gn是G的生成子图,所以G有强连通的定向图.

一个图G有强连通的定向图的必要条件是G为2边连通的.否则G有割边,这与G有强连通的定向图矛盾.定义6把简单图G的顶点集合分成两个不相交的非空集合V1,V2,使得图G中的每一条边,与其关联的两个结点分别在V1和V2中,则G称为偶图或二分图,记作G=<V1,V2,E>,其中V1和V2叫做G的二划分.

对于二分图G=<V1,V2,E>,若,V1中的任意一点与V2中的所有点相邻且V2中的任意一点与V1中的所有点相邻,则称该图为结点m和n的完全偶图或完全二分图,记作Km,n.例1试说明n立方体Qn是二分图.证明:不妨设由Qn的定义知Qn是简单图.假定则边,即两结点序列恰差一位.令显然.而且,若存在即与矛盾.所以X中任何两顶点之间无边相连.同理可证Y中任何两顶点之间也无边相连.因此Qn是二分图.定理4非平凡图G是二分图当且仅当G中不含有长为奇数的圈.证明:(→)设G是一个二分图,G的二分为V1和V2,则G[V1]和G[V2]为零图.设v=v1v2…vkv1是G中长度为k的一个圈.下证k为偶数.不妨设由于v2和v1相邻,故;同样有又最后一个顶点是v1,故k必为偶数.(←)不妨设G中每一对点之间有路连接(否则只考虑G的每个每一对点之间有路连接的极大子图).任取G的一个顶点u,由G的假设,对G的每个顶点v,在G中存在u-v路.现利用u对G的顶点进行分类.设

显然,.由于G中不存在长度为奇数的圈,所以对任意一个点v,G中所有从u到v的路的长度都有相同的奇偶性,因而由G的假设,现对G的每一条边e={u1,u2},若u1,u2都在V1上,则存在两条路P1与P2分别连接u与u1和u与u2,且P1与P2的长度均为偶数,闭链的长度为奇数,故G中有一条长为奇数的圈,矛盾.同样u1和u2不能同时在V2中.故e的两个端点分别在V1和V2中.因此G是二分图.第六节图的矩阵表示(1)1.邻接矩阵:设是有向图,其中V={x1,x2,…,xn},E={e1,e2,…,em},则n阶方阵A=(aij)称为G的邻接矩阵.其中aij为图G中以xi为起点且以xj为终点的边的数目。若G是无向图，aij为图G中以xi和xj为端点的边的数目.说明1:由定义易知,无向图的邻接矩阵是对称矩阵,而有向