离散数学图论图的基本概念

《离散数学图论图的基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论图的基本概念七座桥所有的走法一共有7！=5040种。1736年，在经过一年的研究之后，29岁的欧拉提交了《哥尼斯堡七桥》的论文，圆满解决了这一问题，同时开创了数学新分支---图论。图论在许多应用领域中：地图导航、网络技术研究及程序流程分析都会遇到由“结点”和“边”组成的图在计算机许多学科中如：数据结构、操作系统、网络理论、信息的组织与检索均离不开由这种“结点”和“边”组成的图以及图的特殊形式--树。图与树是建立和处理离散对象及其关系重要工具。如地图导航、周游问题、图像分割等等。一、图的概念1、无序积定义：设A，B为任意的两个集合，称｛｛a，b｝┃a∈A∧b∈B｝为A与B的无序积，记

2、作A&B其元素｛a，b｝可简记为（a，b）2、图的定义1）定义1一个无向图是一个有序的二元组，记作G，其中(1)V≠ø称为顶点集，其元素称为顶点或结点．(2)E称为边集，它是无序积V＆V的多重子集，其元素称为无向边，简称为边．例：无向图G=其中顶点集合V＝｛v1,v2,v3,v4｝边集合E＝｛(v1,v2),(v2,v3),(v3,v2),(v3,v1),(v2,v2),(v2,v2),(v1,v2),｝园括号表示无向边有平行边2）定义2一个有向图是一个有序的二元组，记作D，其中(1)V≠ø称为顶点集，其元素称为顶点或结点．(2)E为边集，它是笛卡儿积Vⅹ

3、V的有穷多重子集，其元素称为有向边，简称边(弧)．有向图D=其中V＝｛v1,v2,v3｝边集合E＝｛,,,,｝（与前面的关系的图表示相当）3、有关图的术语1）用G表示无向图，D表示有向图。有时用V(G)，E(G)分别表示G的顶点集和边集。2）用

4、V(G)

5、，

6、E(G)

7、分别表示G的顶点数和边数若｜V(G)｜＝n，则称G为n阶图。对有向图有相同定义。3）在图G中，若边集E(G)＝ø，则称G为零图若G为n阶图，则称G为n阶零图，记作Nn，特别是称N1为平凡图4）在用图形表示一个图时，若给每个结点和

8、每一条边均指定一个符号（字母或数字），则称这样的图为标定图。5)常用ek表示边(vi，vj)(或)设G＝为无向图，ek=(vi，vj)∈E，则称vi，vj为ek的端点，ek与vi、vj是彼此相关联的．起、终点相同的边称为环不与任何边关联的结点称为孤立点（包括有向图)6）邻接：边的相邻：ek，el∈E．若ek与el至少有一个公共端点，则称ek与el是相邻的顶点的相邻：若∃et∈E，使得et=，则称vi为et的始点，vj为et的终点，并称vi邻接到vj，vj邻接于vi两个结点为一条边的端点，则称两个结点互为邻接点，也称边关联于这两个结点，或称两个结点邻

9、接于此边。7）平行边：在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数．在有向图中，关联一对顶点的有向边如果多于1条，并且它们的方向相同，则称这些边为平行边．8）多重图和简单图：含平行边的图称为多重图既不含平行边也不含环的图称为简单图．（主要讨论简单图）4、结点的度1)定义4设G＝为无向图，∀v∈V，称v作为边的端点的次数之和为v的度数，简称为度，记作dG(v)，简记为d(v)，即为：结点v所关联的边的总条数关于有向图D＝有：∀v∈V，称v作为边的始点的次数之和为v的出度，记作d+(v)，称v作为边的终点的次数之和为v的入度，记

10、作d-(v)称d+(v)+d-(v)为v的度数，记作dD(v).2)称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边根据结点的度数可将结点分为：度为偶数(奇数)的顶点称为偶度顶点(奇度顶点).一个环提供的度为2（有向图的环提供入度1和出度1）3）定义：(G)=max{d(v)

11、v∈V(G)}为图G中结点最大的度δ(G)=min{d(v)

12、v∈V(G)}为图G中结点最小的度简记为、δ定义：－(D)=max{d－(v)

13、v∈V(D)}为图D中结点最大的入度＋(D)=max{d＋(v)

14、v∈V(D)}为图D中结点最大的出度δ-(D)=min{d－(v)

15、v∈V(D)}为图D中结点最

16、小的入度δ＋(D)=min{d＋(v)

17、v∈V(D)}为图D中结点最小的出度5、握手定理（欧拉）1)定理1设G＝为任意无向图,V＝{v1，v2，…，vn},｜E｜=m，则∑d(vi)＝2m(所有结点的度数值和为边数的2倍)证:G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边共提供2m度2)定理2设D＝为任意有向图,V＝{v1，v2，…，vn},

18、E

19、=m，则∑d+(vi)=∑d