资源描述：
《最新14图的基本概念教学讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、14图的基本概念本章内容14.1图14.2通路与回路14.3图的连通性14.4图的矩阵表示14.5图的运算基本要求作业14.1图的基本概念图的定义图的一些概念和规定简单图和多重图顶点的度数与握手定理图的同构完全图与正则图子图与补图图的一些概念和规定G表示无向图，但有时用G泛指图(无向的或有向的)。D只能表示有向图。V(G)，E(G)分别表示G的顶点集和边集。若
2、V(G)
3、＝n，则称G为n阶图。若
4、V(G)
5、与
6、E(G)
7、均为有限数，则称G为有限图。若边集E(G)＝，则称G为零图，此时，又若G为n阶图，则称G为n阶零图，记作Nn，特别地，称N1为
8、平凡图。在图的定义中规定顶点集V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记为。标定图与非标定图、基图将图的集合定义转化成图形表示之后，常用ek表示无向边(vi,vj)（或有向边），并称顶点或边用字母标定的图为标定图，否则称为非标定图。将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的，任何无向图G的各边均加上箭头就可以得到以G为基图的有向图。关联与关联次数、环、孤立点设G＝为无向图，ek＝(vi,vj)∈E，称vi,vj为e
9、k的端点，ek与vi或ek与vj是彼此相关联的。若vi≠vj，则称ek与vi或ek与vj的关联次数为1。若vi＝vj，则称ek与vi的关联次数为2，并称ek为环。任意的vl∈V，若vl≠vi且vl≠vj，则称ek与vl的关联次数为0。设D＝为有向图，ek＝∈E，称vi,vj为ek的端点。若vi＝vj，则称ek为D中的环。无论在无向图中还是在有向图中，无边关联的顶点均称为孤立点。相邻与邻接设无向图G＝，vi，vj∈V，ek，el∈E。若et∈E，使得et＝(vi，vj)，则称vi与vj是相邻的。若ek与el至少有
10、一个公共端点，则称ek与el是相邻的。设有向图D＝，vi，vj∈V，ek，el∈E。若et∈E，使得et＝，则称vi为et的始点，vj为et的终点，并称vi邻接到vj，vj邻接于vi。若ek的终点为el的始点，则称ek与el相邻。邻域设无向图G＝，v∈V，称{u
11、u∈V∧(u,v)∈E∧u≠v}为v的邻域，记做NG(v)。称NG(v)∪{v}为v的闭邻域，记做NG(v)。称{e
12、e∈E∧e与v相关联}为v的关联集，记做IG(v)。设有向图D＝，v∈V，称{u
13、u∈V∧∈E∧u≠v}为
14、v的后继元集，记做Г+D(v)。称{u
15、u∈V∧∈E∧u≠v}为v的先驱元集，记做Г-D(v)。称Г+D(v)∪Г-D(v)为v的邻域，记做ND(v)。称ND(v)∪{v}为v的闭邻域，记做ND(v)。举例NG(v1)＝Г+D(d)＝{v2，v5}NG(v1)＝{v1，v2，v5}IG(v1)＝{e1，e2，e3}{c}Г-D(d)＝{a，c}ND(d)＝{a，c}ND(d)＝{a，c，d}简单图与多重图定义14.3在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如
16、果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边。含平行边的图称为多重图。既不含平行边也不含环的图称为简单图。例如：在图14.1中，(a)中e5与e6是平行边，(b)中e2与e3是平行边，但e6与e7不是平行边。(a)和(b)两个图都不是简单图。顶点的度数定义14.4设G＝为一无向图，v∈V，称v作为边的端点次数之和为v的度数，简称为度，记做dG(v)。在不发生混淆时，简记为d(v)。设D＝为有向图，v∈V，称v作为边的始点次数之和为v的出度，记做dD-(v)，简记作d-(v)。称v作为边
17、的终点次数之和为v的入度，记做d+D(v)，简记作d+(v)。称d-(v)+d+(v)为v的度数，记做d(v)。图的度数的相关概念在无向图G中，最大度△(G)＝max{d(v)
18、v∈V(G)}最小度δ(G)＝min{d(v)
19、v∈V(G)}在有向图D中，最大入度△+(D)＝max{d+(v)
20、v∈V(D)}最小入度δ+(D)＝min{d+(v)
21、v∈V(D)}最大出度△-(D)＝max{d-(v)
22、v∈V(D)}最小出度δ-(D)＝min{d-(v)
23、v∈V(D)}称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边。度为偶数(奇数)的顶点称为偶度
24、(奇度)顶点。图的度数举例d(v1)＝4(注意，环提供2度)，△＝4，δ＝1，v4是悬挂顶点，e7是悬挂边。d-(a)＝4，d+(a)＝
