资源描述：
《图的概念与性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图的概念与性质3.1图的概念与性质3.1.1图的定义与表示定义3.1.1图G是一个三元组,其中V(G)是一个非空的结点集(或称顶点集),E(G)是边集,G是从边集E(G)到结点偶对(无序偶或有序偶)集上的函数.例题见书86页图的分类:分为有限图与无限图.本书主要讨论有限图,即结点集与边集均为有限集的图.若边e所对应的偶对是有序的,记为,则称e是有向边(简称弧),a,b分别称为有向边e的始点与终点,并均称为e的端点,称e是关联于结点a和b的,结点a和结点b是相邻的,或称
2、结点a和结点b是邻接的.若边e所对应的偶对是无序的,记为(a,b),则称e是无向边(简称棱).除无起始点、终点外,其他术语与有向边相同.约定用[a,b]表示或(a,b).将每一条边均为有向边的图称为有向图,每一条边均为无向边的图称为无向图.有向图与无向图可以互相转化.对于无向图,因为边没有方向,就可以看做是边的两个端点没有起始与终止之分,所以,如果将无向图中的每条边都看做是两条方向不同的有向边,这样无向图就可以转化为有向图.如果把有向图中的每条有向边都看做无向边,就可得到一个无向图,此无向图称
3、为原有向图的底图.底图只表示出结点间的连接关系而没有表示出连接边的方向.对于有向图,如果只需要考虑连接关系时,就可以用底图来表示.图中不与任何结点相邻的结点称为孤立结点.全由孤立结点构成的图称为零图.仅由一个孤立结点构成的图称为平凡图.关联于同一结点的一条边称为自回路或环.自回路即可以看做有向边也可以看做无向边.自回路的有无一般不使有关图论的各个结论发生很大变化,所以有时可以略去对自回路的考虑.在无向图中,两结点间(包括结点自身间)若多于一条边,则称这几条边为重边或平行边.两结点a与b间互相平行的边的条
4、数称为以结点a与b为端点的边的重数.仅一条边时重数是1,无边时重数是0.含有重边的图称为多重图.非多重图称为线图.在有向图中,对于边的重数要考虑两结点间边的方向,端点相同,方向不同,则算做不同的边.为方便起见,将有n个结点的图称为n阶图,将具有n个结点和m条边的图称为(n,m)图.定义3.1.2无自回路的线图称为简单图.3.1.2图的基本概念与握手定理定义3.1.3图G=中,与V中结点v(v∈V)相关联的边数,称为该结点度数,记做deg(v),且将△G=max｛deg(v)｜v∈V(G)｝δ(
5、G)=min｛deg(v)｜v∈V(G)｝分别称为G=的最大度和最小度.可以看出,图中结点的度数与边数存在一定的关系,即图中所有结点的度数之和等于图中边数的两倍.对此,欧拉于1736年给出如下的图论基本定理,称为握手定理.定理3.1.1设G是一个图,其结点集合为V,边集合为E,则:证明:因每一条边必关联两个结点,每一条边给予关联的每个结点的度数为1,故在一个图中,结点度数的总和等于边数的两倍.定理3.1.2图中度数为奇数的结点有偶数个.证明:设V1和V2分别是图G中的奇数度数和偶数度数的结点集
6、,则由定理3.1.1可得:在上面的等式中,因2
7、E
8、为偶数,而等式左边的度数为偶数的各结点度数之和为偶数,则前一项奇数度数之和也应为偶数,因此可知度数为奇数的结点一定有偶数个.显然,例7中奇数度数的结点有a和b,共两个.定义3.1.4在有向图中,对于任何结点v,以v为始点的边的条数称为结点的出度;以v为终点的边的条数称为结点的入度;结点的出度和入度之和称为v的度数.在无向图中,结点v的度数与结点v相关联的边的条数相同.孤立结点的度数为零.定理3.1.3在任何有向图中,所有结点的入度之和等于所有结点的出度
9、之和.证明:因每条有向边对应一个入度和一个出度,若一个结点具有一个入度或出度,则必关联一条有向边,故有向图中各结点的入度之和等于边数,各结点的出度之和也等于边数,因此,任何有向图中的入度之和等于出度之和.定义3.1.5设G=是n阶无向图,若能将V分成两个互不相交的子集v1与V2,使得G中任一边的两端点都不在同一个Vi(i=1,2)中,则称G为二部图,记为G=.见例8定义3.1.6简单图G=中,若每一对结点间都有边相连,则称该图为完全图.有n个结点的无向完全图记为Kn
10、.定理3.1.4有n个结点的无向完全图Kn的边数为n(n-1)/2.证明:在Kn中,任意两个结点间都有边相连,n个结点中任取两点的组合数为Cn2=1/2(n(n-1)),故Kn的边数为
11、E
12、=n(n-1)/2.若在Kn中,对每条边任意确定一个方向,就称该图为n个结点的竞赛有向完全图,其边数也为n(n-1)/2.若在n阶图中,每两个结点间都有两条方向不同的边,就称该图为有n个结点的有向完全图,其边数为n(n-1).定义3.1.7若无向简单图中
