图论算法总结及图论建模.ppt

图论算法总结
图的基本概念
图的基本概念
二元组 G(V,E) 称为图(graph)。 V为结点(node)或顶点(vertex)集。 E为图中结点之间的边的集合。
点,用数字0…n-1表示
点对(u,v) 称为边(edge)或称弧(arc)
对于边(u,v)∈E
-u和v邻接(adjacent)
-e和u、v关联(incident)
子图(subgraph): 边的子集和相关联的点集
图的基本概念
有向图:边都是单向(unidirectional)的, 因此边(u,v)是有序数对. 有时用弧(arc)专指有向边
带权图:可以给边加权(weight), 成为带权图, 或加权图(weighted graph). 权通常代表费用、距离等, 可以是正数, 也可以是负数
稠密性:边和V(V-1)/2相比非常少的称为稀疏图(sparse graph), 它的补图为稠密图(dense graph)
路径和圈
一条路径(path)是一个结点序列, 路上的相邻结点在图上是邻接的
如果结点和边都不重复出现, 则称为简单路径(simple path). 如果除了起点和终点相同外没有重复顶点和边, 称为圈(cycle).
不相交路(disjoint path)表示没有除了起点和终点没有公共点的路. 更严格地
-任意点都不相同的叫严格不相交路(vertex-disjoint path)
-同理定义边不相交(edge-disjoint path)路
注意: 汉语中圈和环经常混用(包括一些固定术语). 由于一般不讨论自环(self-loop), 所以以后假设二者等价而不会引起混淆
连通性
如果任意两点都有路径, 则称图是连通(connected)的, 否则称图是非连通的.
非连通图有多个连通分量(ponent, cc), 每个连通分量是一个极大连通子图(maximal connected subgraph)
完全图和补图
完全图:N个顶点的图,有N(N-1)/2个节点
对于(u,v), 若邻接则改为非邻接, 若非邻接则改为邻接, 得到的图为原图的补图
完全图=原图∪补图
团:完全子图
生成树
树:N个点,N-1条边的连通图(无环连通图)
生成树: 包含某图G所有点的树
一个图G是树当且仅当以下任意一个条件成立
G有V-1条边, 无圈
G有V-1条边, 连通
任意两点只有唯一的简单路径
G连通, 但任意删除一条边后不连通
图例
图的表示方法
介绍两种图的表示方法:邻接矩阵与邻接表
V*V的二维数组A,A[i][j]=0,若(i,j)不相连,A[i][j]=1,若(i,j)相连
图1
图1的邻接矩阵表示