离散数学 图论课件.ppt

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

1、第四篇图论主要内容第七章无向图第八章有向图第七章无向图主要内容7.1三个古老的问题7.2若干基本概念7.3路径、圈及连通性7.4Euler图和Hamilton图7.5平面图7.6图的着色7.7树与生成树7.1三个古老的问题——图论的起源第一个图论问题Könisberg’ssevenbridgeproblem(哥尼斯堡七桥问题)七桥问题与一笔画ABDC是否可从某处出发经过每座桥恰只一次,然后再回到起点？瑞士数学家Euler在1736年证明此问题无解Euler——图论之父环游世界与Hamilton问题十二面体的20个顶点代表世界上20个城市，能

2、否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？Hamilton圈（环球旅行游戏）地图着色与四色问题任意一张地图，最少需要用多少颜色來着色，才能让相邻的两块涂上不同的颜色？1852年提出四色猜想1879年A.Kempe宣布证明了四色定理1890年Heawood发现Kempe的错误1976年美国数学家K.Appel及W.Haken在计算机的辅助下解決图论的应用广播频道与着色问题当两个广播电台距离太近时,若给它们相同的频道会产生干扰。如何设置每个电台的频道,使得它们既不相互干扰,又使频道总数最少?AB广播频道与着色问题图的点

3、着色(Coloring)药品存放与无关集化学药品存放问题某些药品放置太近可能爆炸，有两个实验室，最多能有多少药品能放在一起碰!!药品存放与无关集配对问题与匹配(Matching)配对问题有一些机器人要分配任务，并不是所有机器人都能够完成所有的任务，要求每个机器人都要分配一项工作，怎么分？ABCcba电灯管道与覆盖集(Covering)问题电灯管道问题某座办公大楼平面图如下,每道走廊都装设了电灯,其开关可设于此走廊两端的转角口其中之一。要使安裝了开关的转角口越少越好,要怎么安裝?信息流传与广播问题(Broadcasting)信息流传问题班上有

4、一件事情要宣布，班长想打电話告訴全班。但若他一个个打似乎太慢了。假设一个班有五十人，打一通电话需要一分钟，那总共就需要四十九分钟。但若是他打了第一个电话后，便请第一个同学再打给別人；第二通电话打了之后，又再请第二个同学打给別人；依此类推，但问题是，也许某些同学沒有某些同学的电话，那么这时，怎样在最短时间內打完所有电话？5次6次计算机网络与连通度(Connectivity)问题计算机网络断线问题一公司内有多部计算机并连成网络,我们想知道其网络设计得好不好。考虑若有某线路毁损后,所有的机器是否仍可彼此互通?进一步,讨论该网络设计可保证在同时至多

5、有几条线路毁损后仍互通?7.2若干基本概念图定义7.2.1无向图G是一个二元组V:vertexset顶点集常写作V(G)，也称点(point)，结点(node)，接点(junction)非空有限集它的元素，习惯上用数字或小写英文字母a,b,c,u,v,w,x,y,z等(或加足标)表示E:edgeset边集合常写作E(G)，也称边(edge)，线(line)，枝(branch)V中元素无序偶的可重集它的元素，常用字母e(可加足标)表示边e＝(a,b)亦记为ab有的书上将无向图G定义成一个三元组，V是顶点集，E是边集，而

6、ψ则是E到V中元素的无序偶之集的一个映射图的图形表示G==<{a,b,c,d},{(a,b),(a,c),(b,d),(b,c),(d,c),(a,d),(b,b)}>结点偶对可以是有序的,也可以是无序的若边e所对应的偶对是有序的,则称e是有向边有向边简称弧,a叫弧e的始点,b叫弧e的终点若边e所对应的偶对(a,b)是无序的,则称e是无向边有向图无向图混合图例G'==<{a,b,c,d,e,f},{,,,,,}>简单图只讨论V是有限集的情况若#V(

7、G)＝p，#E(G)＝q，则称G是一个(p.q)图p称为图G的阶(1,0)图——孤立点或平凡图(p,0)图(p≥2)——空图或零图若E(G)是一个普通集合(即每个元素的重度为1)，且a∈V(G)，(a,a)E(G)，则称图G是一个简单图线(a,a)叫自环线表示重度为i(≥2)的i条线叫做互相平行的简单图——没有自环线和平行线的图。例abcdfeababcde(6,9)图(5,0)图abcd定义7.2.2设G是一个图，a,b∈V(G)。如果e＝(a,b)∈E(G)，则称a和b是彼此相邻接的，记作aAdjb，又称a(和b)是e的端点或e与a(

8、和b)相关联。而(a,b)E(G)被记作aNAdjb。若边e1和e2有公共端点，则称e1和e2是彼此相邻接的定义7.2.3与顶点u相关联(即以u为端点)的边的条数叫做u的度，用