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

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

2、导引图论导引，（美）Douglas B. West 译译 李建中李建中 ，机械工业出版，机械工业出版社社 1. 1.图论问题的起源图论问题的起源v 18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”S SN NA AB B七桥问题的分析v 七桥问题看起来不难，很多人都想试一试，但没有人找到答案.后来有人写信告诉了当时的著名数学家欧拉.千百人的失败使欧拉猜想,也许那样的走法根本不可能.1876年,他证明了自己的猜想.v Euler把南北南北两岸和两个岛两个岛抽象成四

3、个点,将连接这些陆地的桥用连接相应两点的一条线来表示,就得到如下一个简图:BANS欧拉的结论欧拉的结论v欧拉指出欧拉指出:一个线图中存在通过每边一次仅一个线图中存在通过每边一次仅一次回到出发点的路线的充要条件是一次回到出发点的路线的充要条件是:v1)图是连通的图是连通的,即任意两点可由图中的一些即任意两点可由图中的一些边连接起来边连接起来;v2)与图中每一顶点相连的边必须是偶数与图中每一顶点相连的边必须是偶数.v由此得出结论由此得出结论:七桥问题无解七桥问题无解. 欧拉由七桥问题所引发的研究论文是图论欧拉由七桥问题所引发的研究论文是图论的开篇之作的开篇之作,因此称欧拉为图论之父因此称欧拉为图论

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

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

6、径问题、最小生成最短路径问题、最小生成树问题、最大流问题和最小费用问题树问题、最大流问题和最小费用问题. 图论作为数学的一个分支,已经有有效的算法来解决这些问题.当然这当中的有些问题也可以建立线性规划的模型,但有时若变量特别多,约束也特别多,用线性规划的方法求解效率不高甚至不能在可忍受的时间内解决.而根据这些问题的特点,采用网络分析的方法去求解可能会非常有效. 例如,在1978年,美国财政部的税务分析部门在对卡特尔税制改革做评估的过程中,就有一个100,000个约束以上，25,000,000个变量的问题,若用普通的线性规划求解,预计要花7个月的时间.他们利用网络分析的方法网络分析的方法,将将其

7、分解成其分解成6个子问题个子问题,利用特殊的网络计算机程序利用特殊的网络计算机程序,花了大花了大约约7个小时问题就得到了解决个小时问题就得到了解决. 由于后续学习的需要由于后续学习的需要,我们补充离散数学中的一些基本我们补充离散数学中的一些基本内容内容:关系与与函数函数.第一章第一章 图的基本概念图的基本概念(1)(1)定义定义1 图图G是一个三元组是一个三元组,记作记作)(),(),(GGEGVG其中其中12( ) ,nV Gv vv,)(GV称为图称为图G的结点集的结点集.(2)或或12( ) ,mE Ge ee是是G的边集合的边集合,其中其中 ie , jtv v ,jtv v或或为边。

8、为边。若若 ie为为 , ,jtv v称称 ie,jtv v为端点的无向边。为端点的无向边。为以为以VVEG: )(称为关联函数称为关联函数.若若 ie为为,jtv v称称 iejv为起点，为起点，为以为以tv为终点的有向边。为终点的有向边。第一章第一章 图的基本概念图的基本概念(2)(2)v定义定义2. 2. 邻接结点邻接结点: :关联于同一条边的两个结点关联于同一条边的两个结点. .v孤立结点孤立结点: :不与任何结点相连接的结点不与任何结点相连接的结点. .v邻接边邻接边: :关联于同一顶点的两条边关联于同一顶点的两条边. .v环环: :两端点相同的边称为环或自回路两端点相同的边称为环或

9、自回路. .v平行边平行边: :两个结点间方向相同的若干条边称为平两个结点间方向相同的若干条边称为平行边或重边行边或重边. .v对称边对称边: :两端点相同但方向相反的两条有向边两端点相同但方向相反的两条有向边. .第一章 图的基本概念(3)v定义定义3 .3 . 无向图无向图: :每条边都是无向边的图每条边都是无向边的图. .v有向图有向图: :每条边都是有向边的图每条边都是有向边的图. .v混合图混合图: :图中不全是有向边图中不全是有向边, ,也不全是无向边的图也不全是无向边的图. .v平凡图平凡图: :只有一个孤立结点的图只有一个孤立结点的图. .v定义定义4. 4. v多重图多重图:

10、 :含有平行边的图含有平行边的图. .v简单图简单图: :无环且无平行边的图无环且无平行边的图. .v完全图完全图: :任何不同结点之间都有边相连的简单无向图任何不同结点之间都有边相连的简单无向图. .第一章 图的基本概念(4)说明:(1)在简单图 中,以x为起点y为终点的边至多有一条,因此,图中的边可直接用顶点对表示,而关联函数 就可以直接表示在其边集中,故可简记为G=.(2)对无向图G,将G中的每条边用两条与e有相同端点对称边e和e来代替后得到一个有向图D,这样得到的有向图D称为G的对称有向图.由此可见,无向图可视为特殊的有向图.)(),(),(GGEGVG(3) n个结点的完全图记为Kn

11、,完全图Kn有 条边.完全图的对称有向图称为完全有向图,记作 .(4) 图G的顶点个数 称为图G的阶.(5) 对于有向图D,去掉边上的方向得到的无向图G称为D的的基础图基础图.反之,任一个无向图G,将G的边指定一个方向得到一个有向图D,称D D为为G G的一个定向图的一个定向图. .) 1(212nnCn*nK例 证明:在任意六个人的聚会上,要么三个曾相识,要么三个不曾相识.证明:用A,B,C,D,E,F代表这六个人,若两人曾相识,则在代表该两人的顶点间连一条红边;否则连一条蓝边.于是,原问题等价于证明所得图中必含有同色三角形.考察某一顶点,设为F.与F关联的边中必有三条同色,不妨设它们是三条

12、红边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).v注意：v有向图D中，结点x的度deg(x)= deg+(x)+deg-(x)。v(G)和(G)分别表示G的最大顶

13、点度和最小顶点度，即(G)=maxdG(x)|xV(G); (G)=mindG(x)|xV(G).v有向图D中，记+(G)=maxd+G(x)|xV(G);+(G)=mind+G(x)|xV(G). -(G)=maxd-G(x)|xV(G);-(G)=mind-G(x)|xV(G).第二节 图的顶点度和图的同构(1)定义定义2 设G为无向图,对于G的每个结点x,若d(x)=K,则称G为为K正则的无向图正则的无向图.设G为有向图,对于G的每个结点x,若d+(x)=d-(x), 则称G为平衡有向图平衡有向图.在有向图G中,若 则称G为为K正则有向图正则有向图.定理1(握手定理，图论基本定理) 每个

14、图中,结点度数的总和等于边数的二倍,即定理2 每个图中,度数为奇数的结点必定是偶数个.,)()()()(KGGGG.2)deg(ExVx第二节 图的顶点度和图的同构(2)v定理3 在任何有向图中,所有结点入度之和所有结点入度之和等于所有结所有结点出度之和点出度之和.v证明证明 因为每条有向边必对应一个入度和出度,若一个结点具有一个入度或出度,则必关联一条有向边.因此,有向图中各结点的入度之和等于边数,各结点出度之和也等于边数.v定义度序列定义度序列 若V(G)=v1,v2,vp,称非负整数序列(d(v1),d(v2),d(vp)为图图G的度序列的度序列.第二节 图的顶点度和图的同构(3)v推论

15、1 非负整数序列 是某个图的度序列当且仅当当且仅当 是偶数.v证明:由定理1知必要性成立.对于充分性取p各相异顶点v1,v2,vp,若di是偶数,就在vi处作di/2个环;v若di是奇数,在vi处作(di-1)/2个环,由于 是偶数,v故 中由偶数个奇数顶点,从而将所有与奇数di相对应的顶点vi两两配对并连上一条边.最后所得的序列就是 .),.,(21pdddpiid1piid1pddd,.,21),.,(21pddd第二节 图的顶点度和图的同构(4)图序列:简单图简单图的度序列.定理4 非负整数序列 是图序列当当且仅当且仅当 是偶数,并且对一切整数k, 有定义3 设G1=和G2=是简单图,若

16、存在一个从V1到V2的双射函数f，且f具有这样的性质,对V1中的所有x和y, x和y在G1中相邻,当且仅当当且仅当f(x)和f(y)在G2中相邻,就说G1和G2是同构的,记作G1 G2.)(,(2121ppdddddd 1piid, 11pk,min111pkiipiidkkkd例1 画出所有不同构的具有5个结点,3条边的简单无向图。例2 是否可以画一个简单无向图,使各点度数与下列的序列一致:v2, 2, 2, 2, 2, 2 v2, 2, 3, 4, 5, 6 v1, 2 , 3, 4, 4, 5第三节第三节 图的运算图的运算(一）一）定义1 设 与 是任何两个图.若 且 是 在 上的限制,

17、则称 是G的子图的子图,记作 称G为G1的母图. 若 且 ,则称 是G的生成子图或支撑子图生成子图或支撑子图. 设 ,以V1为顶点,以两端点均在V1中的G的边的全体为边集的G的子图,称为V1的导出子图的导出子图,记作GV1. 设 ,以E1为边集,以E1中的边关联的全部顶点集的G的子图,称为E1的导出子图的导出子图,记作GE1. ,EVG1111,EVG,11EEVV11E1GGG 1GG 11VV1G11,VVV11,EEE特别,若 ,则以 G-V1表示从G中删去V1内的所有点以及与这些顶点关联的边所得到的子图,若V1=v,常把G-v简记为G-v,类似地,设 ,G-E1表示在G中删去E1中所有

18、边所得的子图,同样G-e简记为G-e.11,VV V11,EEE第三节第三节 图的运算图的运算(二）二）定义2 设G是n阶无向简单图,以V为顶点集,以所有能使G成为完全图完全图Kn的添加边组成的集合为边集的图,称为G相对于完全图完全图Kn补图补图,简称G的补图,记作 .定义3 设G1和G2都是图G的子图.G1和和G2的并的并 : 仅由G1和G2中所有边组成的图.G1和和G2的交的交G1G2 :仅由G1和G2的公共边组成的图. G1和和G2的差的差G1-G2 :仅由G1中去掉G2中的边组成的图.G1和和G2的环和的环和 G1 G2 :在G1和G2的并中去掉G1和G2的交 所得到的图.(见p12)

19、21GG G定义定义4.自补图自补图:若简单图G同构于G的补图 ,则称G为自补图.(1)证明证明:自补图的阶数为自补图的阶数为n=4k或或n=4k+1,k为某个为某个自然数自然数.(自己查阅自己查阅)(2)找出所有找出所有4阶和阶和5阶的自补图阶的自补图.G例例 在一次舞会上,A,B两国留学生各n人,A国每个学生都与B国一些学生(不是所有)跳过舞.B国每个学生至少与A国一个学生跳过舞.证明一定可以找到A国两个学生a1,a2及B国两个学生b1,b2,使得a1和b1,a2和b2跳过舞,而a2和b1,a1和b2没有跳过舞.(自己思考)图的运算图的运算( (三三) )定义四:设G1和G2是任两个无向图

20、, G1和和G2的的笛笛卡儿积卡儿积为图G=G1G2,其中G满足: V(G)=V(G1)V(G2);G中的两顶点和是邻接的当且仅当当且仅当a=c且b,dE(G2)或者b=d且a,cE(G1).说明:(1)通过图的笛卡儿积运算,可归纳地定义一个重要的图类 -n立方体Qn(n1):当n=1,Qn=K2;当n1,Qn=Qn-1K2.(2) n立方体Qn也可以看作是用顶点表示2n个长度为n的位串图.两个顶点相邻当且仅当当且仅当它们所表示的位串恰恰差一位.第四节第四节 路与连通图路与连通图( (一一) )定义1 设u和v是任意图G的顶点,图G的一条u-v是有限的顶点和边交替序列u0e1u1e2un-1e

21、nun (u=u0, v=un),其中与边ei(1in)相邻的两顶点ui-1和ui正好是ei的两个端点.数n(链中出现的边数)称为链的长度链的长度.u(或u0)和v(或un)称为链的端点链的端点,其余的顶点称为链的内链的内部点部点.一条u-v链,当uv时,称它为开的开的,否则称为闭的闭的.边互不相同的链称为迹迹,内部点互不相同的链称为路路.注释1.(1)在一条链中,顶点和边可以重复.(2)若G是简单图,G中的链u0e1u1e2un-1enun还可用结点序列u0u1un-1un表示.(3)不含边的链(即长度为0)称为平凡链平凡链.(4)设W是有向图D中u-v链(迹,路),指定W的方向从u到v.若

22、W中所有边的方向与此方向一致,则称W为D中从u到v的有向链有向链(迹迹,路路).第四节第四节 路与连通图路与连通图( (二二) )定义2 两端点相同的迹(即闭集)称为回回.两端点相同的路(即闭路)称为圈或回路圈或回路.长度为K,奇数,偶数的回(圈)分别称为称为K,奇奇,偶回偶回(圈圈).有向闭迹(闭路)称为有向回有向回(有向圈有向圈).定理1. 若简单图G中每个顶点的度数至少是k(k2),则G中必含有一个长度至少是k+1的圈.证明:在G的所有路中,取一条长度最长的路p,记p=v0v1vt-1vt.则v0的所有邻接点全在p中,由于d(v0) k 2,所以v0至少有k个邻接点,设所有邻接点为vi1

23、,vi2,vis,1i1 i2 is t,其中s=d(v0) k 2,则C=v0v1v2visv0就是G的一个长为is+1的圈,显然is+1 k +1.第四节第四节 路与连通图路与连通图( (三三) ).定理定理2 设简单图G中每个顶点的度数至少是3,则G中含有偶圈.证明:在G的所有路中,取一条长度最长的路p,记p=v0v1vt-1vt.则v0的所有邻接点全在p中,设v0的所有邻接点为vi1,vi2,vis,1i1 i2 is t,其中s=d(v0) 3,在G中取三个圈c1=v0v1vi2v0 , c2=v0v1visv0, c3=v0vi2vi2+1visv0,它们的长度分别为i2+1,is

24、+1和is-i2+2.这三个数中至少有一个是偶数.即c1, c2, c3中至少有一个是偶圈.定义定义3 给定无向图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中的导出子图GV1,GV2,GVm称为G的连通分支或分连通分支或分支支,m称为G的

25、连通分支数,记作W(G)=m.如下图有4个连通分支.定义4. 如果无向图G中每一对不同的顶点x和y都有一条路,即W(G)=1,则称G是连通图连通图,反之称为非连通图. S, Te|eE(G),e的两个端点分别在S和T中，其中T=V-S。v引理1 非平凡图G是连通图当且仅当对V(G)的每一个非空真子集S, S,S,S=V-S.第四节第四节 路与连通图路与连通图(五五)v定理3 设G是P阶连通图,则v证明:只需证明连通的简单图成立即可.设v悬挂点:度数为1顶点. 1)( PGE.1PG,),(,.,)G(V,.,V,V1,G),(33333213223222221221111111111条边中的便

26、可找出过程继续这一边否则与上一样取到一条论已成立结若再取中的一个端点在为记则存在的真子集是若取不妨设边令知由引理则令至少有两个顶点若VVeGVVvvvVVevVVeVvvVvveVeVvVGVv第四节第四节 路与连通图路与连通图(六六)定理定理4 设连通图G至少有两个顶点,其边数小于顶点数,则此图至少有一个悬挂点.证明:设图G是满足条件的P阶图.反设图G没有悬挂点,由于G是连通图,故每个顶点的度数至少为2,即对每个顶点v,d(v)2,故 ,与 矛盾.22v V(G)E(G)d(v)P E(G) P 定理定理5 设简单图G的结点序列为 .度数依次是d(v1) d(v2) d(vp) ,如果对任意

27、的 则G是连通图是连通图.证明证明:反设G不连通,令G1是G中不含vp的一个连通分支, 而G2是G中含vp的一个连通分支,则G2至少有 个顶点,且 1jjp(G),d(v )j,1V(G )k , 12pv ,v ,.,v11pd(v )(G) 12121V(G )V(G )p,kV(G )pV(G )p(G) 第四节第四节 路与连通图路与连通图(七七)则由已知 .若记 则 ,则与 矛盾.推论1 设G是P阶简单图,每个顶点的度至少是P/2,则G是连通图.定义5 设 是有向图, ,若图 D中存在x到y的有向路,称结点结点x可达结点可达结点y. 规定x到自身总是可达的. kd(v )k 11212

28、iiikkV(G )v ,v ,.,v ,iii ikkd(v )d(v )k 111ikV(G )d(v )k 1V(G )k )(),(),(DDEDVDx,yV(D) 定义定义6 设G是有向图,任何结点间,至少有一个结点可达另一个结点,则称该有向图是单侧连通的单侧连通的.如果有向图D的任何一对结点间是相互可达的,则称该有向图是该有向图是强连通的强连通的.若有向图G的基础图是连通的 ,则称该有向图D是弱连通的弱连通的.定义定义7 设G是有向图, ,G中所有从x到y的有向路的最小长度称为从称为从x到到y的距离的距离. x,yV(D) 定义定义8 设G是无向图, ,G中所有从x到y的路的最小长

29、度称为从称为从x到到y的距离的距离. 称为图图G的直径的直径. x,yV(D) Dmaxd(x,y)x,yV(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

30、-S不连通或是平凡图，任意S的真子集S满足G-S是连通的,则称S为G的一个边割边割.定义4 设G是连通图,称 是G的点割 为G的点连通度或连通度点连通度或连通度;称 是G的边割为G的边连通度边连通度. TTGKmin)(SSGmin)(定理定理1 对一个图G,有 是图G的最小顶点度.(不证)证明:若G不连通,则 结论成立.若G连通.(1)先证 设x是G中度数最小的顶点,即 .设所有与 关联的边集为S(x),显然x是G-S(x)的一个孤立点.所以(2)再证 当 时,显然 假设对所有 的图G有 设 S是H的一个边割,且 若边 易知 故由假设知 并设T是H-e的一个点割,且 此时, 就是H的一个点割

31、,即 K(H) Tu n+1=（H）. 再由归纳假设即知 K(G) （G） 结论成立. K(G)(G)(G). (G) 0K(G)(G), (G)(G). d(x)(x) x(G)S(x)(G). K(G)(G). 1(G)1K(G). 2(G)n(n) K(G)(G). ()1Hn1Sn.e u,v S, (He)n, K(He)(He)n, K(He)T . Tu第五节 连通图和二分图(3)定义5 如果无向图G的连通度 称图G是n连通的连通的或G为n连通图连通图.若 称图G是n边连通边连通的或G为n边连通图边连通图.定理2 设图G是n连通的,则对(反证)定理3 设G是2边连通图,则G有强连

32、通的定向图.),1()(nnGK),1()(nnG .)deg(),(nxGVx证明:设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.iGiiiiQPGG1)()(1iiGVGV1G,1iiiiQPGG1

33、iG1iG第五节 连通图和二分图(4) 因此,最后的 是强连通有向图.由于Gn是G的生成子图,所以G有强连通的定向图. 一个图G有强连通的定向图的必要条件必要条件是G为2边连通的.否则G有割边,这与G有强连通的定向图矛盾.nG定义6 把简单图G的顶点集合分成两个不相交的非空集合V1,V2,使得图G中的每一条边,与其关联的两个结点分别在V1和V2中,则G称为偶图或二分图偶图或二分图,记作G=,其中V1和V2叫做G的二划分二划分. 对于二分图G=,若 ,V1中的任意一点与V2中的所有点相邻且V2中的任意一点与V1中的所有点相邻,则称该图为结点m和n的完全偶完全偶图或完全二分图图或完全二分图,记作K

34、m,n.12,Vm Vn例1 试说明n立方体Qn是二分图.证明:不妨设 由Qn的定义知Qn是简单图.假定 则边 ,即两结点序列恰差一位.令显然 .而且,若存在., 2 , 1,1 , 0)(21nixxxxQVinn ),(,2121nnnQVyyyyxxxx 1)(,1niiinyxQEyx1 212,(),0(mod2),(),nnnnX YV QXx xx xxxX YV Q),2(mod12121 nnyyyyyyYYXQVYXn),()( ,.,2121nnnQExxtsXxxxxXxxxx 即 与 矛盾.所以X中任何两顶点之间无边相连.同理可证Y中任何两顶点之间也无边相连.因此Qn

35、是二分图.定理4 非平凡图G是二分图当且仅当当且仅当G中不含有长为奇数的圈.证明:( )设G是一个二分图,G的二分为V1和V2,则GV1和GV2为零图.设v=v1v2vkv1是G中长度为k的一个圈.下证k为偶数.不妨设 由于v2和v1相邻,故 ;同样有又最后一个顶点是v1,故k必为偶数.1) ()(32121 xxxxxxnXxx,11Vv 22Vv 13Vv ()不妨设G中每一对点之间有路连接(否则只考虑G的每个每一对点之间有路连接的极大子图).任取G的一个顶点u,由G的假设,对G的每个顶点v,在G中存在u-v路.现利用u对G的顶点进行分类.设 显然, .由于G中不存在长度为奇数的圈,所以对

36、任意一个点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路中存在一条长为偶数的vuGGVvvV),(2路中存在一条常为奇数的vuGGVvvV1Vu.21VV )(21GVVV12 PPe第六节 图的矩阵表示(1)1.邻接矩阵:设 是有向图,其中V=x1,x2,xn,E=e1,e2,em,则n阶方阵A=(aij)称为G的邻接矩阵邻接矩阵.其中aij为图G中以xi为起点且以xj为终点的边的数目。若G是无向图，aij为图G中以xi和xj为端点的边的数目.说明1:由定义易知,无向图的邻接矩阵是对称矩阵对称矩阵,而有向图的邻接矩阵未必是对称矩阵对称矩阵.(如P27),EVG定理1 已知有向图 , 其中V=x1,x2,xn,且A=(aij)nn为G的邻接矩阵,则Ak