【图】
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：$G=(V,E)$，其中 $V$ 是非空有限集合，代表顶点，$E$ 是可以为空的有限集合，代表边
若顶点 $v_i$ 和 $ v_j$ 间的边没有方向，则称这条边为无向边，用无序偶对 $(v_i,v_j)$ 表示；若顶点 $v_i$ 和 $v_j$ 间的边有方向，则称这条边为有向边（弧），用有序偶对 $< v_i,v_j >$ 表示，其中 $v_i$ 称为弧头，$v_j$ 称为弧尾
在一个无向图中，对于任意两个顶点 $v_i$ 和顶点 $v_j$，若存在边 $(v_i,v_j)$，则称顶点 $v_i$ 和顶点 $v_j$ 互为邻接点，同时称边 $(v_i,v_j)$ 依附于顶点 $v_i$ 和顶点 $v_j$
在一个有向图中，对于任意两个顶点 $v_i$ 和顶点 $v_j$，若存在弧 $< v_i,v_j >$，则称顶点 $v_i$ 邻接到顶点 $v_j$，顶点 $v_j$ 邻接自顶点 $v_i$，同时称弧 $< v_i,v_j >$ 依附于顶点 $v_i$ 和顶点 $v_j$
若图的任意两个顶点之间的边都是无向边，则称该图为无向图；若图的任意两个顶点之间的边都是有向边，则称该图为有向图
【基本术语】
度
- 在无向图中，依附于顶点 $v$ 的边数称为顶点的度，记为 $TD(v)$，在 $n$ 个顶点 $m$ 条边的无向图中，所有点的度的和为 $2m$，且有：$TD(v)=ID(v)+OD(v)$
- 在有向图中，以顶点 $v$ 为弧头的弧的数目称为顶点的入度，记为 $ID(v)$，在 $n$ 个顶点 $m$ 条边的有向图中，所有点的入度和为 $m$
- 在有向图中，以顶点 $v$ 为弧尾的弧的数目称为顶点的出度，记为 $OD(v)$，在 $n$ 个顶点 $m$ 条边的有向图中，所有点的出度和为 $m$
路径与回路
- 在无向图 $G=(V,E)$ 中，对于一个满足 $(v_{ij-1},v_{ij})\in E(1\leq j\leq m)$的顶点序列 ${v_p=v_{i_0},v_{i_1},v_{i_2},…, v_{i_m}=v_q}$称为从顶点 $v_p$ 到顶点 $v_q$ 之间的路径，若 $G$ 是有向图，则 $G$ 的路径是有方向的
- 在路径序列中，起点和终点相同的路径称为回路（环）
- 在路径序列中，顶点不重复出现的路径称为简单路径
- 在路径序列中，除起点终点外，其余顶点不重复出现的回路称为简单回路
- 对于一个非带权图，路径上边的个数称为路径长度，对于一个带权图，路径上各边权的和称为路径长度
连通性
- 对于图 $G=(V,E)$ 和 $G’=(V’,E’)$，若 $V’\subseteq V,E’\subseteq E$，则称 $G’$ 为 $G$ 的子图，一个图可以有多个子图
- 在无向图中，如果从一个顶点 $v_i$ 到另一个顶点 $v_j(i≠j)$ 有路径，则称顶点 $v_i$ 和 $v_j$ 是连通的，如果图中任意两个顶点都是连通的，则称该图是连通图
- 对于无向图来说，非连通图的极大连通子图称为连通分量，其中，极大是指包括所有连通的顶点及这些顶点相关联的所有边
- 在有向图中，对图中任意一对顶点 $v_i$ 和 $v_j(i≠j)$，若从顶点 $v_i$ 到顶点 $v_j$ 和从顶点 $v_j$ 到顶点 $v_i$ 均有路径，则称该有向图是强连通图
- 对于有向图来说，非强连通图的极大强连通子图称为强连通分量，其中，极大是指包括所有连通的顶点及这些顶点相关联的所有边
- 对于一个具有 $n$ 个顶点的连通图 $G$ ，包含 $G$ 中全部顶点的一个极小连通子图称为生成树，其中，极小是指子图中只有一个入度为 $0$ 的点且其他点的入度均为 $1$，一个连通图的生成树可以有多个
- 在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林
对于 $n$ 个点的无向图 $G(V,E)$ 来说，要保证在任何情况下都是连通的，在最极端的情况下，$n-1$ 个顶点构成一个完全无向图，剩下一个点再加一条边后必然与该图构成一个连通图，即最少需要的边数为：
对于 $m$ 条边的非连通无向图 $G(V,E)$ 来说，最极端的情况下，由 $n$ 个顶点构成的完全图与一个独立的顶点构成，假设最少要 $n$ 个点，那么边数 $m$ 满足：
【特殊形态的图】
- 在一个图中，不存在顶点到其自身的边，且同一条边不重复，则称图为简单图
- 在一个无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图，其有 $\frac{n*(n-1)}{2}$ 条边
- 在一个有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图，其有 $n*(n-1)$ 条边。
- 一个边数接近完全图的图称为稠密图，一个边数远远少于完全图的图称为稀疏图
- 对边赋予的有意义的数值量称为权（权值），边上带权的图，称为网（带权图），根据图是无向图或有向图，分为有向网图、无向网图
