图论:图的基本概念.pdf

图论:图的基本概念.pdf

ID:58313665

大小:464.88 KB

页数:6页

时间:2020-09-06

图论:图的基本概念.pdf_第1页
图论:图的基本概念.pdf_第2页
图论:图的基本概念.pdf_第3页
图论:图的基本概念.pdf_第4页
图论:图的基本概念.pdf_第5页
资源描述:

《图论:图的基本概念.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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。