第二章道路和回路2.1道路和回路

《第二章道路和回路2.1道路和回路》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章道路与回路2.1道路与回路定义2.1.1有向图G=(V,E)中,若边序列P=(ei1,ei2,…,eiq),其中eik=(vl,vj)满足vl是eik-1的终点,vj是eik+1的始点，就称P是G的一条有向道路.如果eiq的终点也是ei1的始点，则称P是G的一条有向回路道路与回路如果P中的边没有重复出现，则分别称为简单有向道路和简单有向回路进而,如果P中结点也不重复出现,又分别称它们是初级有向道路和初级有向回路,简称为路和回路显然,初级有向道路(回路)一定是简单有向道路(回路)有向道路ABCDe3e1e2e4e5(e

2、1,e2,e5,e1)有向道路，不是简单有向道路(e1,e2,e5,e4)简单有向道路，不是初级有向道路(A)(e1,e2,e3)初级有向道路(e1,e2,e5)初级有向回路道路与回路定义2.1.2无向图G=(V,E)中，若点边交替序列P=(vi1,ei1,vi2,ei2,…,eiq-1,viq)满足vik,vik+1是eik的两个端点,则称P是G中的一条链或道路.如果viq=vi1,则称P是G中的一个圈或回路如果P中没有重复出现的边,称之为简单道路或简单回路,若其中结点也不重复,又称之为初级道路或初级回路例V1到v4的初

3、级道路v1v2v3v4v5e1e2e3e4e5e6e7v1e1v2e6v5e4v4e7v2V1到v2的简单道路道路与回路定义2.1.31.设G是无向图,若G的任意两结点之间都存在道路,就称G是连通图,否则称为非连通图2.如果G是有向图,不考虑其边的方向,即视为无向图,若它是连通的,则称G是连通图3.若连通子图H不是G的任何连通子图的真子图,则称H是G的极大连通子图或称连通支显然G的每个连通支都是它的导出子图连通图ABCD连通图ABCD非连通图两个连通分支{B},{A,C,D}道路与回路定义2.1.4设C是简单图G中含结点数

4、大于3的一个初级回路，如果结点vi和vj在C中不相邻，而边(vi,vj)E(G)，则称(vi,vj)是C的一条弦。道路与回路证明：若对简单图G中每一个vkV(G)，都有d(vk)≥3，则G中必含带弦的回路。证明：在G中构造一条极长的初级道路P=(v0,ei1,v1,ei2,…,vl-1,eil,vl)。由于P是极长的初级道路，所以v0和vl的邻接点都在该道路P上。由已知条件，d(vk)≥3，不妨设Γ(v0)={v1,vij,vik,…},其中1

5、j)就是该回路中的一条弦。带弦回路1.构造极长初级道路(v0,v1),(v0,v1,v2),(v0,v1,v2,v3),(v0,v1,v2,v3,v4)2.Γ(v0)={v1,v2,v3,v4}3.(v0,v1,v2,v3,v0)即为所求的初级回路，而(v0,v2)就是该回路的一条弦v3v2v0v1v4极长初级道路极长初级道路:在无向简单图G=中,E≠∅,设1=v0v1…vl为G中一条初级道路,若路径的两个端点v0和vl不与初级道路本身以外的任何结点相邻,这样的初级道路称为极长初级道路(有向图中,初级道路起点的

6、前驱,终点的后继,都在初级道路本身上)扩大初级道路法扩大初级道路法:任何一条初级道路,如果不是极长初级道路,则至少有一个端点与初级道路本身以外的结点相邻,则将该结点及其相关联的边扩到新的初级道路中来,得到更新的初级道路。继续上述过程,直到变成极长初级道路为止道路与回路定义2.1.5设G=(V,E)是无向图，如果V(G)可以划分为子集X和Y，使得对所有的e=(u,v)E(G),都有u和v分属于X和Y，则称G是二分图(偶图)。完全二分图完全二分图K3,3道路与回路证明：如果二分图G中存在回路，则它们都是由偶数条边组成的。证明

7、：设C是二分图G的任一条回路，不妨设v0X是C的始点，由于G是二分图，所以沿回路C必须经过偶数条边才能达到某结点viX，因而只有经过偶数条边才能回到v0。道路与回路证明：设G是简单图，当m>(n-1)(n-2)/2时，G是连通图。证明：假定G是非连通图，则它至少含有2个连通分支。设分别是G1=(V1,E1),G2=(V2,E2)。其中

8、V1(G1)

9、=n1,

10、V2(G2)

11、=n2,n1+n2=n,

12、E1(G1)

13、+

14、E2(G2)

15、=m。由于G是简单图，因此道路与回路由于1≤n1≤n-1,1≤n2≤n-1所以与已知条件矛

16、盾，故G是连通图。2.3欧拉道路与回路1736年瑞士著名数学家欧拉(LeonhardEuler)发表了图论的第一篇论文“哥尼斯堡七桥问题”．成功地回答了，图中是否存在经过每条边一次且仅一次的回路人们普遍认为欧拉是图论的创始人1936年，匈牙利数学家寇尼格（Konig）出版了图论的第一部专著《有限图与无限