(-w-) 简单初等图论初步入门指导科普用

# 基本概念

# 关于图的定义

• V 是一个非空集，E 是 V 中元素的无序对构成的多重集，有序对 G=<V,E> 则称之为一个图。其中 V 为顶点集，E 为边集。

$$若e=uv\in E(G)，则称u,v为边e的断点，或顶点u，v与边e彼此关联$$

• 在一个图中，同一条边关联的两个顶点称为相邻点，同一个顶点关联的若干边称为相邻边。
• 若 G 中一条边的两端点为同一点，即 e=uu，则称 e 为自环。若 uv 的重复度＞1，则称 uv 是多重边。
• 与一个顶点 u 关联的边的条数称为 u 的度数，记为$d(u)或d_G(u)$。度数为 0 的点称为孤立点，度数为 1 的点称为悬挂点。度数为奇数的点称为奇顶点，度数为偶的点称为偶顶点。

$$特别地，图G中最小度数记为\delta(G)，最大度数记为\Delta(G),也可简写为\delta,\Delta$$

• 设 G 是图，若 V (G)，E (G) 均为有限集，则称 G 为有限图。

  握手定理：

  $$有限图G中满足\sum_{v\in V(G)}d(v)=2\epsilon,其中v或v(G)表示图G的顶点数，\epsilon或\epsilon(G)表示图G的边数\\$$

  由上面引理可得出：有限图中奇顶点的个数必为偶数。

  Havel-Hakimi algorithm:

  $$一个序列可以构成无向图，当且仅当将这个序列降序排列后，将第一个数d_1删去，并将d_2,...,d_{2+d_1-1}减去1后剩下的序列可以构成无向图。$$

  （有点废话的感觉）

• 若图 G 中$v=1,\epsilon=0$，则称其为平凡图。

  若图 G 中$\epsilon=0$，则称其为零图。

  若图 G 中不含多重边和自环，则称其为简单图。

  若图 G 含有多重边，则称其为多重图。

• 若图 G 是一个简单图，且 G 中任意两顶点均有边相连，则称 G 为完全图。n 个顶点的完全图记为$K_n$。

• 若图 G 中存在两个子集$V_1,V_2$, 使得$V_1\cup V_2=V(G),V_1\cap V_2=\varnothing$, 且$V_1$ 中任意两点不相邻，$V_2$ 中任意两点不相邻，则称 G 为二分图。进一步地，若$V_1$ 中每一点和$V_2$ 中每一点相连，则称 G 为完全二分图。且当$|V_1|=m，|V_2|=n$ 时记为K_

• 若图 G 中每个顶点度数都为 k，则称 G 为 k 次正则图。

• 设 G，H 为两个图，若$V(H)\subseteq V(G)且E(H)\subseteq E(G)$，则称 H 是 G 的子图，记为$H\subseteq G$。若$H\subseteq G 且H\neq G$，则称 H 是 G 的真子图，记为$H\subset G$。若$H\subseteq G且V(H)=V(G)$，则称 H 是 G 的生成子图（也称支撑子图）。

• 设 G 是一个图，$E_1\subseteq E(G)$，则把以$E_1$ 为边集，$E_1$ 中全体边的端点为顶点集的图称为由$E_1$ 导出的 G 的子图（边导出子图），类似的，若$V_1\subseteq V(G)$, 则把以$V_1$ 为顶点集，端点均在$E_1$ 中全体边为边集的图称为由$V_1$ 导出的 G 的子图（点导出子图）。

• 设 G 为 n 个顶点的简单图，从这 n 个顶点构成的完全图$K_n$ 中删去 G 的所有边，但保留顶点集 V (G) 所得到的图称为 G 的补图，记为～G。

• 设 G，H 是两个图，若存在双射（一一映射）：

$$\theta:V(G)\rightarrow V(H)\\ \psi:E(G)\rightarrow E(H)\\$$

​ 使得当且仅当 e=uv 时，$\psi(e)=\theta(u)\theta(v)$，则称 G 和 H 时同构的，记为$G\cong H$，而有序对$<\theta,\psi>$ 称为 G 与 H 之间的一个同构映射或简 称为同构。可以证明，图的同构关系为一个等价关系，因此可以把所有图划分为若干等价类。

• 顶点标以名称的图称为标志图。

# 路与连通

• 图中的一个非空点、边交替序列$W=v_0e_1v_1e_2...e_kv_k$ 称为一条从$v_0$ 到$v_k$ 的路径，或称$(v_0,v_k)$- 路径，其中$v_{i-1},v_i$ 是$e_i$ 的端点。称$v_0$ 为 W 的起点，$v_k$ 为 W 的终点，$v_i(0<i<k)$ 为 W 的内点，k 为 W 的路长。

  • 把 W 逆转得到$W^{-1}=v_ke_k...e_2v_1e_1v_0$
  • 而 W 的子序列$v_ie_iv_{i+1}...e_jv_j$ 称为 W 的节。
  • 若 W 的终点是 W’的起点，则可以把 W 和 W’首尾相接得到新路径 WW’。

• 设$v_0e_1v_1e_2v_2...e_kv_k$ 为图 G 中的一条路径：

  • 若$k\geq 1且v_0=v_k$，则称该路径为闭路径，否则为开路径。

  • 若$v_0,v_1,...,v_k$ 互不相同，则称该路径为为路。

  • 若$e_1,e_2,...,e_k$ 互不相同，则称该路径为迹，显然，路一定是迹。

    • 若$k\geq 1 且v_0=v_k$ 则称该迹为闭迹，否则称为开迹。其中，闭迹也称为回路。

• 若闭迹$v_0e_1v_1e_2v_2...e_kv_0$ 中$v_0,v_1,...v_{k-1}$ 互不相同，则称该迹为圈或 k 圈，且当 k 为偶数时为偶圈，k 为奇数时为奇圈。

  • 等价定义：只有$v_0=v_k$ 的路称为圈，即闭路为圈。
  • 定理：若图 G 中每个顶点的度数都大于等于 2，即$\delta \geq2$，则 G 中必有圈。
  • 定理：$图G为二分图\Leftrightarrow G中不含奇圈$

• 若$u,v\in V(G)$ 且存在从 u 到 v 的路，则称 u 和 v 是相连的或连通的，若 G 中任意两点都连通，则称图 G 是连通的。

  • 显然，连通关系是一个等价关系，根据该关系可以把图 G 的顶点集 V 分成若干等价类$V_1,V_2,...,V_n$，而每个由$V_i$ 导出的 G 的点导出子图$G(V_i)$ 称为 G 的一个连通分支。
  • 图 G 的连通分支数由$\omega(G)$ 表示的。显然，$G是连通的\Leftrightarrow \omega(G)=1$
  • 定理：$n-\omega\leq\epsilon\leq\frac{1}{2}(n-\omega)(n-\omega+1)$
    • 由上定理可知：在 n 和$\omega$ 固定时，当 G 的某一个连通分支是$n-\omega+1$ 个顶点的完全图，剩下$\omega-1$ 个分支是孤立点时，G 的边数最大。
    • 由上定理可知：当$\omega=1$ 时，$\epsilon\geq n-1$. 即n 个顶点的连通图至少有 n-1 条边，因此把有 n 个顶点，n-1 条边的连通图称为最小连通图。

• 图 G 中，若 u，v 是连通的，则称最短 (u，v)- 路的长为 u，v 的距离，记为 d (u，v)。

  # 习题部分引理（可自己证明）：

  • 若图中只有两个奇顶点，则它们必连通。
  • 简单图中，必存在长为$\delta$ 的路。
  • 简单图 G 中，若$\epsilon>C_{v-1}^2$, 则 G 连通。
  • 若 G 不连通，则～G 连通。
  • 连通图中，任意两条最长路必有公共顶点。

# 最短路

• 若对图 G 中每条边 e 都规定一个非负实数w (e)，则称 G 为赋权图（或权图），w (e) 称为 e 的权。G 的边与非负实数的这种关系（用 w 表示）称为权函数。特别地，uv 不相邻时，$w(uv)=\infty$。
• 设 G 是一个赋权图，H 是 G 的子图，H 中各边的权之和称为子图 G 的权，记为 w (H)。权图中路 P 的权称为 P 的长度，两点 u，v 之间最短路的长度称为 u，v 之间的距离，记为 d (u，v)。
• G 是一个权图，$u_0\in V(G),S\subseteq V(G),u_0$ 到 S 内各点的所有路中长度最小的称为$u_0$ 到 S 的最短路，其长度称为$u_0$ 到 S 的距离，记为$d(u_0,S)$。
• Dijkstra 算法原理：若$S\subset V,u\in S$, 则d(u,\sim S)=min_{u_1\in s,v\in \sim S}\

# 有向图

• 设 V 是一个非空集合，A 是一个由 V 中元素的有序对构成的多重集，有序对 D=<V,A> 则称为一个有向图，其中，V 为顶点集，其元素称为顶点或点，A 称为弧集，其元素称为弧。

• 设 D 是一个有向图，若$a=<u,v>\in A(D)$，则称 a 从 u 连接到 v，且称 u，v 与 a 彼此相关联；称 u 是 a 的尾或起点，称 v 是 a 的头或终点。且统称 u，v 是 a 的端点。（箭头指向的是箭头的头）

• 子有向图，真子有向图，导出子有向图等定义与无向图类似。

• 对于每个有向图 D，忽略其弧的方向，这样得到的无向图称为 D 的底图。反之，对于一个无向图，对它每一条边确定一个方向，得到的有向图称为它的一个定向图。

  • 有向图 D 的底图连通时，我们称 D 是连通的，底图中有圈时，我们称 D 中有圈。

• 我们用$d_D^-(v)和d_D^+(v)$ 定义 v 的入度和出度，即以 v 为头的弧的数目和以 v 为尾的弧的数目。同样有最大最小入度出度$\delta^+,\delta^-,\Delta^+,\Delta^-,\delta=min(\delta^-,\delta^+),\Delta=max(\Delta^-,\Delta^+)$。显然有$\sum_{v\in V}d^-(v)=\sum_{v\in V}d^+(v)=\epsilon$

• 有向图的有向路径是指一个非空有限的点、弧交替序列$W=v_0a_1v_1a_2...a_kv_k$，其中$a_i的头是a_i,尾是a_{i-1}$。同理若 W 中点互不相同则成为有向路，若 W 中弧互不相同则成为有向迹，有向闭迹（有向回路），有向圈也可以类比无向图定义。

• 如果 D 中存在有向 (u，v)- 路，则称 v 是从 u 可达的。如果 u，v 是互相可达的，则称 u，v 是双向连通的。若 D 中任意两顶点，至少有一顶点可从另一顶点到达，则称 D 为单向连通图。若 D 中任意两点都是双向连通的，则称 D 是双向连通图或强连通图。

  • 只有双向连通关系是一个等价关系，根据它可以把图 D 分成若干强连通分支。而所有强连通分支不一定覆盖整个图。

• 若有向图 D 中每两个顶点有且恰有一条弧，则称 D 为竞赛图。显然，D 是竞赛图当且仅当 D 是完全图的定向图。

# 图的矩阵表示

• 图的关联矩阵：$A_{v\times \epsilon},a_{ij}=1当且仅当点i和边j关联，否则a_{ij}=0$. 即关联矩阵每列只有两个 1，每行的 1 的个数为行序号代表顶点的度数。
• 图的邻接矩阵。简单无向图的邻接矩阵 X 的 n 次方$X^n$ 中第 i 行第 j 列的数表示从顶点 i 到顶点 j 的长度为 n 的路径数目。

# Euler 图与 Hamilton 图

# Euler 图

• 图 G 中包含所有边的迹称为 Euler 迹，闭的 Euler 迹称为 Euler 闭迹（Euler 回路），具有 Euler 回路的图称为 Euler 图。只具有 Euler 开迹的图称为半 Euler 图。Euler 迹实际上就是一条一笔画。

  • 连通图 G 是 Euler 图当且仅当 G 中所有顶点均为偶顶点。
  • 连通图 G 是半 Euler 图当且仅当 G 中恰有两个奇顶点。

• 有向图 D 中包含左右弧的有向迹称为 Euler 有向迹，具有 Euler 有向闭迹（Euler 有向回路）的有向图称为 Euler 有向图，具有 Euler 有向开迹的有向图称为半 Euler 有向图。显然，Euler 有向图中若无孤立点，则必强连通。

• 有向图 D 中，$v\in V(G)$，若$d^-(v)=d^+(v)$ 则称 v 是平衡的，若 D 中每个顶点都是平衡的，则称 D 是平衡的。若存在 k，使得 D 中每个顶点的出度和入度都等于 k，则称 D 是一致平衡的。

  • 单连通有向图 D 是 Euler 图当且仅当 D 是平衡的。
  • 单连通有向图 D 是半 Euler 图当且仅当 G 中恰有两个奇顶点 u，v 满足$d^-(v)=d^+(v)+1,d^+(u)=d^-(u)+1$。

# Hamilton 图

• 图 G 中包含所有顶点的圈称为 Hamilton 圈，含有 Hamilton 圈的图称为 Hamilton 图。G 中含有所有顶点的路称为 Hamilton 路，含有 Hamilton 路的图称为半 Hamilton 图。

  • 判断一个图是否是 Hamilton 图是 NP 完全问题。
  • 图 G 是 Hamilton 图，则对于顶点集 V 的任意非空真子集 S，均有$\omega(G-S)\leq |S|$。其中 G-S 表示 G 中删除 S 中的所有顶点及其关联边剩下的子图。（必要条件）
  • 简单图 G 中，若$v\geq 3 且\delta\geq \frac{v}{2}$，则 G 是 Hamilton 图。（充分条件）
  • 引理：简单图 G 中，$u_1$ 和$u_2$ 是不相邻的顶点，且满足$d(u_1)+d(u_2)\geq v$，则 G 是 Hamilton 图当且仅当$G+u_1u_2$ 是 Hamilton 图。（充要条件）。

• 图 G 中，反复连接满足$d(u_1)+d(u_2)\geq v$ 的不相邻顶点$u_1,u_2$，直到没有这样的顶点对。得到的图称作 G 的闭包，记为 C (G)。即简单图 G 是 Hamilton 图当且仅当 C (G) 是 Hamilton 图。

  • 推论：若 C (G) 是完全图，则 G 是 Hamilton 图。

• 有向图 D 中，包含所有顶点的有向圈称为 Hamilton 有向圈，含有 Hamilton 有向圈的有向图称为 Hamilton 有向图，D 中包含所有顶点的路称为 Hamilton 有向路，含有 Hamilton 有向路的有向图称为半 Hamilton 有向图。显然，半 Hamilton 有向图一定是强连通的。

  • 竞赛图必定是半 Hamilton 有向图。
  • 强连通的竞赛图必定是 Hamilton 有向图。

# 作业引理

• 若 G 是一个具有奇数个顶点的二分图，则 G 中没有 Hamilton 圈。
• 若无向图 G 存在一个强连通的定向图，则称它为可定向的。
  • 任意一个 Euler 图都是可定向的。
  • 任意一个 Hamilton 图都是可定向的。

# 树

• 连通无回路的图称为树。树中度为 1 的点称为树叶，度大于 1 的点称为分枝点或内点，每个连通分支均为树的图称为森林。

• T 是 n 个顶点$\epsilon$ 条边的非平凡图，以下条件等价：

  • T 是树
  • T 中无回路，且$\epsilon=n-1$
  • T 连通，且$\epsilon=n-1$
  • T 中无回路，且在 T 的任意两个不相邻点之间添加一条边都会得到回路。
  • T 连通，删去任意一边就会不连通。
  • T 的任意两个不同顶点之间恰有一条路。

• 定理：任意一棵非平凡树中，至少有两片树叶。

  # 作业引理

  • 对于$n\geq 2$，设$d_1,d_2,...,d_n$ 是 n 个正整数，且$\sum d_i=2n-2$，则存在顶点度数为$d_1,d_2,...,d_n$ 的一棵树。
  • $\Delta\geq k$ 的树至少有 k 个树叶。

# 生成树

• 若图 G 的生成子图 T 是树，则称 T 是 G 的生成树。

  • G 是连通图当且仅当 G 有生成树。

• 权图 G 中带权最小的生成树称为最小生成树或最优树。

  • Kruskal 算法（（（（

# 有向树

• 底图是树的有向图称为有向树。

• 若一棵有向树中恰有一个顶点入度为 0，其余所有顶点的入度均为 1，则称该有向树为有根树或树形图，入度为 0 的顶点称为根。

  • 有根树 T 的根到其余每个顶点都有且恰有一条有向路。

• 设 u 是有根树的分枝点，若从 u 到 s 有一条弧 <u,s> 则称 s 是 u 的儿子，u 为 s 的父亲；同一父亲的儿子称为兄弟；若从 u 到 v 有一条有向路，则称 v 是 u 的子孙，u 是 v 的祖先；从根到某一顶点的路长称为该顶点的路长或层数，从根到树叶的最大层数称为有根树的高。

• 设 u 是有根树 T 的一个顶点，$V_u$ 是 u 及其子孙构成的顶点集，$V_u$ 的导出子图称为 T 的以 u 为根的子树。

• 在有根树中，将每个分枝点发出的弧从左到右依次标以正整数 1，2，3，…，则该有根树称为有序树。

• 有序树中，如果每个顶点 v 都满足$d^+(v)\leq m$，则称该有序树为 m 叉树，如果每个顶点 v 都满足$d^+(v)=m$ 则称该有序树为正则 m 叉树。

  • 定理：正则 m 叉树中，分枝点数 i 与树叶数 l 满足：$(m-1)i=l-1$
  • 定理：T 是正则 m 叉树，i 表示分枝点数，I 表示分枝点的路长总和，L 表示树叶的路长总和，则$L=(m-1)I+mi$

# 平面图和图的着色

# 平面图

• 如果一个图可以画在平面上，使得它的边在端点之外不相交，则称这个图为平面图，或说它是可平面嵌入的。平面图 G 的这样一种画法称为 G 的一个平面嵌入或平图。

• 一条连续的，自身不相交的封闭曲线称为 Jordan 曲线。

  • Jordan 曲线把平面分成了两部分，其中一部分是无界的，这一部分（不含曲线本身）称为 J 的外部，记为 extJ，extJ 的点称为 J 的外点，extJ 与 J 的并称为 extJ 的闭包，记为 ExtJ。另一部分（不含曲线本身）称为 J 的内部，记为 intJ，intJ 的点称为 J 的内点，intJ 与 J 的并称为 intJ 的闭包，记为 IntJ。
  • 引理：任何连接 Jordan 曲线 J 的内点与外点的曲线必与 J 相交。
  • 苏博南猜想：任一个多面体，将其顶点当作顶点，棱当作边的图为平面图。

• 平图 G 把平面划分成若干个连通区域，每个连通区域的闭包称为 G 的一个面，其中恰有一个无界的面，称为外部面。（注：” 面 “的概念只在平图中讨论）

  • 欧拉公式：连通平图 G 中满足$v-\epsilon+f=2$
  • 推论：给定平面连通图 G，则 G 的所有平面嵌入都有相同的面数。
  • 推论：若 G 是平面简单图，$v\geq3$，则有$\epsilon\leq 3v-6$
    • 由上推论：平面简单图中，必然存在一个度数小于等于 5 的顶点。
  • 推论：若平图 G 的每个面由至少四条边围成，则有$\epsilon\leq 2v-4$，其实如果平图 G 每个面至少由 k 条边围成，则$v\geq(1-\frac{2}{k})\epsilon+2$

• 图 G 中删除一条边 uv，并且添加一个二度点 w 和两条边 uw 和 wv，则称边 uv 被细分。若图 H 是由图 G 经过一系列边的细分而得到，就称 H 是 G 的剖分图或细分图，G 是 H 的收缩图。若两个图是同一个图的剖分图，则称这两个图同胚。

  • Kuratowski 定理：图 G 是平面图，当且仅当$K_5和K_{3,3}$ 的任何细分图都不是 G 的子图。即 G 的任意一个子图都不是$K_5或K_{3,3}$ 的细分图。

  # 作业引理

  • $K_5或K_{3,3}$ 中任意删除一条边得到的图都是平面图。
  • 平面图 G 满足$v-\epsilon+f=\omega(G)+1$

# 对偶图

• 设 G 是一个平图，先作一新图 G*：

  （1）对应 G 的面$F_1,F_2,...,F_f$ 作顶点$F^*_1,F^*_2,...,F^*_f$

  （2）当且仅当$e\in E(G)$ 是 G 的两个面$F_i,F_j$ 的公共边时，在$F^*_i和F^*_j$ 之间连一条边 e*

  （3）当且仅当$e\in E(G)$ 两侧为同一个面时，在该面对应的顶点上作一个子环

  这样做成的图 G * 称为 G 的对偶图。图 G** 中可以有平行边。

  • 对偶图必定是平面图
  • 对偶图的对偶图与原图同构，即$G^{**}\cong G$
  • 同构的图的对偶图不一定同构。即$G_1\cong G_2\nRightarrow G_1^*\cong G_2^*$

• 对偶图 G 和图 G 的关系：$v^*=f,\epsilon*=\epsilon,f^*=v$

  # 作业引理

  • 若一个图和它的对偶图同构，则称它是自对偶的。自对偶的图满足$\epsilon=2v-2$

# 顶点着色

• 图 G 中对 G 的每个顶点着色，使得没有两个相邻的顶点着上相同的颜色，这种着色称为图的正常着色。若图 G 的顶点可用 k 种颜色正常着色，则称 G 是 k - 可着色的。使 G 是 k - 可着色的最小的 k 称为 G 的色数，记为$\chi(G)$，若$\chi(G)=k$，则称 G 是 k 色的。

  • 对于完全图$K_n$，有$\chi(K_n)=n,\chi(~K_n)=1$
  • 对于 n 个顶点构成的圈$C_n$，当 n 为偶数时$\chi(C_n)=2$，当 n 为奇数时，$\chi(C_n)=3$
  • 对于非平凡树 T，有$\chi(T)=2$
  • G 是二分图，则$\chi(G)=2$
  • 对于任意简单图 G，有$\chi(G)\leq1+\Delta(G)$
  • 若简单连通图 G 不是完全图且不是奇圈，则$\chi(G)\leq\Delta(G)$
  • 五色定理：任何无自环的平面图 G 是 5 - 可着色的。

  # 作业引理

  • 图 G 是 2 - 可着色的当且仅当 G 种无奇圈。
  • 如果对 G 的每个真子图 H 都有$\chi(H)<\chi(G)$，则称 G 是临界的。k 色的临界图称为 k - 临界图。k - 临界图满足$\delta\geq k-1$
  • 每个 k 色图至少有 k 个度大于等于 k-1 的顶点。

# 面着色

• 设 e 是 G 的一条边，若$\omega(G-e)>\omega(G)$，则称 e 是 G 的割边。

• 割边的两侧为同一个面。

• 一个没有割边的连通平图称为地图。地图种的两个面如果有一条公共边，则称这两个面是相邻的。

• 设 G 是一个地图，对 G 的每个面着色，使得没有两个相邻的面着上相同的颜色，则称这种着色为地图的正常面着色，地图 G 可用 k 种颜色正常面着色，则称 G 是 k - 面可着色的。使得 G 是 k - 面可着色的最小的 k 称为 G 的面色数，记为$\chi^*(G)$。若$\chi^*(G)=k$ 则称 G 是 k - 面色的。

  • 显然地图中有$\chi(G^*)=\chi^*(G)$
  • 五色定理：任何地图 G 是 5 - 面可着色的。

  # 作业引理

  • 地图 G 是 2 - 面可着色的当且仅当它是一个欧拉图。