L001 图的基本概念
图的定义
一般认为，图论起源于 1730s 「欧拉」（Leonhard Euler）为「柯尼斯堡七桥问题」（Seven Bridges of Königsberg）给出的解。
「图」（graph）的一种简单数学表示是一个二元组，记作 \(G=\left\langle V,E\right\rangle\)，其中 \(V\) 是「顶点」（vertex）的有限集合，顶点也称「结点」（node）；\(E\) 是「边」（edge）的有限集合，\(E\) 中的每条边是一个无序对，由 \(V\) 中的两个顶点组成。
若边 \(e_1=(v_1,v_2)\)，那么 \(v_1,v_2\) 称作 \(e_1\) 的两个「端点」（endpoint），边和它的端点互相「关联」（incident），称一条边的两个端点「相邻」（adjacent），其互为「邻点」（neighbor）。
若又考虑 \(e_2=(v_1,v_2)\)，其和 \(e_1\) 端点完全相同，称呼其为「重边」（multiple edges），也称「平行边」（parallel edges）。为了支持重边，我们扩展图的定义，将 \(E\) 扩展为「多重集」（multiset）。
若 \(e_3=(v,v)\)，即两个端点为同一个端点，那么称 \(e_3\) 为一个「自环」（loop）。
不含自环和重边的图称作「简单图」（simple graph）。
图 \(G=\left\langle V,E\right\rangle\) 中的顶点数量 \(|V|\) 称作 \(G\) 的「阶」（order），记作 \(\nu(G)\). 阶为零的图称为「零图」（null graph）。
图 \(G\) 的边的数量 \(|E|\) 称作 \(G\) 的「边数」（size），记作 \(\epsilon(G)\). 边数为零的图称为「空图」（empty graph），阶为 1 的空图称为「平凡图」（trivial graph）。
若一个简单图的每对顶点都相邻，则称为「完全图」（complete graph），阶为 \(n\) 的完全图记作 \(K_n\).
顶点 \(v\) 关联的边的数量称作 \(v\) 的「度」（degree），记作 \(d(v)\)，特别地，每个自环按 2 计数。度为零的点称为「孤立点」（isolated vertex）。
Th.1.1 对于任意图 \(G=\left\langle V,E\right\rangle\)，有：
该定理俗称「握手引理」（handshake lemma）。
Cor.1.1 任何一个图中，度为奇数的顶点有偶数个。
图 \(G\) 中所有顶点的度构成的非增序列称为 \(G\) 的「度序列」（degree sequence），其中的最大值称为「最大度」（maximum degree），记作 \(\Delta(G)\)；其中的最小值称为「最小度」（minimum degree），记作 \(\delta(G)\).
图的表示
将图表示为矩阵，便可运用线性代数方法对图进行研究，这是「代数图论」（algebraic graph theory）的分支。
对于阶为 \(n\) 的图 \(G\)，其「邻接矩阵」（adjacency matrix）是 \(n\) 维对称方阵，记作 \(\mathbf{A}(G)\)，其第 \(i\) 列第 \(j\) 列元素 \(A_{i,j}\) 表示顶点 \(v_i\) 和顶点 \(v_j\) 共同关联的边的数量，特别地，若 \(i=j\)，则 \(A_{i,i}\) 为两倍 \(v_i\) 关联的自环数。
显然，\(\mathbf{A}(G)\) 的第 \(i\) 列元素和与第 \(i\) 行元素和都是 \(v_i\) 的度，即：
对于阶为 \(n\)，边数为 \(m\) 的图 \(G\)，其「关联矩阵」（incidence matrix）是 \(n\times m\) 维矩阵，记作 \(\mathbf{M}(G)\)，其中第 \(i\) 列第 \(j\) 行元素 \(M_{i,j}\) 表示顶点 \(v_i\) 与边 \(e_j\) 是否关联：1 是 0 否，特别地，若 \(e_j\) 为自环，则 \(M_{i,j}=2\) 当且仅当 \(e_j\) 是关联 \(v_i\) 的自环，否则 \(M_{i,j}=0\).
显然 \(\mathbf{M}(G)\) 第 \(i\) 行元素之后为 \(v_i\) 的度，且任一列元素之和必为 \(2\) ，也即：
以上是图的数学表示，接下来讨论图在计算机内存中的存储方式。
图可以表示为邻接矩阵或关联矩阵，而矩阵可以用二维数组存储在内存中。然而实际中的图往往稀疏（边较少），故而采用「邻接表」（adjacency list）存储。
邻接表是一种数据结构，使用双层嵌套列表存储邻接表。对于阶为 \(n\)，边数为 \(m\) 的图，邻接表的存储空间是 \(O(n+m)\). 当然这个列表的具体实现可以采用数组、链表、哈希表等数据结构，各有优缺点。
图的关系
对于图 \(G=\left\langle V_G,E_G\right\rangle\) 和图 \(H=\left\langle V_H,E_H\right\rangle\)，若 \(V_H\subseteq V_G\) 且 \(E_H\subseteq E_G\)，那么称 \(H\) 是 \(G\) 的「子图」（subgraph）。
在此条件下，若 \(V_H\subset V_G\) 且 \(E_H\subset E_G\)，那么称 \(H\) 是 \(G\) 的「真子图」（proper subgraph）；若 \(V_H=V_G\)，则称 \(H\) 是 \(G\) 的「生成子图」（spanning graph）。
对于图 \(G=\left\langle V,E\right\rangle\)，若 \(V'\subseteq V\) 且以 \(V'\) 为顶点集，\(E\) 中两端点均在 \(V'\) 中的所有边为边集组成的图称为 \(G\) 的「点导出子图」（vertex-induced subgraph），简称「导出子图」（induced subgraph），记作 \(G[V']\).
对于图 \(G=\left\langle V,E\right\rangle\)，若 \(E'\subseteq E\) 且以 \(E'\) 中所有边的端点为顶点集，\(E'\) 为边集组成的图称为 \(G\) 的「边导出子图」（edge-induced subgraph），记作 \(G[E']\).
从简单图 \(G=\left\langle V_G,E_G\right\rangle\) 到图 \(H=\left\langle V_H,E_H\right\rangle\) 的「同构」（isomorphism）是双射 \(f:V_G\to V_H\)，满足边 \((v_i,v_j)\in E\) 当且仅当 \((f(v_i),f(v_j))\in E'\). 若该同构存在，则称 \(G\) 和 \(H\) 「同构」（isomorphic），记作 \(G\cong H\). 特别地，若 \(H=G\) 则称 \(f\) 为 \(G\) 的「自同构」 （automorphism）。
Th.1.2 同构关系是定义在所有简单图的集合上的等价关系。
同构的定义可以扩展到非简单图，只需如此修改：从图 \(G=\left\langle V_G,E_G\right\rangle\) 到 \(H=\left\langle V_H,E_H\right\rangle\) 的同构是两个双射 \(f:V_G\to V_H\) 和 \(g:E_G\to E_H\)，其中 \(e\in E_G\) 的端点为顶点 \(v_i,v_j\in V_G\) 当且仅当 \(g(e)\in E_H\) 且 \(g(e)\) 的端点恰为 \(f(v_i),f(v_j)\in V_H\).
【这里有一张图，图 1.6】
上图展示了「彼得森图」（Peterson graph）
判定两个图是否同构的问题的复杂度属于「非确定性多项式时间」（NP, nondeterministic polynomial-time），但尚不清楚属于「多项式时间」（P, polynomial-time）还是「NP 完全」（NPC, NP-complete），即对该问题复杂度的认识尚不充分。
图的运算
对于图 \(G=\left\langle V,E\right\rangle\)，从 \(G\) 中「删除」（delete）边子集 \(E'\subseteq E\) ，剩余的子图记作 \(G-E'\). 特别地，仅删除一条边 \(e\in E\) 时，\(G-\{e\}\) 可简写为 \(G-e\). 从 \(G\) 中删除边并不会删除其端点。
对于图 \(G=\left\langle V,E\right\rangle\)，从 \(G\) 中「删除」（delete）点子集 \(V'\subseteq V\) ，剩余的子图记作 \(G-V'\). 特别地，仅删除一个顶点 \(v\in V\) 时，\(G-\{v\}\) 可简写为 \(G-v\). 从 \(G\) 中删除顶点时会删除其关联的所有边。
简单图 \(G=\left\langle V,E\right\rangle\) 的「补图」（complement）是以 \(V\) 为顶点集 \(\{(u,v)|(u,v)\notin E\}\) 为边集的简单图，记作 \(\overline{G}\).
对于图 \(G=\left\langle V_G,E_G\right\rangle\) 和图 \(H=\left\langle V_H,E_H\right\rangle\)：
- 它们的「交」（intersection）是以集合 \(V_G\cap V_H\) 为点集，\(E_G\cap E_H\) 为边集的图，记作 \(G\cap H\)；
- 它们的「并」（union）是以集合 \(V_G\cup V_H\) 为点集，\(E_G\cup E_H\) 为边集的图，记作 \(G\cup H\)，若 \(V_G\cap V_H=\varnothing\)，则 \(G\cup H\) 称为「不交并」（disjoint union），又称「和」（sum），记作 \(G+H\)；
- 它们的「联」（join）是向图 \(G+H\) 中增加边集 \(\{(u,v)|u\in V_G,v\in V_H\}\) 得到的简单图，记作 \(G\lor H\).