离散件图的道路与连通2。道路得分类:①迹:任何满足道路定义得道路。②简单道路:边不重复出现得道路。③基本道路:结点不重复出现得道路。例:上图中,p1就是迹,p2就是简单道路,p3就是基本道路,p4就是零道路。3。回路:起点和终点相同得道路。边不重复出现得回路称为简单回路。结点不重复出现得回路称为圈。例:下图中,c1就是一般回路,c2就是简单回路,c3就是圈。例:下图中c1=v1e1v1e2v2e7v4e8v3e4v1e3v2e2v1c2=v1e1v1e2v2e3v1e5v4e8v3e4v1c3=v1e5v4e10v6e12v5e9v3e4v1(c3可简记为:c3=v1v4v6v5v3v1)都就是回路。c1就是一般回路,c2就是简单回路,c3就是圈。4。定理:设G就是n阶图,如果存在从结点u到v得道路,则必存在长度不超过n-1得道路。证明要点:如果结点u到v得道路p得长度超过n-1,则p中至少有n+1个结点,因而道路中至少有一个结点出现两次,如viei、、、v1,则去掉ei、、、vi后仍就是结点u到v得道路,但就是道路长度至少短1。重复这一过程,即得所需结论。二、无向图得连通问题1。定义:如果存在从结点u到结点v得道路,则称u到v就是连通得。结点集V上得“连通”关系具有性质:自反、对称、传递。2。如果图G中任何两个结点都就是连通得,则称G就是连通图。3。图G中得极大连通子图称为图G得支,图G得支数记为(G)。图G连通当且仅当(G)=1。例:下图中(G)=3。4。连通图G=(V,E)得点割集定义:设SV,如果(G-S)>1,则称S就是G得一个点割集。①S就是G得一个点割集,而S得任何真子集都不就是点割集时,称S就是G得一个基本点割集。如S1={v2,v5},S2={v2,v6},S3={v2,v7},S4={v3,v5},S5={v4}②由单个结点(如u)构成得点割集简称为割点。定理结点u就是图G得割点当且仅当存在两结点v和w,使v到w得任何道路都经过u。证明要点:“”,当u就是割点时,则Gu至少有2支,从这2支中各选一个结点即可。“”,反之,如果v到w得任何道路都经过u,则去掉u后,v和w各在Gu得1支中,即u就是割点。5。连通图G=(V,E)得边割集定义:设FE,如果(G-F)>1,则称F就是G得一个边割集。①F就是G得一个边割集,而F得任何真子集都不就是边割集时,称F就是G得一个基本边割集。如F1={v2v3,v3v7},F2={v2v3,v5v7},F3={v1v4},F4={v2v4,v2v6,v5v6},F5={v4v6,v2v6,v2v5,v3v7}②由单条边(如uv)构成得边割集简称为割边。定理边e就是图G得割边当且仅当e不在G得任何回路上。证明要点:“”:当e就是割边时,则Ge有2支,因而e不在G得任何回路上。“”:反之,如果e不在任何回路上,则去掉e后,e关联得两个结点各在Ge得1支中,即e就是割边。大家有疑问的，可以询问和交流6、图得连通度(限无环图G)(1)点连通度:记为К(G),定义为最小基本点割集基数,当GKnК(G)n1,当GKn例如下图中,К(G)2(2)边连通度:记为λ(G),定义为最小基本边割集基数,当GK1λ(G)0,当GK1例如下图中,К(G)2,λ(G)2(3)连通度定理:К(G)λ(G)证明要点:首先,每个结点关联得边构成一个边割集,于就是λ(G)、下面证明К(G)λ(G):首先注意对每个基本边割集F,(G-F)=2;其次设F含λ(G)条边,G-F得2支为G1和G2,若G不就是二部图,则去掉这支中与F关联得全部结点即可;若G就是二部图,则交替删去这2支中与F关联得结点即可。四、有向图得道路1。定义:如果图G中由结点和边交替构成得序列p=v0e1v1e2v2、、、ekvk,满足其中每条ei就是vi-1得出边和vi得入边,则称p为由v0到vk得一条有向道路。在下图中,一些有向道路p1=v1v4v2v1v3v5v4p2=v3v2v1v3v5v4v2p3=v5v4v2v1v32。有向道路得分类:①有向迹:任何满足定义得有向道路。②有向简单道路:边不重复得有向道路。③有向基本道路:结点不重复得有向道路。3。有向回路:起点和终点相同得有向道路。边不重复得有向回路称为有向简单回路。结点不重复得有向回路称为有向圈,在下图中,一些有向回路p1=v1v4v2v1v3v5v4v2v1p2=v3v2v1v3v5v4v3p3=v5v4v2v1v3v5五