资源描述：
《离散数学ch04图论基本概念ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学DiscreteMathematics计算机与信息工程学院第4章图论内容提要图的基本概念4.1连通图4.34.4图的矩阵表示路和回路4.2内容提要欧拉图和哈密顿图4.5二部图及匹配4.74.8平面图树4.6有趣的图论问题能否从河岸或小岛出发，通过每一座桥，且仅通过一次回到原地？问题图论是一个重要的数学分支。数学家欧拉1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。以及在民间广为流传的一些游戏问题：例如 迷宫问题、棋盘上马的行走路线问题等等。这些古老
2、的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。有趣的图论问题（0，0）（0，3）（3，0）（5，1）（0，1）（1，0）（1，3）（3，3）（5，0）（2，3）（2，0）（0，2）（5，2）（4，3）（4，0）（5，3）图有趣的图论问题一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？有趣的图论问题解这是通路问题的一个典型实例。用f表示人，w表示狼，s表示羊，h表示草。集合{f，w
3、，s，h}中能平安在一起的子集有：{f，w，s，h}，{f，w，s}，{f，s，h}，{f，w，h}，{f，w}，{f，s}，{f，h}，{w，h}，{f}，{w}，{s}，{h}。用顶点表示渡河过程中的状态，状态是二元组：第一元素是集合{f，w，s，h}在渡河过程中留在原岸的子集，第二元素是在彼岸的子集，将一次渡河后代表状态变化的顶点间连边，得图。容易看出，一条路径就是一种渡河方案。有趣的图论问题有趣的图论问题图可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。一个图是由一些结点和连接两结点间的连线组成,至于连线的长短、
4、曲直及结点的位置是无关紧要的.4.1图的基本概念4.1图的基本概念下面表示的是同一个图什么是图?可用一句话概括图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。因为它显得太抽象，不便于理解，所以有必要给出另外的回答。下面便是把图作为代数结构的一个定义。4.1图的基本概念定义1一个图G定义为一个三元组，记作G=。其中V是个非空有限集合，它的元素称为结点；E也是个有限集合，其元素称为边，而φ是从E到V中的有序对或无序对的映射。4.1图的基本概念由定义可知，图G中的每条边都与图中的无序或有序结点对相联系的
5、。若边e∈E与无序结点对（vi，vj）相联系，则φ(e)=（vi，vj），这时边e称为无向边，有时简称为边；若边e∈E与有序结点对相联系，则φ(e)=，此时边e称为有向边或弧，vi称为弧e的始结点，vj称为弧e的终结点。4.1图的基本概念【例4.1】G=V(G),E(G),G其中：V(G)={a,b,c,d}E(G)={e1,e2,e3,e4}G：G(e1)=(a,b)G(e2)=(b,c)G(e3)=(a,c)G(e4)=(a,a)试画出G的图形。4.1图的基本概念【例4.1】解：G的图形如图所示。4.
6、1图的基本概念定义2在图G=中，如果每条边都是弧，该图称为有向图；若每条边都是无向边，该图G称为无向图；如果有些边是有向边，另一些边是无向边，图G称为混合图。4.1图的基本概念4.1图的基本概念有向图无向图混合图定义3在有向图G=中，对任意结点v∈V，以v为始结点的弧的条数，称为结点v的出度，记为d+(v)；以v为终结点的弧的条数，称为v的入度，记作d-(v)；结点v的出度与入度之和，称为结点的度数(degree)，记为d(v)，显然d(v)=d+(v)+d-(v)。一个度数为0的结点称为孤立结点（isolatedvertex）
7、。4.1图的基本概念对于无向图G=，结点v∈V的度数等于联结它的边数，也记为d(v)。注意：若v点有环，规定该点度因环而增加2。4.1图的基本概念对于无向图G=，记Δ(G)或Δ=max{d(v)
8、v∈V}δ(G)或δ=min{d(v)
9、v∈V}它们分别称为图G的最大度和最小度。4.1图的基本概念例4.1图的基本概念关于无向图中的结点的度，欧拉给出一个定理，这是图论中的第一个定理。定理4.1.1握手定理：图中结点度数的总和等于边数的两倍.一个图中有10个结点，每个结点的度数为6,图中有多少条边？？结点度数总和：610=60因为2
10、e=60，所以e=30.解：4.1图的基本概念推论：在任何图中,度数为奇数的结点必定是偶数个.下面哪些可以作为一个图的度数
