2 第三章图的连通性 主要内容 图的连通性刻画 一、割边、割点和块 二、图的连通度与敏格尔定理 三、图的宽直径简介 教学时数 安排6学时讲授本章内容
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 1 第三章 图的连通性 主要内容 一、割边、割点和块 二、图的连通度与敏格尔定理 三、图的宽直径简介 教学时数 安排6学时讲授本章内容 图的连通性刻画
本次课主要内容 割边、割点和块 (一)、割边及其性质 (二)、割点及其性质 (三)、块及其性质
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 2 本次课主要内容 (一)、割边及其性质 (二)、割点及其性质 (三)、块及其性质 割边、割点和块
研究图的连通性的意义 研究图的连通性，主要研究图的连通程度的刻画， 其意义是： 图论意义：图的连通程度的高低，是图结构性质的重 要表征，图的许多性质都与其相关，例如：连通图中任 意两点间不相交路的条数就与图的连通程度有关。 实际意义：图的连通程度的高低，对应于通信网络 “可靠性程度”的高低。 网络可靠性，是指网络运作的好坏程度，即指如计算 机网络、通信网络等对某个组成部分崩溃的容忍程度。 网络可靠性，是用可靠性参数来描述的。参数主要 分确定性参数与概率性参数
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 3 研究图的连通性的意义 研究图的连通性，主要研究图的连通程度的刻画， 其意义是： 图论意义：图的连通程度的高低，是图结构性质的重 要表征，图的许多性质都与其相关，例如：连通图中任 意两点间不相交路的条数就与图的连通程度有关。 实际意义：图的连通程度的高低，对应于通信网络 “可靠性程度”的高低。 网络可靠性，是指网络运作的好坏程度，即指如计算 机网络、通信网络等对某个组成部分崩溃的容忍程度。 网络可靠性，是用可靠性参数来描述的。参数主要 分确定性参数与概率性参数
确定性参数主要考虑网络在最坏情况下的可靠性度 量，常称为网络拓扑的“容错性度量”，通常用图论概 念给出，其中，本章将介绍的图的连通度就是网络确定 性参数之一。近年来，人们又提出了“坚韧度”、“核 度”、“整度”等描述网络容错性的参数。 概率性参数主要考虑网络中处理器与信关以随机的、 彼此独立的按某种确定性概率损坏的情况下，网络的可 靠性度量，常称为网络拓扑的“可靠性度量”。 (一)、割边及其性质 定义1边e为图G的一条割边，如果 w(G-e)>o(G)。 红色边为该图的割边
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 4 确定性参数主要考虑网络在最坏情况下的可靠性度 量，常称为网络拓扑的“容错性度量”，通常用图论概 念给出，其中，本章将介绍的图的连通度就是网络确定 性参数之一。近年来，人们又提出了“坚韧度”、“核 度”、“整度”等描述网络容错性的参数。 概率性参数主要考虑网络中处理器与信关以随机的、 彼此独立的按某种确定性概率损坏的情况下，网络的可 靠性度量，常称为网络拓扑的“可靠性度量”。 (一)、割边及其性质 定义1 边e为图G的一条割边，如果 ( ) ( ) G e G − 。 红色边为该图的割边
注：割边又称为图的“桥”。 图的割边有如下性质： 定理1边e是图G的割边当且仅当e不在G的任何圈中。 证明：可以假设G连通。 “必要性” 若不然。设e在图G的某圈C中，且令e=uv. 考虑P=C-e,则P是一条uv路。下面证明G-e连通。 对任意x,y∈V(Ge),由于G连通，所以存在x-y 路Q.若Q不含e,则x与y在Ge里连通；若Q含有e,则可 选择路：x-uPv-y,说明x与y在Ge里也连通。所以， 若边e在G的某圈中，则Ge连通。 但这与e是G的割边矛盾！
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 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 -y 路Q.若Q不含e，则x与y在G-e里连通；若Q含有e，则可 选择路：x -u P v - y,说明x与y在G-e里也连通。所以, 若边e在G的某圈中，则G-e连通。 但这与e是G的割边矛盾！ “必要性