资源描述：
《无向图及有向图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学CH7图的基本概念1无向图及有向图1图论的起源图论是组合数学的一个分支,它起源于1736年欧拉的第一篇关于图论的论文，这篇论文解决了著名的“哥尼斯堡七桥问题”，从而使欧拉成为图论的创始人。1.哥尼斯堡七桥问题哥尼斯堡位于前苏联的加里宁格勒，历史上曾经是德国东普鲁士省的省会，普雷格尔河横穿城堡，河中有两个小岛，共有七座桥连接两岸和小岛。问题：在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？哥尼斯堡七桥问题解决方式莱昂哈德·欧拉（LeonhardEuler）在1735年圆满地解决了这一问题，证明这种方法并不存在，也顺带解决了一笔画问题。他在圣彼得堡科学院发表了图论史上
2、第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数。→→图论的起源欧拉最后给出任意一种河──桥图能否全部走一次的判定法则。如果通奇数座桥的地方不止两个，那么满足要求的路线便不存在了。如果只有两个地方通奇数座桥，则可从其中任何一地出发找到所要求的路线。若没有一个地方通奇数座桥，则从任何一地出发，所求的路线都能实现，他还说明了怎样快速找到所要求的路线。不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的图论。5欧拉图定义一个图,如果能够从一点出发,经过每条边一次且仅一
3、次再回到起点,则称为欧拉图欧拉在论文中给出并证明了判断欧拉图的充分必要条件定理,并证明了七桥图不是欧拉图。从这个问题可以看出：图：图用点代表各个事物,用边代表各个事物间的二元关系。所以，图是研究集合上的二元关系的工具，是建立数学模型的一个重要手段。2、一百多年以后“七桥”问题以后，图论的研究停滞了一百多年，直到1847年，基尔霍夫用“树”图解决了电路理论中的求解联立方程的问题，十年后凯莱用“树”图计算有机化学中的问题。在这一时期流行着两个著名的图论问题：哈密尔顿回路问题和“四色猜想”问题。3.哈密尔顿回路问题1856年,英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正十二面体的二十
4、个顶点上标上二十个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市一次且仅一次，然后回到出发点。哈密尔顿回路图此路线称为：哈密尔顿回路，而此图称为：哈密尔顿图。4、“四色猜想”问题人们在长期为地图(平面图)上色时发现，最少只要四种颜色，就能使得有相邻国界的国家涂上不同的颜色四色猜想的证明一直没有解决，直到一百多年后，在计算机出现以后，于1976年用计算机算了1200多小时，才证明了四色猜想问题。5、又过了半个世纪四色猜想问题出现后，图论的研究又停滞了半个世纪，直到1920年科尼格写了许多关于图论方面的论文，并于1936年发表了第一本关于图论的书。此后图论从理论上到应用上都有了很大
5、发展。特别是计算机的出现使图论得到飞跃的发展。学好图论十分重要图论是组合数学的一个分支，与其它数学分支如群论、矩阵论、集合论、概率论、拓扑学、数值分析等有着密切的联系。图论给含有二元关系的系统提供了数学模型，因而在许多领域里都具有越来越重要的地位，并且在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。从二十世际50年代以来，由于计算机的迅速发展，有力地推动了图论的发展，使得图论成为数学领域里发展最快的分支之一。第7章图的概念本章学习：1.无向图及有向图2.通路、回路、图的连通性3.图的矩阵表示4.最短路径及关键路径14今日内容无向图及有向图图的一些相关概念度握手定理子图相关概念图同
6、构15预备知识有序积:A×B={
7、x∈A∧y∈B}有序对:≠无序积:A&B={(x,y)
8、x∈A∧y∈B}无序对:(x,y)=(y,x)多重集:{a,a,a,b,b,c}≠{a,b,c}重复度:a的重复度为3,b的为2,c的为1161、无序积：A&B设A、B为两集合，称{{a,b}
9、a∈A∧b∈B}为A与B的无序积，记作A&B。为方便起见，将无序对{a,b}记作(a,b)。(a,b)＝(b,a)例：设A={a,b},B={c,d},则A&B＝？A&A＝？A&B={(a,c),(a,d),(b,c),(b,d)}A&A={(a,a),(a,b),(b,b)}1
10、72、无向图一个无向图G是一个二元组,即G=,其中:①.V是一个非空集合,称为G的顶点集,V中元素称为顶点或结点;②.E是无序积V&V的一个多重子集,称E为G的边集,E中元素称为无向边或简称边。•用小圆圈表示V中顶点,若(a,b)∈E,就在a,b之间连线段表示边(a,b),其中顶点的位置、连线的曲直及是否相交都无关紧要。18无向图示例给定无向图G＝，其中V＝{v1,v2,v3,v4,v5}， E={(v
