图 论
哥尼斯堡七桥问题：图论发源于18世纪普鲁士的哥尼斯堡。普雷格河流经这个城市，河中有两个小岛，河上有七座桥，连接两岛及两岸。如图所示，当时城里居民热衷于讨论这样一个问题：一个人能否走过这七座桥，且每座桥只经过一次，最后仍回到出发点。
将上面问题中的两座小岛以及两岸用点表示，七座桥用线（称为边）表示，得到下图：
于是，上述问题也可叙述为：寻从图中的任意一个点出发，经过所有的边一次且仅一次并回到出发点的路线。
注意：在上面的图中，我们只关心点之间是否有边相连，而不关心点的具体位置，边的形状以及长度。
一、基本概念：
图：由若干个点和连接这些点中的某些“点对”的连线所组成的图形。
顶点：上图中的A ，Ｂ，Ｃ，D ．常用表示。
n 21 v , , v , v 边：两点间的连线。记为（Ａ，Ｂ），（Ｂ，Ｃ）．常用表示。
m 21e , , e , e
次：一个点所连的边数。定点ｖ的次记为d(v)．
图的常用记号：Ｇ＝（Ｖ，Ｅ），其中，}{v V i =，}{e E i =
子图：图Ｇ的部分点和部分边构成的图，成为其子图。
路：图Ｇ中的点边交错序列，若每条边都是其前后两点的关联边，则称该点边序列为图Ｇ的一条链。
圈（回路）：一条路中所含边点均不相同，且起点和终点是同一点，则称该路为圈（回路）。
有向图：，其中(,)G N A =12{,,,}k N n n n = 称为的顶点集合，A a 称为G 的弧集合。
G {(,)ij i j }n n ==若，则称为的前驱， 为n 的后继。
(,)ij i j a n n =i n j n j n i 赋权图（网络）：设是一个图，若对G 的每一条边（弧）都赋予一个实数，称为边的权，。记为。
G (,,)G N E W =
两个结论：１、图中所有顶点度数之和等于边数的二倍； ２、图中奇点个数必为偶数。
二、图的计算机存储：
天津港进口车1. 关联矩阵
简单图：，对应(,)G N E =N E ×阶矩阵()ik B b =
10ik i k b ⎧=⎨⎩
点与边关联
否则简单有向图：，对应(,)G N A =N A ×阶矩阵()ik B b =
110ik ik ik a i b a i ⎧⎪
=−⎨
⎪⎩
弧以点为尾
弧以点为头否则
2. 邻接矩阵
简单图：，对应(,)G N E =N N ×阶矩阵()ij A a =
10
ij i j a ⎧=⎨
途乐怎么样⎩点与点邻接
否则简单有向图：，对应(,)G N A =N N ×阶矩阵()ij A a =
10ij i j
a ⎧=⎨
⎩有弧从连向否则
5
v 34
v
010101101001010111101010001101111010
654321666
54321⎥⎥
⎥
⎥⎥
⎥
⎥⎥
⎦
⎤
⎢⎢⎢⎢⎢
北京别克4s店⎢⎢⎢⎣⎡=×v v v v v v A v v v v v v
3. 权矩阵：
简单图：，对应(,)G N E =N N ×阶矩阵()ij A a =
ij ij i j a ω⎧
=⎨
∞
⎩
点与点
邻接
否则
1234567812345678
02130654.5061002907250473080 v v v v v v v v v v v v v v v v 48∞∞∞∞⎡⎤
⎢⎥∞∞∞∞∞⎢⎥
⎢⎥∞∞∞∞∞⎢⎥∞∞∞∞∞⎢⎥⎢⎥∞∞∞∞⎢⎥∞∞∞∞⎢⎥⎢⎥∞∞∞∞⎢⎥∞∞∞∞∞∞⎢⎥⎣⎦
三、图的应用：
例：如图，用点代表7个村庄，边上的权代表村庄之间的路长，现在要在这7个村庄
中布电话线，如何布线，使材料最省？
分析：需要将图中的边进行删减，使得最终留下的图仍然连通，并且使总的权值最小。
1. 最小树问题：
树：一个无圈的连通图称为一棵树，记为Ｔ．
双龙柯兰多怎么样
树的特征：１、无圈且连通；
２、任意两点间有且只有一条路；
３、若一棵树的顶点个数为Ｐ，则其边数为Ｐ－１．
部分树：若图Ｇ的部分图是一棵树，则称该部分图为Ｇ的部分树。最小树：总的权值最小的部分树。
求最小树的算法：
破圈法：任取一圈，去掉圈中最长边，直到无圈。
例：求下图的最小树
（1）圈1341：删
（2）圈1241：删
13
福特猛禽f350a
12
a
（3）圈34653：删（4）圈3563：删
34
a
35
a
（5）圈4654：删
46
a
三菱跑车伊柯丽斯
避圈法: 去掉G 中所有边，得到n 个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。
2. 最短路问题：
例 ｖ１，ｖ２，ｖ３，ｖ４，ｖ５，ｖ６，ｖ７，ｖ８，ｖ９九个城市间的公路网如图所示，假定有一批货物需要用卡车由ｖ１分别运到ｖ８，ｖ９，问各走哪条路最短？
分析：在有向赋权图上给定一个起点，一个终点，要求一条起点到终点的通路，使其总权数最小。
最短路算法：
（1）Dijkstra 标号算法（两个指定顶点之间的最短路径）
基本思路：若序列{ v s ,v 1…..v n-1,v n }是从v s 到v n 间的最短路，则序列{ v s ,v 1…..v n-1} 必为从v s 到v n-1的最短路。
发布评论