资源描述：
《离散数学 图论》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第六章图论基础图是建立和处理离散数学模型的一种重要工具。图论是一门应用性很强的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立图论模型来解决。随着计算机科学的发展，图论的应用也越来越广泛，同时图论也得到了充分的发展。这里将主要介绍与计算机科学关系密切的图论的内容。6.1图的基本概念我们已知集合的笛卡尔积的概念，为了定义无向图，还需要给出集合的无序积的概念。任意两个元素a,b构成的无序对（Unorderedpair）记作(a,b)，这里总有。设为两个集
2、合，无序对的集合称为集合A与B的无序积（UnorderedProduct），记作。无序积与有序积的不同在于。例如，设，，则,。为了引出图的定义，我们先介绍如下的例子。MHBS图6.1-1starts=0,i=1i=1i=11?i=i+1s=s+1printsendNY图6.1-2例6.1-1(1)北京、上海、香港、澳门是中国的几个著名的城市，分别用字母表示为,城市的集合为，这些城市间现有的航空线的集合是。我们也可以将这些城市间的航空线关系用图6.1-1来表示。⑵的程序框图如图6.1-21586.1.1图的定义及相关概念定义6.1-1一个无向图(
3、UndirectedGraph)G是一个有序二元组，记作，其中是一个非空集合，V中的元素称为结点或顶点（Vertex）；E是无序积的多重子集（元素可重复出现的集合），称E为G的边集(EdgeSet)，E中的元素称为无向边或简称边(Edge)。在一个图中，为了表示V和E分别是图G的结点集和边集，常将V记成，而将E记成。以上给出的是一个无向图的数学定义。它们可以用图形来表示，而这种图形有助于我们理解图的性质。在这种表示法中，每个结点用点来表示，每条边用线来表示，这样的线连接着代表该边端点的两个结点。例如,,G的图形如图6.1-3所示。图6.1-4图
4、6.1-3定义6.1-2 一个有向图(DirectedGraph)G是一个有序二元组，记作，其中V是一个非空的结点（或顶点）集；E是笛卡尔积V×V的多重子集，其元素称为有向边(DirectedEdge)，也简称边或弧(Arc)。对于一个有向图G，一般也可画出图形来表示。例如，其中,,的图形为图6.1-4。给图的结点标以名称，如图6.1-3中的这样的图称为标定图(Labledgraph)。同时也可对边进行标定，图6.1-3中,,,,,.当时,称和是的端点（或顶点）(EndPoint)，并称与和是关联的(Incidence)，而称结点与是邻接的(A
5、djacent)。若两条边关联于同一个结点，则称两边是邻接的(Adjacent)。无边关联的结点称为孤立点(Isolatedpoint)；若一条边关联的两个结点重合，则称此边为环(Ring)或自回路(Selfcircuit)。若，则称与（或）关联的次数是1;若，称与关联的次数为2；若不是的端点，则称与的关联次数为0158（或称e与u不关联）。在图6.1-3中，,,是的端点，与、的关联次数均为1，是孤立点，是环，与关联的次数为2。当是有向边时，又称是的始点(InitialPoint)，是的终点(TerminalPoint)。如果图的结点集和边集都
6、是有限集，则称图为有限图(Finitegraph)，本书讨论的图都是有限图。若图中,,为了方便起见，这样的图也称为图，有时也简称阶图。这时图称为零图(NullGraph)，图称为平凡图(TrivialGraph)。关联于同一对顶点的两条边称为平行边(ParallelEdge)（若是有向边方向应相同），平行边的条数称为边的重数。不含平行边和环的图称简单图(SimpleGraph)。在本书中除非特别声明，一般是指简单图。6.1.2结点的度定义6.1-3设为一无向图，,关联边的次数称为v的度数，简称度(Degree)，记作的d(v)。设为一有向图，,
7、v作为边的始点的次数，称为v的出度(OutDegree)，记作；v作为边的终点的次数称为v的入度(InDegree)，记作；v作为边的端点的次数称为v的度数，简称度(Degree)，记作，显然。在图6.1-3中，，，，；在图6.1-4中，，，,,。称度为1的结点为悬挂点(Hangingpoint)，与悬挂点关联的边称为悬挂边(Hangingedge)。如图6.1-3中，是悬挂点，是悬挂边。记,,分别称为图的最大度(MaxDegree)和最小度(MinDegree)。若是有向图，除了,，还有如下的定义最大出度最大入度最小出度最小入度图6.1-4中
8、,,,,,,.例6.1-2在图6.1-3中而该图有６条边，即结点度数和是边数的２倍。事实上这是图的一般性质。158定理6.1-1设图为具有结点集的图，
