图论：图的基本概念.pdf

《图论：图的基本概念.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章图的基本概念6.2无向图的基本定义设V是一个非空集合,EP2(V),二元组(V,E)称为一个无向图,V中元素称为无向图的顶点，V为顶点集；E的元素称为图的边，E称为边集。(P(V)是V的子集)1.基本术语(1)简单图如果一个图的：1.每个顶点都没有圈2.任意两个顶点间最多只有一条边(2)表示任意一条边都可用它的两个端点来表示，如x=uv(或x=vu)，用小写的英文字母u,v,w表示图的顶点(可以带下标)，常用小写的英文字母x,y,z表示图的边(可以带下标)(3)(p,q)图如果V=p,E=q，则称G为一个(p,q)图，即G是一个具有p个顶点q条边的图。特别

2、的：称(1,0)图又称为平凡图(4)顶点之间邻接如果{u,v}E，则称u与v邻接(5)顶点和边的关联(四种表达图的边的方法)1.x=uv(x=vu)2.u和v时边x的端点3.顶点u和v与边x互相关联4.u和v邻接(6)边与边的邻接若x与y是图G的两条边,并且仅有一个公共端点,即x∩y=1,则称边x与y邻接(7)图的关系表示一个无向图G就是一个非空集合V上定义的一个反自反且对称的二元关系E和V构成的系统(8)伪图1.带环图联结一个顶点与其自身的边称为环，允许有环存在的图称为带环图2.多重边图如果允许两个顶点之间有两个以上的边存在，这样的边称为多重边，允许有多重边存在的

3、称为多重边图Tips:允许有环与多重边存在的图，我们称为伪图(9)零图设G=(V,E)为无向图,如果E=,则称G为零图于是，n个顶点的零图称为n阶零图(10)完全图设G=(V,E)为无向图,如果G中任意两个顶点间都有唯一的边，则称G为完全图。于是，n个顶点的完全图用Kn表示n(n‒1)显然的，Kn有2条边2.有向图简介设V为一个非空有限集：AVV{(u,u)V},二元组D=(V,A)称为一个有向图,V中的元素称为D的顶点,A中元素(u,v)称为D的从u到v的弧或有向边Tips:(1)有向图不做要求(2)有向图中不能有自己指向自己的圈(1)性质(1)具有n个定点的

4、有向图有2n+1个(?)(2)基本术语1.弧,对称弧---->边:有向图的边也叫做弧。如果x=(u,v)与y=(v,u)均为A的弧,则称x与y为一对对称弧2.弧的起点和终点---->边的端点如果x=(u,v)是有向图的一条边，则称弧x为起于顶点u终于顶点v的弧,或从u到v的弧，u称为x的起点,v为终点3.定向图---->None不含对称弧的有向图称为定向图3.子图设G=(V,E)是一个图，图H=(V1,E1)称为G的一个子图,其中V1是V的非空子集且E1是E的子集如果G1是G的子图,则说G包含G1Tips:1.注意，顶点集合非空pk(k‒?)?2.显然的，Kn有∑?(?,

5、?)·2个子图?=?k(?‒?)(先从p个顶点中选出k个(k>0),一个Kk有?条边，于是，每条边的去留就构成选择，由乘法原理得出)(?)(1)真子图G1是图G的两个子图，如果G1G,则称G1是G的真子图(2)生成子图设G=(V,E)是一个图,如果FE,则称G的子图H=(V,F)为G的生成子图Tips:1.生成子图中包含原图的所有顶点n(?‒?)?2.显然的，Kn有2生成子图表示设x是G的一条边,则G的生成子图(V,E{x})简记为G-x(生成子图只能去边)如果u和v是G的两个不邻接的顶点,则图(V,E∪{u,v})简记成G+uv,它是在G的图解中,把u与v

6、间联一条线而得到的图(3)极大子图设G的子图H具有某种性质,若G中不存在与H不同的具有此性质且包含H的真子图,则称H是具有此性质的极大子图Tips:极大子图必须指明时什么性质极大子图必须是子图(4)导出子图设S为图G=(V,E)的顶点集V的非空子集,则G的以S为顶点集的极大子图称为由S导出的子图,记为.形式地,=(S,P2(S)∩E).Tips：(1)导出子图是极大子图的一种，其指明的性质是：包含若干顶点(2)顶点关联的边也会去掉表示：设G=(V,E),vV,由V{v}导出的子图记成G-v.从图的图解上看,G-v的图解是从G的图中去掉顶点v及

7、与v关联的边所得到的图解4.图的同构设G=(V,E),H=(U,F)是两个无向图.如果存在一个一一对应:VU,使得uvE当且仅当(u)(v)F,则称G与H同构,记为GH仅考虑图的几何表示，则同构的图可以在变换后重合乌拉姆猜想设G=(V,E),H=(U,F)是两个图，V={v1,v2,...,vp}，U={u1,u2,...,up},p≥3.如果对每个i,G-viH-ui,则GH5.顶点的度(这是一个非常重要的概念，就像矩阵的秩一样)设v为图G=(V,E)的任一顶点,G中与v关联的边的数目称为顶点v的度,记为d