图的基本概念(2).pptVIP

第7章 图的基本概念 7.1 图的定义及相关术语 7.2 通路回路图的连通性 7.3 图的矩阵表示 7.4 例题选解 习 题 八 7.2 通路、回路、图的连通性 定义7.2.1 给定图G=〈V,E〉，图中的一条通路是一个点、边交替的序列: ? v i1 e i1 v i2 e i2 …v ip-1 e ip-1 v ip 其中v ik ∈V，e ik ∈E（其中e ik =（v ik ,v ik+1）或者e ik =〈v ik ，v ik+1 〉），v i1 、v ip分别称为通路的起点和终点，当其重合时通路称为回路。 一条通路中所包含的边数称为此路的长度。 由定义可知，一条通路即是G的一个子图，通 路允许经过的顶点或边重复，因此根据不同要求通路可以作如下的划分： 简单通路（迹） 顶点可重复但边不可重复的通路。 初级通路（路径） 顶点不可重复的通路。 简单回路（闭迹） 边不重复的回路（顶点数大于等于3）。 初级回路（圈） 顶点不可重复（仅起点、终点重复）的回路。 一般称长度为奇数的圈为奇圈，称长度为偶数的圈为偶圈。 显然，初级通路必是简单通路，非简单通路称为复杂通路。 在应用中，常常只用边的序列表示通路，对于简单图亦可用顶点序列表示通路，这样更方便。 定理7.2.1 在一个n阶图中，若从顶点u到顶点v（u≠v）存在通路，则必存在从u到v的初级通路且路长小于等于n-1。 证明 设L=ue1v1e2v2…epv是图中从u到v的通路, 若其中顶点没有重复，则L是一条初级通路。 否则必有t、s（1≤t＜s≤p-1），使得vt=vs，此时从L中去掉从vt到vs之间的一段路后，所得仍为从u到v的通路，重复上述动作直到顶点无重复为止，所得通路即为由u到v的初级通路。 例1 一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？ 解 这是通路问题的一个典型实例。用f表示人，w表示狼，s表示羊，h表示草。 集合{f，w，s，h}中能平安在一起的子集有： {f，w，s，h}，{f，w，s}，{f，s，h}，{f，w，h}， {f，w}，{f，s}，{f，h}，{w，h}，{f}，{w}，{s}，{h} 用顶点表示渡河过程中的状态，状态是二元组： 第一元素是集合{f，w，s，h}在渡河过程中留在原岸的子集，第二元素是在彼岸的子集，将一次渡河后代表状态变化的顶点间连边，得图8.2.1。 容易看出，一条路径就是一种渡河方案。 1.无向图的连通性 定义7.2.2 在无向图G中，若顶点u与v之间存在通路，则称u与v是连通的，规定任何顶点自身是连通的。 若G是平凡图或G中任二顶点均连通，则称G是连通图，否则称G是非连通图或分离图。 如果我们在G的顶点集V上定义一个二元关系R： R={〈u,v〉|u、v∈V且u与v是连通的} 容易证明，R是自反的、对称的、传递的，即R是一个等价关系，于是R可将V划分成若干个非空子集：V1，V2，…，Vk，它们的导出子图G［V1］，G［V2］，…，G［Vk］构成G的连通分支，其连通分支的个数记作P（G）。 显然，G是连通图，当且仅当P（G）=1。 例如,图8.2.2所示的图G1是连通图,P（G1）=1,图G2是一个非连通图, P（G2）=3。 例2 求证：若图中只有两个奇度数顶点，则二顶点必连通。 证明 用反证法来证明。 设二顶点不连通，则它们必分属两个不同的连通分支，而对于每个连通分支，作为G的子图只有一个奇度数顶点，余者均为偶度数顶点，与握手定理推论矛盾，因此，若图中只有两个奇度数顶点，则二顶点必连通。 例3 在一次国际会议中，由七人组成的小组{a,b,c,d,e,f,g}中，a会英语、阿拉伯语；b会英语、西班牙语；c会汉语、俄语；d会日语、西班牙语；e会德语、汉语和法语；f会日语、俄语；g会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？ 解