第14讲-图的有关概念-节点的度数

第14讲图的有关概念,节点的度数主要内容:1.图的有关概念.2.节点的度数.3.子图与图的同构.Chapter7图论图论的创始人是瑞士数学家L.Euler，他于1736年首次建立“图”模型解决了Köningsberg七桥问题.图论的应用领域非常广泛，它已经渗透到诸如语言学、逻辑学、物理学、化学、电信工程、信息论、控制论、经济管理等各个领域，特别是在计算机科学中的数据结构、计算机网络、计算机软件、算法理论、操作系统、分布式系统、编译程序以及数据挖掘等方面都扮演着重要角色.7.1图的基本概念哥尼斯堡(Köningsberg)七桥问题:问题是:是否可从某一个地方出发，经过七座桥，每座桥只经过一次，然后又回到原出发点.CABD1b2b3b4b5b6b7bCADB1b2b3b4b5b6b7b程序调用的图论模型:e8:v3可调用v2;e1:v2可调用v1;e4:v5可调用v5自身.•单行道;•好感?1v2v3v4v5v1e2e3e4e5e6e7e8e9e1.图的定义由前面的2个例子可以得出Definition图G(graph)主要由2部分组成:(1)节点集合V,其中的元素称为节点(vertex或node).(2)边集合E,其中的元素称为边(edge).通常将图G记为G=(V,E).几点说明:(a)节点又可以称为点、顶点或结点,常用一个实心点或空心点表示,但在实际应用中还可以用诸如方形、圆形、菱形等符号,为了方便可以在这些符号的旁边或内部写上表意名称.(计算机学科中常称节点.)(b)边及其的表示.•无向边?b3=AB=BA={A,B}(可重).•有向边(弧)?所有边都是无向边的图称为无向图(graph,undirectedgraph),所有边都是有向边的图称为有向图(digraph,directedgraph)..,),(32328vvvve(c)图的拓扑不变性质.需要注意的是,我们讨论的图不但与节点位置无关,而且与边的形状和长短也无关.有n个节点的图称为n阶(order)图,有n个节点m条边的图称为(n,m)图.在图G=(V,E)中,称V=的图为空图(emptygraph),记为,若V但E=的图称为零图(discretegraph),n阶零图可记为Nn,仅一个节点的零图称为平凡图(trivialgraph).2.邻接Def设G=(V,E)是图,对于任意u,vV,若从节点u到节点v有边,则称u邻接到(adjacentto)v或称u和v是邻接的(adjacent).无向图?有向图?(无向图的两条边邻接是指它们有公共端点.)euveuvuve3.关联Def设G=(V,E)是图,eE,e的两个端点分别为u和v,则称边e与节点u以及边e与节点v是关联的(incident).显然,图的任意一条边都关联两个节点.关联相同两个节点的边称为吊环,可简称环(loop).关联的起点相同与终点也相同的边称为多重边(multipleedges)或平行边,其边数称为边的重数(multiplicity).例子见书Figure7-4(a)(b).4.简单图(1)简单图Def设G=(V,E)是图,若G中既无吊环又无多重边,则称G是简单图(simplegraph).简单图的例子?彼得森(Petersen,1831~1910)图,它是一个有着特殊性质的简单图,后面会多次出现.(2)完全无向图Def设G=(V,E)是n阶简单无向图,若G中任意节点都与其余n-1个节点邻接,则称G为n阶完全无向图(completegraph),记为Kn.K5:将n阶完全无向图Kn的边任意加一个方向所得到的有向图称为n阶竞赛图..2)1(|)(|nnKEn(3)补图Def设G=(V,E)是n阶简单无向图,由G的所有节点以及由能使G成为Kn需要添加的边构成的图称为G的补图,记为(u和v在G中不邻接u和v在中邻接).GGGG7.2节点的度数边与节点的关联次数?Def设G=(V,E)是无向图,vV,称与节点v关联的所有边的关联次数之和为节点v的度数(degree),记为deg(v).一个环算2度?1v2v3v.3)deg(,5)deg(,2)deg(321vvv2e1e3e4e5eDef设G=(V,E)是有向图,vV,称以v为起点的边的数目为节点的出度(out-degree),记为deg+(v),以v为终点的边的数目为节点的入度(in-degree),记为deg-(v),称deg+(v)+deg-(v)为节点v的度数,记为deg(v).一个环算2度?1v2v3v4v下面的定理是L.Euler在1736年证明的图论中的第一定理,常称为“握手(?)定理”.Theorem在任何(n,m)图G=(V,E)中,其所有节点度数之和等于边数m的2倍,即Corollary在任意图G=(V,E)中,度数为奇数的节点个数必为偶数.Proof.2)deg(mvVv.)deg()deg()deg(2)deg()deg(奇数偶数vvVvvvvm由定理及其推论很容易知道,在任何一次聚会上,所有人握手次数之和必为偶数并且握了奇数次手的人数必为偶数.(环的解释?)在任意有向图中,显然有Theorem在任意有向图中,所有节点的出度之和等于入度之和.在任意图中,度数为0的节点称为孤立点(isolatedvertex),度数为1的节点称为悬挂点(pendantvertex).例7-1(P200)证明:对于任意n(n2)个人的组里,必有两个人有相同个数的朋友.Proof将组里的每个人看作节点,两个人是朋友当且仅当对应的节点邻接,于是得到一个阶简单无向图G,进而G中每节点的度数可能为0,1,2,…,n-1中一个.当G中无孤立点时,于是每节点的度数可能为1,2,…,n-1.由于共有n个节点,于是必有两节点度数相同.当G中有孤立点时,这时每节点的度数只可能为0,1,2,…,n-2.同样由于共n有个节点,因此必有两节点度数相同.若一个无向图G的每节点度数均为k,则称G为k-正则图(k-regulargraph).例子?例7-2(P200)设无向图G是一个3-正则(n,m)图,且2n–3=m,求n和m各是多少?Hint根据握手定理有,3n=2m.Def7-9任意图G=(V,E):有向图G=(V,E):例子?),deg(max)(vGVv).deg(min)(vGVv),(degmax)(vGVv),(degmax)(vGVv),(degmin)(vGVv).(degmin)(vGVv对于无向图G=(V,E),V={v1,v2,…,vn},称deg(v1),deg(v2),…,deg(vn)为的度数序列.对于有向图,还可以定义其出度序列和入度序列.例7-3是否存在一个无向图G,其度数序列分别为(1)7,5,4,2,2,1.(2)4,4,3,3,2,2.Solution(1)由于序列7,5,4,2,2,1中,奇数个数为奇数,根据握手定理的推论知,不可能存在一个图其度数序列为7,5,4,2,2,1.(2)因为序列4,4,3,3,2,2中,奇数个数为偶数,可以得到一个无向图(见图7-11),其度数序列为4,4,3,3,2,2.7.3子图、图的运算和图同构1.子图可以通过一个图的子图去考察原图的有关性质以及原图的局部结构.Def设G=(V,E)和H=(W,F)是图,若WV且FE,则称H=(W,F)是G=(V,E)的子图(subgraph).若H=(W,F)是G=(V,E)的子图且W=V,则称H=(W,F)是G=(V,E)的生成子图(spanningsubgraph).例7-4(一个图的子图较多)常见的4种产生G=(V,E)的子图的方式如下:(1)G[W]设WV,则以W为节点集合,以两端点均属于W的所有边为边集合构成的子图,称为由W导出的子图(inducedsubgraphbyW),记为G[W].1v2v3v4v5v?],,[321vvvG?},,{321vvvGABe(2)G–W设WV,导出子图G[V–W]记为G–W,是在G中去掉所有W中的节点,同时也要去掉与W中节点关联的所有边.通常将G–{v}记为G-v.(3)G[F]设FE,则以F为边集合,以F中边的所有端点为节点集合构成的子图,称为由F导出的子图(inducedsubgraphbyF),记为G[F].(4)G–F设FE,则从G中去掉F中的所有边得到的生成子图记为G–F.1v2v3v4v5vabcdefg?],,[cbaG?},,{cbaG简单图G=(V,E)的补图G+U:(与子图无关).EKGn.}{uvGuvG).,()},{(vuGvuG2.图的运算图的运算就是通过一定的操作,产生“新”的图.前面的子图的产生实际上就是图的运算,但它们都是在一个图中进行讨论的.也便于用代数方法讨论图.在有些问题的讨论中,还会出现两个图之间的一些运算.我们在此仅给出定义,请参见有关文献.Def(1)).,(),,(222111EVGEVG.21GG(2)(3)(4)思考图的每种运算的性质有哪些?它与集合的并、交、差、(补)及环和(对称差)运算的性质有什么不同?.21GG.,),,(12121VVEEEEVGG).()(122121GGGGGG3.图同构由于图的拓扑性质,有可能两个表面上看起来不同的图本质上是同一个图,这就是图同构的问题.Def(见书)直观理解:G1G2是指其中一个图仅经过下列两种变换可以变为另一个图:(a)挪动节点的位置；(b)伸缩边的长短.无向图:不同构的例子P2045.有向图:对于两个有向图同构的判断,特别要注意边的方向的一致性.思考给出至少4个两个图同构的必要条件.1G2G3GUlam猜想?