图 2008赛前知识点梳理三.

Presentation on theme: "图 2008赛前知识点梳理三."— Presentation transcript:

1 图 2008赛前知识点梳理三

2 图的定义(Graph ) 比较： 线性表：数据间关系是线性的，每个元素只有一个前趋，一个后续
树：有着明显的层次关系，每个元素只有一个前趋，但有多个后续 图：数据之间的关系是任意，每个元素的前趋和后续个数是不定，图是一种较为复杂的非线性数据结构

3 引入：柯尼斯堡七桥问题，能否从A地发出，各座桥恰好通过一次，最后回到出发地A？
结论：1736年，数学家欧拉首先解决了这个问题，由此开创了图论研究。这事实上是欧拉图的“一笔画问题”。 答案是否定的，因为，对于每一个顶点，不论如何经过，必须有一条进路和一条出路，与每一个顶点相邻的线（关联边）必须是偶数条（除起点和终点外），而此图中所有点都只有奇数条关联边。

4 定义：简单讲，一个图是由一些点和这些点之间的连线组成的。
严格意义讲，图是一种数据结构，定义为：graph=（V，E）。V是一个非空有限集合，代表顶点（结点），E代表边的集合，一般用（Vx，Vy）表示，其中，Vx，Vy属于V。 　　分类：如果边是没有方向的，称为“无向图”。表示时用一队圆括号表示，如：（Vx，Vy），（Vy，Vx），当然这两者是等价的。并且说边（Vx，Vy）依附于（相关联）顶点Vx和Vy。 如果边是带箭头的，则称为“有向图”，表示时用一队尖括号表示，此时<Vx，Vy>与<VY，VX>是不同的，如<VX，VY>的起点为VX，终点为VY。 有向图中的边又称为弧。起点称为弧头、终点称为弧尾。< P><Vy，Vx>是不同的，如<Vx，Vy>的起点为Vx，终点为Vy。

5 相邻：若两个结点U、V之间有一条边连接，则称这两个结点U、V是关联的。
　　 带权图：两点间不仅有连接关系，还标明了数量关系（距离、费用、时间等）。 　　 图的阶：图中结点的个数。 结点的度：图中与结点A关联的边的数目，称为结点A的度。 　　　入度：在有向图中，把以结点V为终点的边的数目称为V的入度； 　　　出度：在有向图中，把以结点U为起点的边的数目称为U的出度； 　　　奇点：度数为奇数的结点； 　　　偶点：度数为偶数的结点； 　　　终端结点：在有向图中，出度为0的结点； 　　　　定理1：图中所有结点的度数之和等于边数的2倍； 　　　　定理2：任意一个图一定有偶数个奇点；

6 图 ⑴、 ⑵图的各顶点的度见下表： 入度（ indegree）：有向图中把以顶点 v为终点的边的条数称为是顶点 v的入度。 出度（ outdegree）：有向图中把以顶点 v为起点的边的条数称为是顶点 v的出度。⑵图各顶点的入度和出度见下表 (各顶点的入度与出度之和为该顶点的度 )

7 连通：如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V是连通的。
　　路（径）：从一个结点出发，沿着某些边连续地移动而到达另一个指定的结点，这种依次由结点和边组成的序列，叫“路”或者“路径”。 　　　路径长度：路径上边的数目。 　　　简单路径：在一个路径上，各个结点都不相同，则称为简单路径。 　　回路：起点和终点相同的路径，称为回路，或“环”。 　　连通图：对于图G中的任一对不同顶点U、V，都有一条（U，V）通路，则称图G是连通的。 　　强连通图：在有向图G中，每一对结点之间都有路径的图。 　　网络：带权的连通图。

8 表示方法 1. 邻接矩阵存储 ⑴ 邻接矩阵 无向图：A[I，J] = 1 当I与J两个结点相邻时 = 0 当I与J两个结点不相邻时，或I=J
1. 　邻接矩阵存储 ⑴ 邻接矩阵 无向图：A[I，J] = 1 当I与J两个结点相邻时 　　　　　　= 0 当I与J两个结点不相邻时，或I=J 　　　　　　　　（1=<I，J<=图中结点数） 　　且有：A[I，J]=A[J，I]，即邻接矩阵是对称的。 表示方法

9 带权图的邻接矩阵可以定义为： 2邻接矩阵表示为

10 图的邻接表表示法 　

11 图的遍历 1、概念：从图中某一结点出发系统地访问图中所有结点，使每个结点恰好被访问一次，这种运算 称图的遍历。为了避免重复访问某个结点，可以设一个标志数组visited[I]，未访问时值为FALSE，访问一次后就改为TRUE。 2、分类：深度优先遍历和广度优先遍历。

12 深度优先遍历：类似于树的先序遍历，从图中某个结点V0出发，访问此结点，然后依次访问从V0的未被访问的邻接点出发进行深度优先遍历，直到图中所有和V0有路径相通的结点均被访问到。若此时图中尚有结点未被访问，则另选图中一个未被访问的结点V1作为起点，重复上述过程，直至图中所有结点都被访问到为止。 如下面两个图的深度优先遍历结果分别为： 　　a，b，c，d，e，g，f 　　V1，V2，V4，V8，V5，V3，V6，V7

13 广度优先遍历：从图中某个结点V0出发，访问此结点，然后依次访问与V0邻接的、未被访问过的所有结点，然后再分别从这些结点出发进行广度优先遍历，直到图中所有被访问过的结点的相邻结点都被访问到。若此时图中还有结点尚未被访问，则另选图中一个未被访问过的结点作为起点，重复上述过程，直到图中所有结点都被访问到为止。如上面两个图的广度优先遍历结果分别为： 　　　a，b，d，e，f，c，g 　　　V1，V2，V3，V4，V5，V6，V7，V8

14 最小生成树问题 　如果图G=（V，E）是一个连通的无向图，则从G的任一个顶点出发进行一次深度优先遍历或广度优先遍历便可遍历全部图。 　　设遍历过程中走过的边的集合为TE（G），显然T=（V，TE）是G的一个连通子图，且T本身也是一棵树（无根树），则称T是G的生成树。 上图（B）和（C）是对（A）分别进行深度和广度优先遍历得到的一种生成树。注意，图的生成树是不唯一的。对于一棵带权树，生成树中各边的权值之和称为这棵生成树的代价，代价最小的生成树称为“最小代价生成树”。

15 如何求最小代价生成树呢 R.C.Prim提出的求最小代价生成算法是常用的一种，设图的顶点集合V共有n个顶点，则算法如下： 1、设置一个顶点的集合S1和一个边的集合TE，S1和TE的初始状态均为空集； 2、选定图中的一个顶点K，从K开始生成最小代价生成树，将K加入到集合S1； 3、重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中X∈S1，not(Y∈S1)。将顶点Y加入集合 S1，边（X，Y）加入集合TE。 图给出了上图（A）的最小代价生成树的生成过程：

16 一笔画问题 由数学知识可知：当一个图的顶点全是偶点或仅有两个奇点时才能一笔画出，而且此图必须是连通图。 给出几个数学概念：
　　给出几个数学概念： 　　　1． 欧拉路：在无孤立结点的图G中，若存在一条路，经过图中每条边一次且仅一次，则称此路为欧拉路。如下图（左）可以构成一个欧拉路 　　　2． 欧拉回路：若存在一条路，经过图中每条边一次且仅一次，且回到原来位置，则称此路为欧拉回路。因此，七桥问题转换成了欧拉回路问题。如下图（右）可以构成一个欧拉路 　　　3． 欧拉图：存在欧拉回路的图，称为欧拉图。 　　　4． 定理1：存在欧拉路的条件：图是连通的，且存在0个或2个奇点。 　　　5． 定理2：存在欧拉回路的条件：图是连通的，且存在0个奇点。 　　　6． 哈密尔顿图：无孤立结点的连通图，若存在一条路，经过图中每一个结点一次且仅一次，则称为哈密尔顿图。 　　　7． 哈密尔顿环：是一条沿着图的n边环行的路径，它访问每一个结点一次且仅一次，并且返回到它的开始位置。

17 求关键路径（2001年初赛） 　[问题描述] 设有一个工程网络如下图表示（无环路的有向图）：其中，顶点表示活动，①表示工程开始，⑤表示工程结束（可变，用N表示），边上的数字表示活动延续的时间。编程求关键路径。

18 2001年初赛 　[问题描述]设在A、B两个城市之间有N个路站（如下图中的S1，且N<100），城市与路站之间，路站与路站之间各有若干条路（各路段数<=20），且每条路段上的距离均为整数。A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段到达S2，……最后到达B，通路上路段之和称为通路距离（<=1000）。 　[任务]当所有的路段距离给出后，求出所有不同距离的通路个数。 如下图是N=1的一种情况：从A到B的通路条数为6，但因其中通路5+5=4+6，所以答案应为5。