图论的基本概念.ppt

《图论的基本概念.ppt》由会员分享，可在线阅读，更多相关《图论的基本概念.ppt（55页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、连即任意两点可由图中的一些边连接起来接起来;2)2)与图中每一顶点相连的边必须是偶数与图中每一顶点相连的边必须是偶数.由此得出结论由此得出结论:七桥问题无解七桥问题无解.欧拉由七桥问题所引发的研究论文是图论的开欧拉由七桥问题所引发的研究论文是图论的开篇之作篇之作,因此称欧拉为图论之父因此称欧拉为图论之父.现在学习的是第3页，共55页4.4.图的作用图的作用 图是一种表示工具.改变问题的描述方式,往往是创造性的启发式解决问题的手段.一种描述方式就好比我们站在一个位置和角度观察目标,有的东西被遮挡住了,但如果换一个位置和角度,原来隐藏着的东西就可能被发现.采用一种新的描述方式,可能会产生新思想.图

3、论中的图提供了一种直观,清晰表达已知信息的方式.它有时就像小学数学应用题中的线段图一样,能使我们用语言描述时未显示的或不易观察到的特征、关系,直观地呈现在我们面前,帮助我们分析和思考问题,激发我们的灵感.现在学习的是第4页，共55页5.5.图的广泛应用图的广泛应用 图的应用是非常广泛的图的应用是非常广泛的,在工农业生产、交通运在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络输、通讯和电力领域经常都能看到许多网络,如如河道网、灌溉网、管道网、公路网、铁路网、电河道网、灌溉网、管道网、公路网、铁路网、电话线网、计算机通讯网、输电线网等等话线网、计算机通讯网、输电线网等等.还有许还有许多看

4、不见的网络多看不见的网络,如各种关系网如各种关系网,像状态转移关系像状态转移关系、事物的相互冲突关系、工序的时间先后次序关、事物的相互冲突关系、工序的时间先后次序关系等等系等等,这些网络都可以归结为图论的研究对象这些网络都可以归结为图论的研究对象 -图图.其中存在大量的网络优化问题需要我们其中存在大量的网络优化问题需要我们解决解决.还有象生产计划、投资计划、设备更新等还有象生产计划、投资计划、设备更新等问题也可以转化为网络优化的问题问题也可以转化为网络优化的问题.现在学习的是第5页，共55页6.基本的网络优化问题 基本的网络优化问题有:最短路径问题、最小生成树问题、最大流问题和最小费用问题.图

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

6、由于后续学习的需要,我们补充离散数学中的我们补充离散数学中的一些基本内容一些基本内容:关系与函数关系与函数.现在学习的是第7页，共55页第一章 图的基本概念(1)定义1 图 图G是一个三元组,记作 其中(1)V(G)=v1,v2,vn,称为图G的结点集.(2)E(G)=e1,e2,em是G的边集合,其中ei为 vj,vt或.若ei为vj,vt,称ei为vj和vt为端点的无向边;若ei为,称ei为vj 为起点,vt为终点的有向边;(3)称为关联函数.)(),(),(GGEGVG,)(GVVVEG:)(现在学习的是第8页，共55页第一章 图的基本概念(2)定义2.邻接结点:关联于同一条边的两个结点

7、.孤立结点:不与任何结点相连接的结点.邻接边:关联于同一顶点的两条边.环:两端点相同的边称为环或自回路.平行边:两个结点间方向相同的若干条边称为平行边或重边 对称边:两端点相同但方向相反的两条有向边.现在学习的是第9页，共55页第一章 图的基本概念(3)定义3 无向图:每条边都是无向边的图.有向图:每条边都是有向边的图.混合图:图中不全是有向边,也不全是无向边的图.平凡图:只有一个孤立结点的图.定义4.多重图:含有平行边的图.简单图:无环且无平行边的图.完全图:任何不同结点之间都有边相连的简单无向图.现在学习的是第10页，共55页第一章 图的基本概念(4)说明:(1)在简单图 中,以x为起点y

8、为终点的边至多有一条,因此,图中的边可直接用顶点对表示,而关联函数 就可以直接表示在其边集中,故可简记为G=.(2)对无向图G,将G中的每条边用两条与e有相同端点对称边e和e来代替后得到一个有向图D,这样得到的有向图D称为G的对称有向图.由此可见,无向图可视为特殊的有向图.)(),(),(GGEGVG现在学习的是第11页，共55页(3)n个结点的完全图记为Kn,完全图Kn有 条边.完全图的对称有向图称为完全有向图,记作 .(4)图G的顶点个数还称为图G的阶.(5)对于有向图D,去掉边上的方向得到的无向图G称为D的基础图.反之,任一个无向图G,将G的边指定一个方向得到一个有向图D,称D为G的一个

9、定向图.)1(212nnCn*nK现在学习的是第12页，共55页例 证明:在任意六个人的聚会上,要么三个曾相识,要么三个不曾相识.证明:用A,B,C,D,E,F代表这六个人,若两人曾相识,则在代表该两人的顶点间连一条红边;否则连一条蓝边.于是,原问题等价于证明所得图中必含有同色三角形.考察某一顶点,设为F.与F关联的边中必有三条同色,不妨设它们是三条红边FA,FB,FC.再看三角形ABC.若它有一条红边,设为AB,则FAB是红边三角形;若三角形ABC没有红边,则其本身就是蓝边三角形.现在学习的是第13页，共55页第二节 图的顶点度和图的同构(1)定义1 设G是任意图,x为G的任意结点,与结点x

10、关联的边数(一条环计算两次)称为x的度数.记作deg(x)或d(x).定义2 设G为无向图,对于G的每个结点x,若d(x)=K,则称G为K正则的无向图.设G为有向图,对于G的每个结点x,若d+(x)=d-(x),则称G为平衡有向图.在有向图G中,若 则称G为K正则有向图.定理1(握手定理，图论基本定理)每个图中,结点度数的总和等于边数的二倍,即定理2 每个图中,度数为奇数的结点必定是偶数个.,)()()()(KGGGG.2)deg(ExVx现在学习的是第14页，共55页第二节 图的顶点度和图的同构(2)定理3 在任何有向图中,所有结点入度之和等于所有结点出度之和.证明 因为每条有向边必对应一个

11、入度和出度,若一个结点具有一个入度或出度,则必关联一条有向边,因此,有向图中各结点的入度之和等于边数,各结点出度之和也等于边数.定义 度序列,若V(G)=v1,v2,vp,称非负整数序列(d(v1),d(v2),d(vp)为图G的度序列.现在学习的是第15页，共55页第二节 图的顶点度和图的同构(3)推论1 非负整数序列 是某个图的度序列当且仅当 是偶数.证明:由定理1知必要性成立.对于充分性取p各相异顶点v1,v2,vp,若di是偶数,就在vi处作di/2个环;若di是奇数,在vi处作(di-1)/2个环,由于 是偶数,故 中由偶数个奇数顶点,从而将所有与奇数di相对应的顶点vi两两配对并连

12、上一条边.最后所得的序列就是 .),.,(21pdddpiid1piid1pddd,.,21),.,(21pddd现在学习的是第16页，共55页第二节 图的顶点度和图的同构(4)图序列:简单图的度序列.定理4 非负整数序列 是图序列当且仅当 是偶数,并且对一切整数k,有定义3 设G1=和G2=是简单图,若存在一个从V1到V2的双射函数f,且f具有这样的性质,对V1中的所有x和y,x和y在G1中相邻,当且仅当当且仅当f(x)和f(y)在G2中相邻,就说G1和G2是同构的,记作G1 G2.)(,(2121ppdddddd 1piid,11pk,min111pkiipiidkkkd现在学习的是第17

13、页，共55页例1 画出所有不同构的具有5个结点,3条边的简单无向图.例2 是否可以画一个简单无向图,使各点度数与下列的序列一致:(1)2,2,2,2,2,2(2)2,2,3,4,5,6(3)1,2,3,4,4,5现在学习的是第18页，共55页第三节第三节 图的运算图的运算(一）一）定义1 设 与 是任何两个图.若 且 是 在 上的限制,则称 是G的子图,记作 称G为G1的母图.若 且 ,则称 是G的生成子图或支撑子图.设 ,以V1为顶点,以两端点均在V1中的全体边为边集的G的子图,称为V1的导出子图,记作GV1.设 ,以E1为边集,以E1中的边关联的全部顶点集的G的子图,称为E1的导出子图,记

14、作GE1.,EVG1111,EVG,11EEVV11E1GGG 1GG 1GG 11G,11VVV11,EEE现在学习的是第19页，共55页特别,若 ,则以 G-V1表示从G中删去V1内的所有点以及与这些顶点关联的边所得到的子图,若V1=v,常把G-v简记为G-v,类似地,设 ,G-E1表示在G中删去E1中所有边所得的子图,同样G-e简记为G-e.,11VVV11,EEE现在学习的是第20页，共55页第三节第三节 图的运算图的运算(二）二）定义2 设G是n阶无向简单图,以V为顶点集,以所有能使G成为完全图完全图Kn的添加边组成的集合为边集的图,称为G相对于完全图完全图Kn补图补图,简称G的补图

15、,记作 .定义3 设G1和G2都是图G的子图.G G1 1和和G G2 2的并的并 :仅由G1和G2中所有边组成的图.G1和和G2的交的交 :仅由G1和G2的公共边组成的图.G G1 1和和G G2 2的差的差G G1 1-G-G2 2:仅由G1中去掉G2中的边组成的图.G1和和G2的环和的环和 :在G1和G2的并中去掉G1和G2的交 所得到的图.21GG 21GG G12GG现在学习的是第21页，共55页定义定义4.自补图自补图:若简单图若简单图G同构于同构于G的补图的补图 ,则则称称G为自补图为自补图.(1)证明证明:自补图的阶数为自补图的阶数为n=4k或或n=4k+1,k为某为某个自然数

16、个自然数.(自己查阅自己查阅)(2)找出所有找出所有4阶和阶和5阶的自补图阶的自补图.G现在学习的是第22页，共55页例例.在一次舞会上在一次舞会上,A,B两国留学生各两国留学生各n人人,A国每国每个学生都与个学生都与B国一些学生国一些学生(不是所有不是所有)跳过舞跳过舞.B国每个学生至少与国每个学生至少与A国一个学生跳过舞国一个学生跳过舞.证明证明:一定可以找到一定可以找到A国两个学生国两个学生a1,a2及及B国两个学国两个学生生b1,b2,使得使得a1和和b1,a2和和b2跳过舞跳过舞,而而a2和和b1,a1和和b2没有跳过舞没有跳过舞.(自己思考自己思考)现在学习的是第23页，共55页图

17、的运算图的运算(三三)定义四:设G1和G2是任两个无向图,G1和G2的笛卡儿积为图 ,其中G满足:V(G)=V(G1)V(G2);G中的两顶点和是邻接的当且仅当a=c且b,d E(G2)或者b=d且a,c E(G1).说明:(1)通过图的笛卡儿积运算,可归纳地定义一个重要的图类-n立方体Qn(n1):当n=1,Qn=K2;当n1,Qn=Qn-1K2.(2)n立方体Qn也可以看作是用顶点表示2n个长度为n的位串图.两个顶点相邻,当且仅当它们所表示的位串恰恰差一位.21GGG现在学习的是第24页，共55页第四节第四节 路与连通图路与连通图(一一)定义定义1 1 设设u u和和v v是任意图是任意图

18、G G的顶点的顶点,图图G G的一条的一条u-vu-v是有是有限的顶点和边交替序列限的顶点和边交替序列u u0 0e e1 1u u1 1e e2 2u un-1n-1e en nu un n(u=(u=u u0 0,v=u,v=un n),),其中与边其中与边e ei i(1(1 i i n)n)相邻的两顶点相邻的两顶点u ui-1i-1和和u ui i正好是正好是e ei i的两个端点的两个端点.数数n(n(链中出现的边数链中出现的边数)称为链的长度称为链的长度.u(u.u(u0 0)和和v(uv(un n)称为链的端点称为链的端点,其余其余的顶点称为链的内部点的顶点称为链的内部点.一条一

19、条u-vu-v链链,当当u u v v时时,称称它为开的它为开的,否则称为闭的否则称为闭的.边互不相同的链称为边互不相同的链称为迹迹,内部点互不相同的链称为路内部点互不相同的链称为路.现在学习的是第25页，共55页注释注释1.1.(1)(1)在一条链中在一条链中,顶点和边可以重复顶点和边可以重复.(2)(2)若若G G是简单图是简单图,G,G中的链中的链u u0 0e e1 1u u1 1e e2 2u un-1n-1e en nu un n还可用还可用结点序列结点序列u u0 0u u1 1u un-1n-1u un n表示表示.(3)(3)不含边的链不含边的链(即长度为即长度为0)0)称为

20、平凡链称为平凡链.(4)(4)设设W W是有向图是有向图D D中中u-vu-v链链(迹迹,路路),),指定指定W W的方向从的方向从u u到到v.v.若若W W中所有边的方向与此方向一致中所有边的方向与此方向一致,则称则称W W为为D D中从中从u u到到V V的有向链的有向链(迹迹,路路).).现在学习的是第26页，共55页第四节第四节 路与连通图路与连通图(二二)定义定义2.两端点相同的迹两端点相同的迹(即闭集即闭集)称为回称为回.两端点相两端点相同的路同的路(即闭路即闭路)称为圈或回路称为圈或回路.长度为长度为K,奇数奇数,偶偶数的回数的回(圈圈)分别称为分别称为K,奇奇,偶回偶回(圈圈

21、).有向闭迹有向闭迹(闭闭路路)称为有向回称为有向回(有向圈有向圈).现在学习的是第27页，共55页定理定理1.若简单图若简单图G中每个顶点的度数至少是中每个顶点的度数至少是k(k 2),则则G中必含有一个长度至少是中必含有一个长度至少是k+1的圈的圈.证明证明:在在G的所有路中的所有路中,取一条长度最长的路取一条长度最长的路p,记记P=v0v1vt-1vt.则则v0的所有邻接点全在的所有邻接点全在p中中,由由于于d(v0)k 2,所以所以v0至少有至少有k个邻接点个邻接点,设所设所有邻接点为有邻接点为vi1,vi2,vis,1 i1 i2 is t,其其中中s=d(v0)k 2,则则C=v0

22、v1v2visv0就是就是G的的一个长为一个长为is+1的圈的圈,显然显然is+1 k+1.现在学习的是第28页，共55页第四节第四节 路与连通图路与连通图(三三)定理定理2.设简单图设简单图G中每个顶点的度数至少是中每个顶点的度数至少是3,则则G中含有偶圈中含有偶圈.证明证明:在在G的所有路中的所有路中,取一条长度最长的路取一条长度最长的路p,记记P=v0v1vt-1vt.则则v0的所有邻接点全在的所有邻接点全在p中中,设设v0的所有邻接点为的所有邻接点为vi1,vi2,vis,1 i1 i2 is t,其中其中s=d(v0)3,在在G中取三个圈中取三个圈c1=v0v1vi2v0,c2=v0

23、v1visv0,c3=v0vi2vi2+1visv0,它们的长度分别为它们的长度分别为i2+1,is+1和和is-i2+2.这三个数中至少有一个是偶这三个数中至少有一个是偶数数.即即c1,c2,c3中至少有一个是偶圈中至少有一个是偶圈.现在学习的是第29页，共55页定义定义3.给定无向图给定无向图G=,x,y V(G),若图中存在连接若图中存在连接x和和y的路的路,称节点称节点x和和y是是连通的连通的.规定规定x到自身总是连通的到自身总是连通的.现在学习的是第30页，共55页第四节第四节 路与连通图路与连通图(四四)1.说明:容易验证,结点集V(G)上的顶点间的连通关系是V(G)上的一个等价关

24、系等价关系,该等价关系确定V(G)的一个划分V1,V2,Vm,使得当且仅当当且仅当两个顶点x和y属于同一子集Vi时,x和y才是连通的.Vi在G中的导出子图GV1,GV2,GVm称为G的连通分支或分支连通分支或分支,m称为G的连通分支数,记作W(G)=m.如下图有4个连通分支.定义4.如果无向图G中每一对不同的顶点x和y都有一条路,即W(G)=1,则称G是连通图,反之称为非连通图.现在学习的是第31页，共55页第四节第四节 路与连通图路与连通图(五五)引理1 非平凡图G是连通图当且仅当对V(G)的每一个非空真子集S,定理3 设G是P阶连通图,则 证明:只需证明连通的简单图成立即可.设 悬挂点:度

25、数为1顶点.,().S SSVS.1)(PGE.1PG,),(,.,)G(V,.,V,V1,G),(33333213223222221221111111111条边中的便可找出过程继续这一边否则与上一样取到一条论已成立结若再取中的一个端点在为记则存在的真子集是若取不妨设边令知由引理则令至少有两个顶点若VVeGVVvvvVVevVVeVvvVvveVeVvVGVv现在学习的是第32页，共55页第四节第四节 路与连通图路与连通图(六六)定理4 设连通图G至少有两个顶点,其边数小于顶点数,则此图至少有一个悬挂点.证明:设图G是满足条件的P阶图.反设图G没有悬挂点,由于G是连通图,故每个顶点的度数至少为

26、2,即对每个顶点v,d(v)2,故 ,与 矛盾.22v V(G)E(G)d(v)P E(G)P 现在学习的是第33页，共55页定理定理5 设简单图G的结点序列为 .度数依次是d(v1)d(v2)d(vp),如果对任意的 则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)现在学习的是第34页，共55页第四节第四节 路与连通图路与连通图(七七)则由已知,.若记 则 ,则与 矛盾

27、.推论1 设G是P阶简单图,每个顶点的度至少是P/2,则G是连通图.定义5 设 是有向图,若图 D中存在x到y的有向路,称结点x可达结点y.规定x到自身总是可达的.kd(v)k 11212iiikkV(G)v,v,.,v,iii ikkd(v)d(v)k 111ikV(G)d(v)k 1V(G)k)(),(),(DDEDVDx,yV(D)现在学习的是第35页，共55页定义定义6 设G是有向图,任何结点间,至少有一个结点可达另一个结点,则称该有向图是单侧连通的.如果有向图D的任何一对结点间是相互可达的,则称该有向图是强连通的.若有向图G的基础图是连通的,则称该有向图D是弱连通的.定义定义7 设G

28、是有向图,G中所有从x到y的有向路的最小长度称为从x到y的距离.称为图G的直径.x,yV(D)D maxd(x,y)x,y V(G)现在学习的是第36页，共55页第五节 连通图和二分图(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的块.现在学习的是第37页，共55页定义3如果G的顶点集的一个真子集T满足G-T不连通或是平凡图,则称T为G的一个点割.如果图G的边集的一个真子

29、集S满足G-S不连通或是平凡图,则称S为G的一个边割.定义4设G是连通图,称 是G的点割为G的点连通度或连通度;称 是G的边割为G的边连通度.TTGKmin)(SSGmin)(现在学习的是第38页，共55页定理1 对一个图G,有 是图G的最小顶点度.证明:若G不连通,则 结论成立.若G连通.(1)先证 设x是G中度数最小的顶点,即 .设所有与 关联的边集为S(x),显然x是G-S(x)的一个孤立点.所以(2)再证 当 时,显然 假设对所有 的图G有 设 S是H的一个边割,且 若边 易知 故由假设知 并设T是H-e的一个点割,且 此时,就是H的一个点割,即 K(H)Tu n+1=（H）.再由归纳

30、假设即知 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现在学习的是第39页，共55页第五节 连通图和二分图(3)定义5 如果无向图G的连通度 称图G是n连通的或G为n连通图.若 称图G是n边连通的或G为n边连通图.定理2 设图G是n连通的,则对(反证)定理3 设G是2边连通图,则G有强连通的定向图.),1()(nnGK),1()(nnG.)deg(),(nxGVx现

31、在学习的是第40页，共55页证明:设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,1iiiiQPGG1iG1iG现在学习的是第41页，共55页第五节 连通图

32、和二分图(4)因此最后的 是强连通有向图.由于Gn是G的生成子图,所以G有强连通的定向图.一个图G有强连通的定向图的必要条件是G为2边连通的.否则G有割边,这与G有强连通的定向图矛盾.定义6 把简单图G的顶点集合分成两个不相交的非空集合V1,V2,使得图G中的每一条边,与其关联的两个结点分别在V1和V2中,则G称为偶图或二分图,记作G=,其中V1和V2叫做G的二划分.对于二分图G=,若 ,V1中的任意一点与V2中的所有点相邻且V2中的任意一点与V1中的所有点相邻,则称该图为结点m和n的完全偶图或完全二分图,记作Km,n.nG,21nVmV现在学习的是第42页，共55页例1试说明n立方体Qn是二

33、分图.证明:不妨设 由Qn的定义知Qn是简单图.假定 则边 ,即两结点序列恰差一位.令显然 .而且,若存在.,2,1,1,0)(21nixxxxQVinn ),(,2121nnnQVyyyyxxxx 1)(,1niiinyxQEyx),(,),2(mod0),(,2121nnnnQVYXxxxxxxXQVYX ),2(mod12121 nnyyyyyyYYXQVYXn),()(,.,2121nnnQExxtsXxxxxXxxxx 现在学习的是第43页，共55页即 与 矛盾.所以X中任何两顶点之间无边相连.同理可证Y中任何两顶点之间也无边相连.因此Qn是二分图.定理4 非平凡图G是二分图当且仅当

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

35、的路的长度都有相同的奇偶性,因而 由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)(21GVVV21ePP现在学习的是第45页，共55页第六节 图的矩阵表示(1)1.邻接矩阵:设 是任意图,其中V=x1,x2,xn,E=e1,e2,em,则n阶方阵A=(

36、aij)称为G的邻接矩阵.其中aij为图G中以xi为起点且以xj为终点的边的数目.说明1:由定义易知,无向图的邻接矩阵是对称矩阵,而有向图的邻接矩阵未必是对称矩阵.(如P27),EVG现在学习的是第46页，共55页定理1 已知有向图 ,其中V=x1,x2,xn,且A=(aij)nn为G的邻接矩阵,则Ak中的i和j列元素aij(k)是图G中从xi到xj且长度为k的有向链的数目.证明:k=1时,结论显然成立.若Ak-1第i行j列元素aij(k-1)是G中长度为k-1的从xi到xj的有向链的数目.又Ak=Ak-1A,所以aij(k)=因为G中每条从xi到xj且长度为k的有向链都是由长度为k-1的从x

37、i到xt(1t n)的链再接上边而得.据归纳假设知定理得证.说明2:该定理同样适合无向图,且定理中的链不能改为迹或路.,EVG(1)1.nkittjtaa现在学习的是第47页，共55页第六节 图的矩阵表示(2)推论1 若G是P阶简单图,且G的邻接矩阵为A=(aij),则对G的每一个顶点vi,i=1,2,p,有d(vi)=aii(2),其中A2=(aii(2).证明:因为图G中与顶点vi关联的边数等于从vi到vi长为2的链的数目,故由定理1知结论成立.R=A+A2+Ap-1=(rij),rij为xi到xj长度不超过p-1的链的数目定理2 已知P(P3)阶图G的邻接矩阵为A,作P阶方阵R=A+A2

38、+Ap-1,则图G连通的充分必要条件为R中的每个元素都不为零.现在学习的是第48页，共55页2.关联矩阵关联矩阵:设 是有向图,且V=,称 阶矩阵M=(mij)为有向图D的关联矩阵,其中,EVD,21nxxx,.,21meeeE 2,1,D,1,D,0,jijijijjijjiexexemexeex是自环 且关联于在 中 以 为起点不是自环在 中 以 为终点不是自环与 不关联mn现在学习的是第49页，共55页第六节 图的矩阵表示(3)设 是无向图,且V=,称 阶矩阵M=(mij)为无向图D的关联矩阵,其中说明3:从关联矩阵可得无向图的一些性质:(1)关联矩阵的每一列只有两个1(每条边只关联两个

39、顶点);(2)关联矩阵的每一行元素之和为对应顶点的度;(3)若某行中元素全为零,则相应顶点为孤立点;(4)重边所对应的列完全相同.,EVG,21nxxx,.,21meeeE mn2,1,0,jiijjijjiexmex eex是自环 且关联于关联不是自环与 不关联现在学习的是第50页，共55页3.可达矩阵:设G=是无重边有向图,其中V=,称 阶矩阵P=(Pij)为G的可达矩阵.其中推论1 若G是P阶简单图,且G的邻接矩阵为A=(aij),则对G的每一个顶点vi,i=1,2,p,有d(vi)=aii(2),其中A2=(aii(2).证明:因为图G中与顶点vi关联的边数等于从vi到vi长为2的链的

40、数目,故由定理1知结论成立.12n x,x,x nn没有有向链到从至少有一条有向链到从jijiijxxxxP,0,1现在学习的是第51页，共55页第六节 图的矩阵表示(2)定理2.已知P(P3)阶图G的邻接矩阵为A,作P阶方阵R=A+A2+Ap-1,则图G连通的充分必要充分必要条件条件为R中的每个元素都不为零.2.关联矩阵:设 是有向图,且V=,称 阶矩阵M=(mij)为有向图D的关联矩阵,其中,EVD,21nxxx,.,21meeeE mn不关联与不是自环为终点以中在不是自环为起点以中在且关联于是自环ijjijjijijijxeexeexexem,0,D,1,D,1,2现在学习的是第52页，

41、共55页第六节 图的矩阵表示(3)设 是无向图,且V=,称 阶矩阵M=(mij)为无向图D的关联矩阵,其中说明3:从关联矩阵可得无向图的一些性质:(1)关联矩阵的每一列只有两个1(每条边只关联两个顶点);(2)关联矩阵的每一行元素之和为对应顶点的度;(3)若某行中元素全为零,则相应顶点为孤立点;(4)重边所对应的列完全相同.,EVG,21nxxx,.,21meeeE mn不关联与不是自环关联且关联于是自环ijjijijijxeexexem,0,1,2现在学习的是第53页，共55页3.可达矩阵:设G=是无重边有向图,其中V=,称 阶矩阵P=(Pij)为G的可达矩阵.其中12,nxxx nn没有有向链到从至少有一条有向链到从jijiijxxxxP,0,1现在学习的是第54页，共55页习题讲解习题讲解:1.无向图无向图G有有21条边条边,12个个3度结点度结点,其余结点其余结点的度数均为的度数均为2,求求G的阶数的阶数n.2.证明证明:若无向图若无向图G不连通不连通,则则G的补图是连通的补图是连通的的.3.设设G为为n阶简单无向图阶简单无向图,n2且且n为奇数为奇数,试问试问G与其补图中度数为奇数的顶点个数是否一定与其补图中度数为奇数的顶点个数是否一定相等相等?4.画出画出4阶完全图阶完全图K4的所有非同构的生成子图的所有非同构的生成子图.现在学习的是第55页，共55页