图论(Graph Theory)是离散数学的一个分支，是一门研究图(Graph)的学问。 图是用来对对象之间的成对关系建模的数学结构，由"节点"或"顶点"(Vertex）以及连接这些顶点的"边"（Edge）组成。 值得注意的是，图的顶点集合不能为空，但边的集合可以为空。图可能是无向的，这意味着图中的边在连接顶点时无需区分方向。否则，称图是有向的。下面左图是一个典型的无向图结构，右图则属于有向图。
**图的分类：**无权图和有权图，连接节点与节点的边是否有数值与之对应，有的话就是有权图，否则就是无权图。 **图的连通性：**在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点 i 到顶点 j 有路径相连（当然从j到i也一定有路径），则称 i 和 j 是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。图的连通性是图的基本性质。 **完全图：**完全是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。 **自环边：**一条边的起点终点是一个点。 **平行边：**两个顶点之间存在多条边相连接。
图的基本术语
顶点(Vertex)：图中的基本单位，也称为节点或结点。
**边(Edge)：**连接两个顶点的线，可以是无向的或有向的，也可能带有权重。
**顶点v的出度(out-degree)：**在有向图中，以 v 为起点有向边数目。
**顶点v的入度(indegree)：**在有向图中，以 v 为终点有向边数目。
**顶点v的度(Degree)：**与 v 相连的边的数目，如果是有向图，顶点 v 的度等于其入度和出度之和。
**路径(Path)：**路径就是从某个顶点到另一个顶点所要经过的顶点序列。
**路径长度：**路径上边的数目称为路径长度。
**最短路径：**从起点到终点经过边的权重和最小的路径。
环(Cycle)：第一个顶点和最后一个顶点相同的路径称为环或回路。
**边的权(Weight)：**在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权。
网(Network)：边上带有权值的图称为带权图，也称网。
图的密度：图中边的数量与顶点数量的比值。
邻接(Adjacent)：如果两个顶点之间有边相连，则称这两个顶点是邻接的。
阶(Order)：图G中顶点集 V 的大小称作图G的阶，比如一个包含 5 个顶点的图可以称为 5 阶图。
自环(Loop)：若一条边的两个顶点为同一顶点，则此边称作自环。
弧：有向图中的有向边也称为弧。
弧头：有向边的终点称为弧头（带箭头的一边）。
弧尾：有向边的起始点称为弧尾（不带箭头的一边）。
桥(Bridge)：若去掉一条边，便会使得整个图不连通，该边称为桥，也可以理解为当且仅当删除这条边后，图的连通分量数量会增加。`
图的定理
**定理1：**无向图中所有顶点的度之和等于边数的 2 倍（因为一条边连接两个点，增加一条边相当于增加两个度）。
**定理2：**有向图中所有顶点的入度之和等于所有顶点的出度之和（有向图中任意一条边，一边是出度一边是入度，所以出度的数量和入度的数量是相等的）。
**定理3：**任意一个无向图一定有偶数个奇点（度为奇数的顶点）。
**定理4：**无论是有向图还是无向图，所有顶点的度之和都是偶数，并且是边数的两倍。即顶点数 n ，边数 E 和度之间对应关系：E=(d[v1]+d[v2]+…+d[vn])/2。
定理5：（欧拉公式）设图G有 e 条边， v 个顶点和 r 个面的平面图，则 v-e+r=2。
图的基本概念和性质
-
图的一些基本概念和术语
1）有向图与无向图：
若 E 是无向边（简称边）的有限集合时，则图 G 为无向图。边是顶点的无序对，记为 (v, w) 或 (w, v）。可以说 w 和 v 互为邻接点。边 (v, w) 依附于 w 和 v , 或称边 (v, w) 和 v, w 相关联。
若 E 是有向边（也称弧）的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为 <v, w>，其中 v, w 是顶点，v 称为弧尾，w 称为弧头，<v, w> 称为从 v 到 w 的弧，也称 v 邻接到 w 。
2）简单图与多重图：
一个图 G 如果满足： ① 不存在重复边； ② 不存在顶点到自身的边。 那么称图 G 为简单图。若图 G 中某两个顶点之间的边数大于 1 条，又允许顶点通过一条边和自身关联，则称图G 为多重图。多重图和简单图的定义是相对的。【数据结构中仅讨论简单图】
3）完全图（又称简单完全图）
对于无向图，|E| 的取值范围为 0 到 n × (n - 1) / 2，有 n × (n - 1) / 2 条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。
对于有向图，|E| 的取值范围为 0 到 n × (n - 1) ， 有 n × (n - 1) 条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。
4）子图与生成子图：
设有两个图 G = (V, E) 和 G’= (V’, E’），若 V’ 是 V 的子集，且 E’ 是 E 的子集，则称 G’ 是 G 的子图。若有满足 V(G’) = V(G) 的子图 G’ ，则称其为 G 的生成子图。
并非 V 和 E 的任何子集都能构成 G 的子图，因为这样的子集可能不是图，即 E 的子集中的某些边关联的顶点可能不在这个 V 的子集中。
5）连通、连通图和连通分量：（针对无向图）
① 在无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的。 ② 若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图。 ③ 无向图中的极大连通子图称为连通分量。
连通的无向图只有一个极大连通子图，即它本身。
假设一个图有 n 个顶点，如果边数小于 n - 1，那么此图必是非连通图。 【思考】：如果图是非连通图，那么最多可以有多少条边？ 【答】：由 n - 1 个顶点构成一个完全图，此时再加入一个顶点则变成非连通图。
6）强连通、强连通图和强连通分量：（针对无向图）
① 在有向图中，如果有一对顶点 v 和 w，从 v 到 w 和从 w 到 v 之间都有路径，则称这两个顶点是强连通的。 ② 若图中任何一对顶点都是强连通的，则称此图为强连通图。 ③ 有向图中的极大强连通子图称为有向图的强连通分量。
【思考】：假设一个有向图有 n 个顶点，如果是强连通图，那么最少需要有多少条边？ 【答】：至少需要 n 条边，构成一个环路。
在无向图中讨论连通性，在有向图中讨论强连通性。
7）生成树与生成森林：
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n，则它的生成树含有 n-1 条边。包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
在非连通图中，连通分量的生成树构成了非连通图的生成森林。
区分极大连通子图和极小连通子图。极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边； 极小连通子图是既要保持图连通又要使得边数最少的子图。
8）顶点的度、入度和出度：
在无向图中，顶点 v 的度是指依附于顶点 v 的边的条数，记为TD(v) 。无向图的全部顶点的度的和等于边数的 2 倍，因为每条边和两个顶点相关联。
在有向图中，顶点 v 的度分为入度和出度，入度是以顶点 v 为终点的有向边的数目，记为 ID(v)；而出度是以顶点 v 为起点的有向边的数目，记为 OD(v) 。顶点 v 的度等于其入度与出度之和，即 TD(v) = ID(v) + OD(v) 。有向图的全部顶点的入度之和与出度之和相等，并且等于边数，这是因为每条有向边都有一个起点和终点。
9）边的权和网：
在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。
10）稠密图与稀疏图：
边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图 G 满足 |E| ＜|V|log|V| 时，可以将 G 视为稀疏图。
11）路径、路径长度和回路：
顶点 vp 到顶点 vq 之间的一条路径是指顶点序列 vp, vi1, vi2, …, vim, vq，当然关联的边也可理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 n 个顶点，并且有大于 n - 1 条边，则此图一定有环。
12）简单路径与简单回路：
在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
13）距离：
从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）。
14）有向树：
一个顶点的入度为 0 、其余顶点的入度均为 1 的有向图，称为有向树。
- 有关图性质的例题 ① 【2009 统考真题】下列关于无向连通图特性的叙述中，正确的是（ A ）。
I. 所有顶点的度之和为偶数
II. 边数大于顶点个数减 1
III. 至少有一个顶点的度为 1
A. 只有 I
B. 只有 II
C. I 和 II
D. I 和 III
② 【2010 统考真题】若无向图 G = (V, E) 中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是（ C ）。
A. 6
B. 15
C. 16
D. 21
③【2017 统考真题】已知无向图 G 含有 16 条边，其中度为 4 的顶点个数为 3,，度为 3 的顶点个数为 4，其他顶点的度均小于 3。图 G 所含的顶点个数至少是（ B ）。
A. 10
B. 11
C. 13
D. 15
④ 【2022 统考真题】对于无向图 G = (V, E), 下列选项中，正确的是（ D ）。
A. 当 |V| > |E| 时，G 一定是连通的
B. 当 |V| < |E| 时，G 一定是连通的
C. 当 |V| = |E| - 1 时，G 一定是不连通的
D. 当 |V| > |E| + 1 时，G 一定是不连通的
邻接矩阵
图的邻接矩阵表示的优点： 非常直观，并且容易实现，编写算法也较简便，因而应用较广； 根据矩阵元素Aij=1或0，便于判定两个顶点之间是否有边（弧）相连； 计算顶点的度数，或有向图的入度、出度方便； 计算图的边数算法简单等。
图的邻接矩阵表示的缺点： 邻接矩阵事实上是一种顺序存储结构，具有顺序结构共有的缺点，比如：只能按最大空间需求申请内存空间、插入和删除顶点复杂等； 空间复杂度高，n个顶点的图，存储邻接矩阵需要n2个单元，如果一个图的顶点数较多，但边（弧）数较少的话--稀疏图，邻接矩阵一样需要n2个存储单元，就太浪费存储空间； 统计图的边数算法虽然简单，用双重循环统计“1”的个数即可，但其时间复杂度为O(n2)。