文档介绍：图论算法与模型构建
总览
图的基本概念与存储结构
图的遍历和染色性
图的连通性问题
路径问题
拓扑排序
流量问题
匹配问题
图论中的“图”并不是通常意义下的几何图形或物体的形状图, 而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.
定义1 一个有序二元组(V, E ) 称为一个图, 记为G = (V, E ), 其中
① V称为G的顶点集, V≠, 其元素称为顶点或结点, 简称点;
② E称为G的边集, 其元素称为边, 它联结V 中的两个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边.
如果V = {v1, v2, …, vn}是有限非空点集, 则称G为有限图或n阶图.
图的基本概念与存储结构
如果E的每一条边都是无向边, 则称G为无向图(如图1); 如果E的每一条边都是有向边, 则称G为有向图(如图2); 否则, 称G为混合图.
图
1
图
2
并且常记
V = {v1, v2, …, vn}, |V | = n ;
E = {e1, e2, …, em}(ek=vivj ) , |E | = m.
称点vi , vj为边vivj的端点. 在有向图中, 称点vi , vj分别为边vivj的始点和终点.
有边联结的两个点称为相邻的点, 有一个公共端点的边称为相邻边. 边和它的端点称为互相关联. 常用d(v)表示图G中与顶点v关联的边的数目, d(v)称为顶点v的度数. 用N(v)表示图G中所有与顶点v相邻的顶点的集合.
d(v1)= d(v3)= d(v4)=4,
d(v2)=2.
我们今后只讨论有限简单图:
(1) 顶点个数是有限的;
(2) 任意一条边有且只有两个不同的点与它相互关联;
(3) 若是无向图, 则任意两个顶点最多只有一条边与之相联结;
(4) 若是有向图, 则任意两个顶点最多只有两条边与之相联结. 当两个顶点有两条边与之相联结时,这两条边的方向相反.
如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.
定义2 若将图G的每一条边e都对应一个实数F (e), 则称F (e)为该边的权, 并称图G为赋权图(网络), 记为G = (V, E , F ).
定义3 设G = (V, E)是一个图, v0, v1, …, vk∈V, 且1≤i≤k, vi-1vi∈E, 则称v0 v1 … vk是G的一条通路. 如果通路中没有相同的边, 则称此通路为道路. 始点和终点相同的道路称为圈或回路. 如果通路中既没有相同的边, 又没有相同的顶点, 则称此通路为路径, 简称路.
定义4 任意两点均有通路的图称为连通图.
定义5 连通而无圈的图称为树, 常用T表示树.
图的储存结构
矩阵
邻接表
邻接多重表
十字链表
无向图邻接表
1
5
2
4
3
1
2
3
4
5
1 |
5 |
4 |
3 | /
2 |
2 |
2 |
3 |
1 |
2 |
4 | /
5 | /
4 | /
5 | /
邻接链表
每一个顶点
有一个所有与之相邻的链表
每一条边
2 个(对无向图)
要在两个顶点的链表中都加入
空间复杂度O(|E|)
对稀疏图这种方式比较好
邻接表