1.定义
G=(V, E)，顶点集V，边集E
图的顶点集V一定非空，但边集E可以为空
2.概念
2.1 无向图（无向边/边）
- (v, w)
2.2 有向图（有向边/弧）
- <v, w>称为从 顶点v到顶点w的弧
- v称为弧尾，w称为弧头
2.2 简单图
- 不存在重复的边
- 不存在顶点到自身的边
2.3 多重图
- 某两个结点之间的边数多于一条，又允许顶点通过一条边和自己关联
2.4 顶点的度
2.4.1 无向图
- 依附于该顶点的边的条数，TD(v)
2.4.2 有向图
- 入度 + 出度
- 出度：以顶点V为终点的有向边的数目，ID(V)
- 入度：以顶点v为起点的有向边的数目，OD(v)
2.5 边的权
- 每条边标上具有某种含义的数值
2.6 带权图
- 每条边标上具有某种含义的数值
2.7 带权路径长度
- 一条路径上所有边的权值之和
3.点到点的关系
3.1 路径
- 顶点Vp到顶点Vq之间的一条路径是指顶点序列
3.2 回路
- 第一个顶点和最后一个顶点相同的路径称为回路或环
3.3 简单路径
- 在路径序列中，顶点不重复出现的路径称为简单路径
3.4 简单回路
- 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
3.5 路径长度
- 路径上边的数目
3.6 最短路径
3.6.1 最短路径存在
- 此路径的长度称为u到v的距离
3.6.2 路径不存在
- 记该距离为无穷（∞）
3.7 无向图顶点的连通性、连通图
- 连通：从顶点v到顶点w有路径存在
- 连通图：任意两个顶点都是连通的
- n个顶点的无向图，若是连通图，则最少有 n-1 条边；若是非连通图，则最多可能有 条边
3.8 有向图顶点的强连通性、强连通图
- 强连通：从顶点v到顶点w和顶点w到顶点v之间都有路径
- 强连通图：图中任意一对顶点都是强连通的
- n个顶点的有向图，若是强连通图，则最少有n条边（形成回路）
4.图的局部
4.1 子图
4.2 连通分量
4.3 强连通分量
4.4 连通无向图的生成树
- 包含全部顶点的极小连通子图
- 图中顶点数为n，则它的生成数含 n-1 条边
- 砍去一条边，则变成非连通图
- 增加一条边，则形成回路
4.5 非连通无向图的生成森林
- 各连通分量的生成树
5.几种特殊形态的图
5.1 完全图
5.1.1 无向完全图
- 无向图中任意两个顶点之间都存在边
- 若定点数|V| = n，则|E|∈[0, n(n-1)/2]
5.1.2 有向完全图
- 有向图中任意两个顶点之间都存在方向相反的两条弧
- 若定点数|V| = n，则|E|∈[0, n(n-1)]
5.2 稠密图、稀疏图
5.3 树
- 不存在回路，且连通图的无向图
- n个顶点的树，必有 n-1 条边
- n个顶点的图，若|E|>n-1，则一定有回路
5.4 森林
5.5 有向树
- 一个顶点的入度为0，其余顶点的入度为1的有向图
6.常见性质
6.1 n个顶点无向图
- 所有顶点的度之和 = 2|E|
- 若G是连通图，则最少有 n-1 条边；若|E|>n-1，则一定有回路
- 若G是非连通图，则最多可能有(n-1)(n-2)/2条边
- 无向完全图共有 n(n-2)/2 条边
6.2 n个顶点有向图G
- 所有顶点的出度之和=入度之和=|E|
- 所有顶点的度之和=2|E|
- 若G是强连通图，则最少有n条边（形成回路）
- 有向完全图共有 n(n-2) 条边