文档介绍：图论及其应用
应用数学学院
1
第三章图的连通性
主要内容
一、割边、割点和块
二、图的连通度与敏格尔定理
三、图的宽直径简介
教学时数
安排6学时讲授本章内容
图的连通性刻画
2
本次课主要内容
(一)、割边及其性质
(二)、割点及其性质
(三)、块及其性质
割边、割点和块
3
研究图的连通性的意义
研究图的连通性,主要研究图的连通程度的刻画,其意义是:
图论意义:图的连通程度的高低,是图结构性质的重要表征,图的许多性质都与其相关,例如:连通图中任意两点间不相交路的条数就与图的连通程度有关。
实际意义:图的连通程度的高低,在与之对应的通信网络中,对应于网络“可靠性程度”的高低。
网络可靠性,是指网络运作的好坏程度,即指如计算机网络、通信网络等对某个组成部分崩溃的容忍程度。
网络可靠性, 是用可靠性参数来描述的。参数主要分确定性参数与概率性参数。
4
确定性参数主要考虑网络在最坏情况下的可靠性度量,常称为网络拓扑的“容错性度量”,通常用图论概念给出,其中,本章将介绍的图的连通度就是网路确定性参数之一。近年来,人们又提出了“坚韧度”、“核度”、“整度”等描述网络容错性的参数。
概率性参数主要考虑网络中处理器与信关以随机的、彼此独立的按某种确定性概率损坏的情况下,网络的可靠性度量,常称为网络拓扑的“可靠性度量”。
(一)、割边及其性质
定义1 边e为图G的一条割边,如果。
红色边为该图的割边
5
注:割边又称为图的“桥”。
图的割边有如下性质:
定理1 边 e 是图G的割边当且仅当 e 不在G的任何圈中。
证明:可以假设G连通。
若不然。设 e 在图G的某圈 C 中,且令e = u v.
考虑P = C- e,则P是一条u v路。下面证明G-e连通。
对任意 x, y V(G-e) 由于G连通,所以存在x ---,则x与y在G-e里连通;若Q含有e,则可选择路:x ---u P v --- y,说明x与y在G-e里也连通。所以,若边e在G的某圈中,则G-e连通。
但这与e是G的割边矛盾!
“必要性”
6
“充分性”
如果e不是G的割边,则G-e连通,于是在G-e中存在一条u --- v 路,显然:该路并上边e得到G中一个包含边e的圈,矛盾。
推论1 e为连通图G的一条边,如果e含于G的某圈中,则G-e连通。
证明:若不然,G-e不连通,于是e是割边。由定理1,e不在G的任意圈中,矛盾!
例1 求证: (1) 若G的每个顶点的度数均为偶数,则G没有割边; (2) 若G为k正则二部图(k≧2),则G无割边。
证明: (1)若不然,设e=uv 为G的割边。则G-e的含有顶点u的那个分支中点u的度数为奇,而其余点的度数为偶数,与握手定理推论相矛盾!
7
(2)若不然,设e=uv 为G的割边。取G-e的其中一个分支G1, 显然,G1中只有一个顶点的度数是k-1,其余点的度数为k。并且G1仍然为偶图。
假若G1的两个顶点子集包含的顶点数分别为m与n,并且包含m个顶点的顶点子集包含度为k-1的那个点,那么有:k m-1= k n。但是因k≧2,所以等式不能成立!
注:该题可以直接证明G中任何一条边均在某一圈中,由定理1得出结论。
边割集简介
边割集跟回路、树等概念一样,是图论中重要概念。在应用上,它是电路网络图论的基本概念之一。所以,下面作简单介绍。
8
定义2 一个具有n个顶点的连通图G,定义n-1为该连通图的秩;具有p个分支的图的秩定义为n-p。记为R(G)。
(1) R (G-S) = n-2;
定义3 设S是连通图G的一个边子集,如果:
(2) 对S的任一真子集S1,有R(G-S1)=n-2。
称S为G的一个边割集,简称G的一个边割。
例2 边子集:S1={a, c, e}, S2={a, b, },S3={f}是否是下图G的边割?
a
g
e
d
c
b
h
f
i
图G
9
解: S1不是;S2与S3是。
定义4 在G中,与顶点v关联的边的集合,称为v的关联集,记为:S (v)。
a
g
e
d
c
b
h
f
i
图G
例3 关联集是割集吗?为什么?
答:不一定!如在下图中,关联集{a,c,e}是割集,但是,关联集{d,e,f}不是割集。
10