图论初步.ppt

图 论,基本内容,一、 图论简介二、 图基础概念三 、图的最短路问题简述,,一、图 论 简 介,图论的起源： 图论是组合数学的一个分支,它起源于1736年欧拉的第一篇关于图论的论文，这篇论文解决了著名的 “哥尼斯堡七桥问题” ，从而使欧拉成为图论的创始人图论简介,图论是以图作为研究对象的一个数学分支，有一套完整的体系和广泛的内容它的起源可以追溯到1736年欧拉关于哥尼斯堡桥问题的研究在19世纪和20世纪的前半期，图论中主要研究 一些游戏问题，诸如迷宫问题、博弈问题和棋盘上马的行走路线等欧拉、克希荷夫、凯莱、哈密尔顿,1847年，克希荷夫应用图论的方法来分析电网络，奠定了现代网络理论的基础，第一次将图论应用于工程技术1857年，凯莱在试算饱和碳化氢的同分异性体时，提出了“树”的概念在这段时间，对图论的发展另有两个里程碑一个是莫别斯约于1840年提出的“四色猜想”另一个是威廉哈密尔顿于1859年提出的周游世界问题此后约半个世纪研究图论的人并不多，直到1936年哥尼格发表了第一本图论专著，从些图论才成为一门独立的学科本世纪30年代后，由于科学技术发展对离散数学模型提出了迫切的要求，图论才成长为一门独立的学科。

现在它已广泛地应用于物理、化学、电子学、通讯科学、计算机科学、经济学、语言学和心理学等各个领域，并与群论、拓扑学、运筹学、七概率论等其它一些数学分支相互渗透近年来，图论这门学科发展迅速，并陆续出现了拓扑图论、代数图论、极图理论、随机图论等新的研究方向列昂哈德欧拉（Leonhard Euler 公元1707-1783年） 1707年出生在瑞士的巴塞尔（Basel）城，13岁就进巴塞尔大学读书，得到当时最有名的数学家约翰·伯努利（Johann Bernoulli，1667-1748年）的精心指导1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授欧拉渊博的知识，无穷无尽的创作精力和空前丰富的著作，都是令人惊叹不已的！,他从19岁开始发表论文，直到76岁，半个多世纪写下了浩如烟海的书籍和论文到今几乎每一个数学领域都可以看到欧拉的名字，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%，彼得堡科学院为了整理他的著作，足足忙碌了四十七年欧拉还创设了许多数学符号,例如 π(1736年)，i(1777年)，e(1748年)，sin和cos(1748年)，tg(1753年)，△x(1755年)，Σ(1755年)，f(x)(1734年)等。

1736年发表了图论的首篇论文，解决了哥尼斯堡七桥问题，奠定了图论的基础，目前一般公认欧拉为图论之父1 哥尼斯堡七桥问题,哥尼斯堡位于前苏联的加里宁格勒，历史上曾经是德国东普鲁士省的省会，普雷格尔河横穿城堡，河中有两个小岛，共有七座桥连接两岸和小岛1. 哥尼斯堡“七桥”问题：,格尼斯堡人在寻找一条路线,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,当时哥尼斯堡的居民中流传着这样一道难题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题问题一: 一个居民从家中出来散步, 经过每座小桥一次且仅一次, 然后回到家中.问题二: 一个居民从家中出来散步, 经过每座小桥一次且仅一次即可.,Euler研究了这一游戏问题, 他将四块陆地视为四个结点, 七座小桥成为连接四个结点的连线. 形成了最早研究的一类图论问题——Euler图问题.,欧拉将其概括为数学模型,“七桥”问题变为“一笔画”问题,,,,,,,,,,,C,D,B,,A,欧 拉 图,定义 一个图,如果能够从一点出发,经过每条边一次且仅一次再回到起点,则称为欧拉图欧拉在论文中给出并证明了判断欧拉图的充分必要条件定理,并证明了七桥图不是欧拉图。

从这个问题可以看出：,图：图用点代表各个事物,用边代表各个事物间的二元关系所以，图是研究集合上的二元关系的工具，是建立数学模型的一个重要手段2、一百多年以后,“七桥”问题以后，图论的研究停滞了一百多年，直到1847年，在这一时期流行着两个著名的图论问题：哈密尔顿回路问题和 “四色猜想” 问题3、哈密尔顿回路问题,1856年,英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正十二面体的二十个顶点上标上二十个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市一次且仅一次，然后回到出发点哈密尔顿回路图：,示意图：此路线称为：哈密尔顿回路，而此图称为：哈密尔顿图示意图：此路线称为：哈密尔顿回路，而此图称为：哈密尔顿图此路线称为：哈密尔顿回路，而此图称为：哈密尔顿图4、“四 色 猜 想” 问 题,人们在长期为地图(平面图)上色时发现，最少只要四种颜色，就能使得有相邻国界的国家涂上不同的颜色四色猜想的证明一直没有解决，直到一百多年后，在计算机出现以后，于1976年用计算机算了1200多小时，才证明了四色猜想问题二、图的基本概念：,1 图的定义； 2 结点的“度” (次数)； 3图的分类； 4子图；,1 图的定义,定义：图 G 是由非空的结点集合V={v1,v2,…,vn}与边集合E={l1,l2,…,lm}组成,其中每条边用一对结点表示： li=(vi1, vi2)( i=1,2,…,m ),这样的一个图 G 可记为 G =〈 V，E 〉。

注意：① V≠Φ，但可以：E＝Φ；② 结点也叫顶点,说明：图是一个三元有序组G=(G(V), G(E), G). 其中G(V)是一个非空的顶点集合, 简称为点集, 简记为V. G(E)是一个与V不交的边集合, 简称为边集, 简记为E. G称为关联函数, G : E  VV. 一个图简记为G=(V, E),VV是一种集合运算, 称为笛卡儿乘积, 当VV中的元素为有序时, 图G称为有向图, 否则称G为无向图. 若eE, u, vV, 当G(e)=uv时, 称边e与顶点u, v相关联, 即边e连接顶点u, v. 也称u, v为e的端点.,图论中的图与几何中的图形的概念毫不相干. 之所以称为图, 是因为图可以用一种图形作图示. 图论中的图示不唯一, 因人而异.,一条边与其端点称为相关联的;,与同一条边相关联两个顶点称为相邻的; 相关联与同一个顶点的两条边称为相邻的. 两个顶点重合为一点的边称为环;,以相同两顶点为端点的边(有向边的方向相同)称为重边.在大多数情况下, 图论研究无环无重边的有限简单图.,例 题：,四个城市：v1、v2、v3、v4, 其中v1与v2间，v1与v4间，v2与v3间有直达高速公路相连，写出其集合并画出此图。

解：G =〈V，E〉，V = (v1，v2，v3，v4) ，E = (l1，l2，l3)，其中：,例 题：,l1= (v1, v2) v1 v2 l2= (v1, v4) l3 = (v2, v3) v3 v4 注意：图与 v1 v2 几何形状无关 v4 v3,,,,,,,,,,,,,,,,2 结点的“度”(次数),与一个结点 v 相关联的边的条数称为这个结点的度，记为: d(v)例如：哥尼斯堡七桥图：d(A)=3 d(B)=3d(C)=5d(D)=3,AC DB,,,,,,,,,,,,3 图的分类:a 按边的方向分类,有向图与无向图:边有方向的图,叫有向图, 边无方向的图叫无向图 起点与终点: 有向边 l =(vi,vj)中vi 称为起点, vj 称为终点 例：有向图 无向图A B 起点 终点 （无向图可以化为有向图）,,,,,,,,,,b.按边的种类分类：,简单图与多重图:不含环与多重边的图叫简单图；含多重边的图叫多重图 有权图与无权图: 有时在一个图中边的旁边可以附加数字以刻划此边的某些数量特征，叫做边的权，此边叫做有权边，具有有权边的图叫有权图或带权图，无有权边的图叫无权图。

4 子 图,子图：设 G =〈 V, E 〉和 H =〈V1, E1〉是两个图，如果 V 包含 V1，E 包含 E1，则称 H 是 G 的子图，记为G H 例如：图G v1 v2 图H v1 v2 v3 v4 v3 v4,,,,,,,,,,,,,,,,生成子图: 如果 H 是 G 的子图，并且V = V1,则称 H 是G 的生成子图例如： 图G v1 v2 图H v1 v2 v3 v4 v3 v4,,,,,,,,,,,,,,,,三、图的最短路问题:,通路：设图 G =〈V, E〉, 考虑 G中边序列 (vi1, vi2), (vi2, vi3), · · ·( vi(k-1), vik ), 该序列由vi1开始至vik止,其中每边的终点都是下一边的起点,这种边的序列叫点vi1到vik的通路，简记为(vi1, vi2, …, vik),例 如：,v1到v2的通路1: (v1, v2, v3, v4, v2)v1 v2v3 v4 v1到v2的通路2: (v1, v3, v4, v2)v1 v2v3 v4,,,,,,,,,,,,,,,,,,,,,有权图的最短路：,通路的长度：有权图(还可以叫赋权图)的通路中各边长度之和就是该通路的长度(一般用d表示)。

最短路：在图中的两点间存在的各个通路中，长度最短的通路叫做这两点间的最短(通)路短程线),求最短路的Dijkstra (迪克斯特拉)算法,1959年,Dijkstra算法能求一个顶点到另一顶点最短路径它是由Dijkstra于1959年提出的实际它能求出始点到其它所有顶点的最短路径Dijkstra算法步骤如下：,0,2,8,1,∞,∞,∞,∞,∞,∞,∞,0,2,8,∞,∞,10,∞,∞,∞,∞,1,0,8,3,∞,10,∞,∞,∞,∞,1,2,0,8,6,10,12,5,∞,∞,1,2,3,0,8,6,10,12,14,∞,1,2,3,5,0,7,10,12,14,∞,1,2,3,5,6,0,9,12,14,∞,1,2,3,5,6,7,0,12,14,10,1,2,3,5,6,7,9,0,11,14,1,2,3,5,6,7,9,10,0,13,1,2,3,5,6,7,9,10,11,0,1,2,3,5,6,7,9,10,11,13,。