离散数学第七章(25.26.27;28)

《离散数学第七章(25.26.27;28)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东南大学远程教育离散数学第五十五讲主讲教师：仲新宇第四篇图论图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究，如1736年欧拉（L.Euler)所解决的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题：例如　迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。第四篇图论图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。对于这样一门应用广泛的学科，其包含的内容是丰富的，本篇我们只准备介绍基本的概念

2、和定理，为今后有关学科及课程的学习和研究提供方便。第四篇图论第七章图论§1图的基本概念§2路与回路§3图的矩阵表示§4欧拉图和汉密尔顿图§5平面图§6树与生成树§1图的基本概念1.基本名词和定义《定义》一个图G是一个三元组,其中V(G)为有限非空结点（或叫顶点）集合,E(G)是边的集合，ΦG是从边集E到结点偶对集合上的函数。讨论定义：(1).V(G)={V1，V2，…，Vn}为有限非空集合,Vi称为结点,简称V是点集。(2).E(G)={e1，…，em}为有限的边集合,ei称为边，每个ei都有V中的结点对与之相对应,称E为边集。即每条边是连结V中的某两个点的。§1图

3、的基本概念(3).若Ｇ中每一条边e与有序偶对或无序偶对(vi,vj)相关系，则可说边e连接结点vi和vj(4).可用e＝或e＝(vi,vj)，以结点来表示图的边，这样可把图简化成：Ｇ＝<Ｖ，Ｅ>。例：有图如下，试写成定义表达式Ｇ＝〈Ｖ，Ｅ〉，其中Ｖ＝{v1,v2,v3,v4,v5}Ｅ＝{x1,x2,x3,x4,x5,x6}§1图的基本概念例：对有向图可表示为：Ｇ＝〈Ｖ、Ｅ〉，其中Ｖ＝｛a、b、c、d｝Ｅ＝｛,,,,,｝下面定义一些专门名词：(1)有向边：在图中对应有序偶对的边（或者：在图中带有箭头方向的边或

4、弧线）§1图的基本概念(2)无向边：在图中对应无序偶对的边（或：在图中不带箭头的边）(3)邻接结点：由一条边（有向或无向）连接起来的结点偶对(4)（ｎ，ｅ）图：具有ｎ个结点（顶点），ｅ条边的图(5)有向图：在Ｇ中每一条边均为有向边(5)有向完全图：在n个结点的有向图G=中，如果E＝V×V，则称G为有向完全图。例：东南大学远程教育离散数学第五十六讲主讲教师：仲新宇§1图的基本概念对有向简单完全图讲：ｅ＝＝n(n-1)（没有自回路）§1图的基本概念(6)无向图：每一条边均为无向边的图(7)无向完全图：每两个结点之间均有连线的无向图。n个结点的无向完全图的边数为：例：§1图的基本概念(8)

5、混合图：既有有向边，又有无向边的图(9)互相邻接的边：连接于同一结点的二条（或若干条）边例：§1图的基本概念(10)闭路（自回路）：图中起始且终止于同一结点的边(闭路的箭头方向是没有意义的)例：(11)多重边（平行边）：二个结点之间方向相同的二条（多条）边例：§1图的基本概念《定义》：含有多重边的图称为多重图，非多重图称为线图。简单图：无自回路的线图称为简单图。由定义可见，简单图是没有自回路和多重边的图。例：§1图的基本概念《定义》：有权图（赋权图）Ｇ是一个三元组〈Ｖ、Ｅ、ｇ〉或四元组〈Ｖ、Ｅ、ｆ、ｇ〉，其中Ｖ为结点集合，Ｅ为边的集合，f是定义在Ｖ上的函数，g是定义在边集合Ｅ上的函数。实际上，

6、有权图可以用一句话概括：每一条边或结点均注上数字的图（数字可以为整数、正实数）例：给出一个有权图Ｇ＝〈Ｖ、Ｅ、ｆ、ｇ〉，其图如下：其中Ｖ＝{v1,v2,v3}Ｅ＝{e1,e2}§1图的基本概念(12)孤立结点：不与任何结点相连接的结点(13)零图：仅包含孤立结点的图，又称（ｎ，０）图(14)平凡图：只有一个结点的图（1，0）图《定义》：在有向图中，对于任何结点v，以v为始点的边的条数，称为结点v的引出度数，记作；以v点为终点的边的条数称为v的引入度数，记作结点的v的引入度数和引出度数之和称为v的度数，用deg（v）表示。由定义可见：度数deg（v）＝对无向图讲：结点的度数等于和该结点关联的

7、边的条数§1图的基本概念例：(15)正则图：所有结点均具有同样度数的简单无向图例：§1图的基本概念《定理》：每个图中，结点度数的总和等于边数的两倍。§1图的基本概念例：若图Ｇ有n个顶点，（n+1）条边，则Ｇ中至少有一个结点的度数≥３。证明：设Ｇ中有n个结点分别为v1,v2,…,vn，则由握手定理：而结点的平均度数=∴结点中至少有一个顶点的度数≥３§1图的基本概念《推论》：(1)在图中，所有度数之和