图的由来——对现实世界的抽象

哥尼斯堡七桥问题

化学研究中的分子结构表示

如，丁烷（C4H10）的两种同分异构结构用图可以表示为：

高铁线路图

期末考试时间的排布

一个学校要对期末考试进行排布，如何避免时间上的冲突？

抽象为图的模型来解决，则顶点代表待排布的课程，连接两个顶点边表示有学生同时选择了这两门课程。

问题转化为用不同的颜色去给顶点上色（顶点着色问；四色问题），要求不同时间段的考试（顶点）用不同的颜色

，相同时间段的考试（顶点）用相同的颜色。

图的构成

什么构成了图：——顶点和边构成的网络结构

我们关心什么？
- 图中有多少个点
- 哪些点之间有线（边）连接
我们不关心什么？
- 边的长度
- 边是否弯曲
- 点的绝对位置

定义

文字定义：

一个图是一个序偶<V, E>，符号表示为： G = <V, E>
V = {v1, v2, …, vn}为有限非空集合，Vi称为顶点，或简称点，V称为顶点集，用**|V|表示顶点数**
E是有限集合，为一个图的所有边的集合，称为边集，且E中的每个元素都有V中的结点对与之对应，用|E|表示边数

常见名词解释

有限图：顶点数和边数都有限的图
空图：边集为空（无边）的图
平凡图：只有一个顶点的图
n 阶图：顶点数为n的图
(n, m) 图：顶点数为n，边数为m的图
环：端点重合为一点的边
重边：连接两个相同顶点的多条边（大于1条），边的条数称作边的重数
简单图：图中没有环且没有重边
复合图：图中有环或者有重边或者二者均有

图的表示

集合表示

对于一个图，将其记为G=<V,E>，并写出V和E的集合表示。

优点：可以精确描述图的组成信息
缺点：较为抽象，不易于直观理解

图形表示

（1）用小圆圈表示V中的结点

（2）有序的结点对<u, v>表示由结点u指向结点v的有向边e

（3）此时u称为e的始点，v称为e的终点，统称为e的端点

（4）无序的节点对(u, v)（或(v, u)）表示结点u和结点v之间的无向边

（5）此时仅称u，v为边e的两个端点

优点：可以直观形象地表示图，易于理解
缺点：当图中结点以及边的数量比较大时，很难全部绘制出来

矩阵表示——邻接矩阵

我们经常需要计算机帮助我们去处理图的数据，然而对于计算机而言，集合的形式或者图形的形式都不太适合，而矩阵却是非常适合计算机计算的形式。

矩阵表示（邻接矩阵）需要准备什么？
- 矩阵的行与列有固定的次序，行列的位置不同，代表不同的矩阵
- 需将图中的结点按某种既定顺序排列
- 若并未给出具体排序，则顺序默认为书写结点集V时的结点顺序
邻接矩阵

设图G = <V, E>，其中V = {v1, v2, …, vn}，并已确定了各结点的排列次序，则将n阶方阵AG = (aij)nxn称为G的邻接矩阵，其中：

图的邻接矩阵是唯一的吗？

一般而言，同一个图按照不同的顶点排列次序，写出的邻接矩阵形式上是不同的，但是相互之间可以通过调换某些行或列的位置而得到。
对邻接矩阵的行或列进行交换，对应的实际上是在对顶点的排序中调换顶点的位置
若不考虑顶点排序的不同产生的邻接矩阵的不同，则图与邻接矩阵之间是一一对应的
实际操作上，往往略去顶点排序不同导致的邻接矩阵的多样性，选择任意一种顶点次序得出的邻接矩阵作为该图的邻接矩阵

图的种类

按边有无方向

有向图
无向图
混合图

按有无平行边（重边）

多重图：有平行边的图
线图：无平行边的图
简单图：无环的线图

按边或顶点是否赋予权重

无权图
赋权图： G是一个三重组<V, E, g>或四重组<V, E, f, g>，其中V是结点集合，E是边的集合，f是从V到非负实数集合的函数，g是从E到非负实数集合的函数。

最短路径——Dijkstra算法

给出一个赋权图，若顶点代表了不同的城市，权重代表了不同城市间的距离，给定起点，如何求出其到任意一点的最短路径？

思路：

把顶点集合V分成两组
- S：已解决的顶点的集合（初始时只含有源点V0）
- U：尚未确定的顶点集合
将U中顶点按递增的次序加入到S中，保证：
- 从源点V0到S中其他各顶点的长度都不大于从V0到U中任何顶点的最短路径长度
- 每个顶点对应一个距离值
S中顶点：从V0到此顶点的长度
U中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

Tips：不适用权重为负的情况

树

定义

不含圈的连通图

生成树

性质
- 包含连通图中所有的顶点的树
- 任意两个连通的顶点之间有且仅有一条边
- 顶点数-边数=1

最小生成树

性质
- 仅针对赋权图而言
- “最小”指的是树中所有边的权重之和最小
- 为“最小权重生成树”的简称
应用
- 不同城市间怎样修路使得各个城市都能连接上又令总里程最短
- 通信线路的铺设
Kruskal算法：
1. 构造一个只含原图G中所有顶点，而不包含任何边的子图T
2. 将图中的边按照权重大小进行从小到大的排序，形成集合E
3. 从E中选取当前权值最小的边
4. 若该边的两个顶点分属不同的树，则将其加入子图T
5. 将该边从E中移除
6. 重复步骤3~5，直至子图T为原图G的一个生成树
Prim算法