哥尼斯堡七桥问题

一笔画问题。
将实际问题抽象成数学问题。

图是一种网状数据结构， 是由一个顶点的有穷非空集V(G)和一个弧或边的集合E(G)构成。

通常记作二元组 G = (V， E)。

其中G表示一个图， V是图G中顶点的集合， E是图G中弧的集合。

线性表可以无元素，树中可以无结点，图中不能没有结点。在定义中强调了顶点集：有穷非空集。

图的分类

权值和网

1.这样的边或弧称之为加权边或加权弧。
2.在一个反映城市交通线路的图中，边或弧上的权值可以表示该条线路的长度或者等级;
3.对于一个电子线路图，边或弧上的权值可以表示两个端点之间的电阻、电流或电压值;
4.反映工程进度的图，边或弧上的权值可以表示从前一个工程到后一个工程所需要的时间等。
5.这种带权的图称为网或网络(network)。

图的基本术语

➊顶点的度(degree)是指依附于某顶点v的边数， 通常记为TD(v)。
➊在有向图中，要区别顶点的入度与出度的概念。
➊顶点v的入度是指以顶点为终点的弧的数目，记为ID(v);
➊顶点v的出度是指以顶点v为始点的弧的数目，记为OD(v)。
TD(v) = ID(v) + OD(v)

简单路径

简单回路

子图

无向图的连通性

无向图的连通分量

注意：无向图的连通分量也称为无向图的极大连通子图。

在有向图中，只要任意两个顶点之间都有路径，那么该图可以称为强连通图。

图 - 生成树和生成树林

一个连通图的生成树是一个极小的连通子图，它包含图中全部的顶点n, 但只有足以让n个顶点连通的n-1条边，就是让n个顶点连通无回路。
此时去回路即可。

图的基本操作

1.在图中任何一个顶点都可以被看成是第一-个顶点;
2.任意-一个顶点的邻接点之间也不存在次序关系，所以无法将图中的顶点排列成一个唯一的线性序列。
3.为了操作方便，需要将图中顶点按任意的顺序排列起来(这个序列是人为规定的)。
所以需明确一个“顶点在图中位置”的概念。

计算

最多 n * （n - 1） / 2条边 构成一个无向完全图，最少n-1条边。

只有连通无向图存在生成树。

图的存储结构

邻接矩阵

用一维数组来存储顶点信息;
顶点与顶点之间的关系用二维数组存储–邻接矩阵。

无向图的邻接矩阵是对称的。

邻接表

邻接矩阵是一种静态存储方法。

存储无向图的邻接矩阵是对称的,因此只要存储邻接矩阵的上三角(或下三角)部分就可以了。
邻接矩阵适用于有向图和无向图的存储，能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。(邻接矩阵的元素可以存储权值)