欢迎来到天天文库
浏览记录
ID:42751446
大小:961.50 KB
页数:81页
时间:2019-09-21
《第四部分 图论》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第四部分图论第十四章图的基本概念第十五章欧拉图与哈密顿图第十六章树第十七章平面图及图的着色第十四章图的基本概念14.1图无序积A&B={(a,b)
2、a∈A∧b∈B}定义14.1一个无向图是一个有序的二元组,记做G,其中(1)V≠φ称为顶点集,其元素称为顶点或结点。(2)E称为边集,它是无序集V&V的多重子集,其元素称为无向边。简称边。定义14.2一个有向图是一个有序的二元组,记做D,其中(1)V同无向图。(2)E为边集,它是笛卡儿积V×V的多重子集,其元素称为有向边。简称边。如书例14
3、.1其它规定与概念见书P268定义14.3在无向图中,关联一对顶点的无向边如果多于1条,则称这些边为平行边,平行边的条数称为重数。在有向图中,关联一对顶点的有向边如果多于1条,并且这些边的始点与终点相同(也就是它们的方向相同),则称这些边为平行边。含平行边的图称为多重图。既不含平行边也不含环的图称为简单图。定义14.4设G=为一无向图,∀v∈V,称v作为边的端点次数之和为v的度数,简记为度,记做dG(v),在不发生混淆时,简记为d(v)。设D=为有向图,∀v∈V,称v作为边的始点的次数
4、之和为v的出度,记做,简记。称v作为边的终点的次数之和为v的入度,记做,简记作,称为v的度数,记做d(v)。悬挂顶点,悬挂边偶度(奇度)顶点定理14.1(握手定理)设图G=为任意无向图,其中结点集合为V={v1,v2,…,vn},
5、E
6、=m,则定理14.2设有向图D=为任意无向图,其中结点集合为V={v1,v2,…,vn},
7、E
8、=m,则且推论任何图(无向的或有向的)中,奇度顶点的个数是偶数个。定理14.3设非负整数列d=(d1,d2,…,dn),则d是可图化的当且仅当定理14.4设G
9、为任意n阶无向简单图,则例:判断下列各数列哪些可图化?哪些可简单图化?(1)(5,5,4,4,2,1)(2)(5,4,3,2,2)(3)(3,3,3,1)(4)(d1,d2,…,dn),d1>d2>…>dn≥1且∑di为偶数(5)(4,4,3,3,2,2)定义14.5设图G的点集为V,边集为E,图G′的点集为V′,边集为E′。如果存在着V到V′的双射函数f,使对任意的u,v∈V,(u,v)∈E(或∈E),当且仅当(f(u),f(v))∈E′(或∈E′),并且重数相同,则称图
10、G和G′同构,记作G≌G′。abcd例如:1234定义14.6设G为n阶无向简单图,如果任意两个不同的结点之间都有一条边关联,则称G为n阶无向完全图,简称n阶完全图,记作Kn(n≥1)。设D为n阶有向简单图,若D中每个顶点都邻接到其余n-1个顶点,又邻接于其余的n-1个顶点,则称D是n阶有向完全图。设D为n阶有向简单图,若D的基图为n阶无向完全图Kn,则称D是n阶竞赛图。如书图14.4易知:n阶无向完全图,n阶有向完全图,n阶竞赛图的边数分别为定义14.7设G为n阶无向简单图,若∀v∈V(G),均有d(v
11、)=k,则称G为k-正则图。定义14.8设G=,G’=为两个图(同为无向图或同为有向图),若V’⊆V且E’⊆E,则称G’是G的子图,G为G’母图,记做G’⊆G,又若V’⊂V或E’⊂E,则称G’为G的真子图。若V’=V,则称G’为G的生成子图。导出子图如图14.5定义14.9设G=为n阶无向简单图。以V为顶点集,以所有使G成为完全图Kn的添加边组成的集合为边集的图,称为G的补图,记做。若图,则称G是自补图。如图14.6定义14.10设G=为无向图。(1)设e∈E,
12、用G-e表示从G中去掉边e,称为删除边e。又设E’⊂E,用G-E’表示从G中删除E’中所有边,称为删除E’。(2)设v∈V,用G-v表示从G中去掉v及所关联的一切边,称为删除顶点v,又设V’⊂V,用G-V’表示从G中删除V’中所有顶点,称为删除V’。(3)设边e=(u,v)∈E,用Ge表示从G中删除e后,将e的两个端点u,v用一个新的顶点w(或用u或v充当w)代替,使w关联e以外u,v关联的所有边,称为边e的收缩。(4)设u,v∈V(u,v可以相邻,也可能不相邻),用G⋃(u,v)(或G+(u,v))表
13、示在u,v之间加一条边(u,v)称为加新边。如图14.714.2通路与回路定义在无向图(或有向图)G=中,设v0,v1,…,vn∈V,e0,e1,…,en∈E,其中ei是关联于结点vi-1,vi的边,交替序列v0e0v1e1…en-1vn称为联结v0到vn的通路。v0和vn分别称为通路的起点和终点,通路中所含边的条数称为该通路的长度。如果通路中的始点与终点相同,则称这条路为回路。如果经过的边各异,则称此路径为简单通路
此文档下载收益归作者所有