图论第三章图的连通性.pptVIP

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