Lec6 Graphs

再次回到图论的世界。😎离散数学和数据结构的图论侧重点不一样，姑且再复习一下。

图类型

图的二分性（Bipartite Graphs）

1. 二分图的定义：

二分图（Bipartite Graph）是可以将顶点集合划分为两个不相交子集 $ U $ 和 $ V $，使得图中的每条边都连接 $ U $ 中的一个顶点和 $ V $ 中的一个顶点的图。
换句话说，二分图中没有任何一条边的两个端点在同一个子集中。

2. 示例分析：

Example 2.9：$ C_6 $ 是二分图

$ C_6 $： 一个包含 6 个顶点的环形图（Cycle Graph）。
判断二分性：
- 将顶点分为两个集合，按交替顺序分配：集合 $ U $ 包含环中的奇数位置的顶点，集合 $ V $ 包含偶数位置的顶点。
- 每条边连接的顶点分别来自 $ U $ 和 $ V $。
- 因此 $ C_6 $ 可以划分为两个集合且满足二分图的定义。
结论： $ C_6 $ 是二分图。

Example 2.10：$ K_3 $ 不是二分图

$ K_3 $： 一个包含 3 个顶点的完全图（Complete Graph）。
判断二分性：
- $ K_3 $ 中的每个顶点与其他两个顶点直接相连。
- 任意划分顶点集合 $ U $ 和 $ V $，必然存在两个同属一个集合的顶点之间有边相连。
- 这种情况不符合二分图的定义。
结论： $ K_3 $ 不是二分图。

3. 总结：

二分图的特性：
- 图中没有奇数长度的环。
- 顶点可以分为两个集合，边只连接不同集合的顶点。
示例总结：
- $ C_6 $ 是二分图，因为其环长度为偶数。
- $ K_3 $ 不是二分图，因为它是奇数长度环的完全图。

关于图的顶点数问题

完全图 $ K_n $
公式：
完全图 $ K_n $ 是指有 $ n $ 个顶点的图，任意两点之间都有一条边连接。
边数：
$ |E| = 1 + 2 + + (n-1) = $
顶点数：
$ |V| = n $。
循环图 $ C_n $
公式：
循环图 $ C_n $ 是由 $ n $ 个顶点和 $ n $ 条边构成的一个封闭环。
边数：
$|E| = n$
顶点数：
$ |V| = n $。
轮图 $ W_n $
公式：
轮图 $ W_n $ 是由一个循环图 $ C_{n-1} $ 和一个额外的中心顶点构成，每个循环顶点与中心顶点相连。
边数：
$|E| = 2n$
顶点数：
$ |V| = n $。
完全二分图 $ K_{m,n} $
公式：
完全二分图 $ K_{m,n} $ 是一个图，其中顶点集合被分为两个不相交的子集，分别含有 $ m $ 和 $ n $ 个顶点，且每个子集中任意两个顶点之间都没有边，但不同子集中的任意两个顶点之间都有边。
边数：
$|E| = mn$
顶点数：
$ |V| = m + n $。

度

注意自环。

问题 1：图 S

已知图 $ S $ 有 16 条边，每个顶点的度为 2。求图中城市的数量。

解答：
根据度数总和公式，图中所有顶点的度数之和等于 $ 2 $。
假设图中有 $ x $ 个顶点，则
$ = 2x = 2 $
解得 $ x = 16 $。

解释：
每个顶点的度为 2，说明图 $ S $ 是一个环图（Cycle Graph），其中每个城市与两个其他城市相连，因此顶点总数为 16。

问题 2：图 T

已知图 $ T $ 有 21 条边，3 个顶点的度为 4，其他顶点的度为 3。求图中港口的数量。

解答：
根据度数总和公式，图中所有顶点的度数之和等于 $ 2 $。
假设图中有 $ x $ 个顶点，则
$ 3 + (x - 3) = 2 $
解得 $ x = 13 $。

解释：

图中有 3 个顶点的度为 4，其余 $ x-3 $ 个顶点的度为 3。
使用度数总和公式计算，总共有 13 个顶点（港口）。

并行算法与线性阵列架构（Parallel Algorithms and Linear Array Architecture）

1. 并行算法简介

并行算法是一种通过将问题分解为多个子问题，并利用多处理器系统同时求解的计算方法。
目标是提高计算效率和减少运行时间。

2. 并行架构的三种常见类型

并行架构是并行算法的硬件支持形式，以下是常见架构之一：线性阵列（Linear Array）。

线性阵列架构

定义：
- 线性阵列是一种并行处理器架构。
- 处理器被排列成一维的线性结构，每个处理器直接与它的相邻处理器通信。
特点：
1. 简单结构： 处理器按线性排列。
2. 局部通信： 每个处理器只与相邻的处理器通信，降低了复杂性。
3. 扩展性： 容易增加处理器数量以扩展规模。
适用场景：
- 问题可以分解为需要局部处理的子问题。
- 如求解一维问题（如线性递推、序列计算）。

3. 示例分析：

Example 2.16：线性阵列并行算法

问题描述： 将一个大问题分解为多个子问题，通过一个具有线性阵列架构的多处理器计算机求解。
实现步骤：
1. 分解： 将问题分解为多个相互依赖的子问题。
2. 分配： 将子问题分配给线性阵列中的处理器，每个处理器解决一个或多个子问题。
3. 通信： 处理器之间通过相邻通信共享结果或同步进度。
4. 合并： 将各处理器的计算结果整合，得到最终答案。
优点：
- 高效地处理线性递推类型问题。
- 通信开销较低，因为只需要与相邻处理器通信。

图的表示

有向图的邻接矩阵

定义：
对于一个有向图 $ G = V, E $，设顶点集合 $ V $ 中的顶点依次为 $ v_1, v_2, , v_n $，则其邻接矩阵 $ A $ 是一个 $ n n $ 的矩阵，其中：
$ a_{ij} = \[\begin{cases} 1, & \text{如果有一条从 } v_i \text{ 到 } v_j \text{ 的有向边} \\ 0, & \text{否则。} \end{cases}\] $
性质：
- 如果 $ G $ 是一个简单图（无自环或多重边），则 $ A $ 是一个 0-1 矩阵。
- 矩阵 $ A $ 的行号对应出度，列号对应入度。

无向图的关联矩阵（Incidence Matrix）

定义：
对于一个无向图 $ G = V, E $，假设顶点集合 $ V = {v_1, v_2, , v_n} $，边集合 $ E = {e_1, e_2, , e_m} $，则关联矩阵 $ M $ 是一个 $ n m $ 的矩阵，矩阵元素定义为： $ m_{ij} = \[\begin{cases} 1, & \text{如果顶点 } v_i \text{ 是边 } e_j \text{ 的一个端点} \\ 0, & \text{否则。} \end{cases}\] $
性质：
- 每一列有两个 1（对应边的两个端点），其余为 0。
- 如果边有方向性，则可以对列中 1 的符号作区分（例如，出发点为 1，终点为 -1）。

示例

有向图邻接矩阵：
对于顶点集合 $ V = {v_1, v_2, v_3} $，边集合 $ E = {(v_1, v_2), (v_2, v_3)} $，邻接矩阵为：$ A =
\[\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}\]
. $
无向图关联矩阵：
对于顶点集合 $ V = {v_1, v_2, v_3} $，边集合 $ E = {e_1, e_2} $，其中 $ e_1 = {v_1, v_2} $，$ e_2 = {v_2, v_3} $，关联矩阵为：$ M =
\[\begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix}\]
. $

例子：

图同构（Graph Isomorphism）

什么是图的同构？

定义：
简单图 $ G_1 = (V_1, E_1) $ 和 $ G_2 = (V_2, E_2) $ 是同构的，当且仅当存在一个从 $ V_1 $ 到 $ V_2 $ 的双射 $ f $，使得：$ a, b V_1, G_1 a b G_2 f(a) f(b) $
- 简单解释： 同构意味着两个图在结构上完全相同，只是顶点的命名方式不同。
- $ f $ 被称为图同构函数（isomorphism）。

形式化定义：

图 $ G_1 = (V_1, E_1) $ 和 $ G_2 = (V_2, E_2) $ 是同构的，当且仅当存在一个双射 $ f: V_1 V_2 $，使得：$ a, b V_1, , (a, b) E_1 (f(a), f(b)) E_2。 $

图同构的性质：

顶点和边数量相等：
- 若 $ G_1 $ 和 $ G_2 $ 同构，则 $ |V_1| = |V_2| $，且 $ |E_1| = |E_2| $。
度数相等：
- $ G_1 $ 中每个顶点的度数必须与 $ G_2 $ 中对应顶点的度数相等。
两图的重要性质保持一致：
- 是否是二分图。
- 是否是连通图。
- 图的子结构，例如环的数量、长度等。
结构一致性：
- 图的邻接矩阵或邻接表在某种重新排列下相等。

图同构的意义：

两个图的同构性表明它们是完全等价的，即使它们的顶点命名和绘制方式不同。
例子：
两个不同绘制方式的三角形图（3 个顶点，3 条边）是同构的，因为它们的结构完全一致。

例子

简单同构：
- 图 $ G_1 $: $ V_1 = {a, b, c}, E_1 = {(a, b), (b, c), (a, c)} $
- 图 $ G_2 $: $ V_2 = {x, y, z}, E_2 = {(x, y), (y, z), (x, z)} $
- 显然 $ f(a) = x, f(b) = y, f(c) = z $ 是一个同构函数。
非同构：
- 如果 $ G_1 $ 是一个三角形图，但 $ G_2 $ 是一条链图（3 个顶点，2 条边），则它们不是同构的。

必要但非充分条件：图同构

问题描述

对于两个简单图 $ G_1 = (V_1, E_1) $ 和 $ G_2 = (V_2, E_2) $，判断它们是否同构时，有以下必要但非充分条件。

必要但非充分条件

顶点数量相同，边数量相同： $ |V_1| = |V_2| |E_1| = |E_2| $
- 解释： 两个同构的图必须有相同数量的顶点和边。
每种度数的顶点数量相同：
- $ G_1 $ 和 $ G_2 $ 中具有相同度数的顶点数量必须一致。
- 示例： 如果 $ G_1 $ 有 3 个度数为 2 的顶点，$ G_2 $ 也必须有 3 个度数为 2 的顶点。
所有真子图的等价性：
- 对于 $ G_1 $ 的每一个真子图 $ g $，都必须存在 $ G_2 $ 中的一个真子图与 $ g $ 同构。
- 解释： 这保证了两个图在局部结构上保持一致。

必要条件≠充分条件

满足上述条件并不一定保证 $ G_1 $ 和 $ G_2 $ 是同构的。
原因： 两个图可能在局部性质上相同，但在全局的边连接方式上不同。

示例

满足必要条件但非同构的图：
- $ G_1 $：一个正方形图（4 个顶点，4 条边）。
- $ G_2 $：一个链式图（4 个顶点，3 条边）。
- 分析：
  - 顶点数相同：$ |V_1| = |V_2| = 4 $。
  - 边数相同：$ |E_1| = |E_2| = 4 $。
  - 顶点度数相同：每个顶点的度数都为 2。
  - 但由于结构不同，它们不是同构图。
同构的图：
- $ G_1 $：三角形图（3 个顶点，3 条边）。
- $ G_2 $：不同绘制的三角形图（3 个顶点，3 条边）。
- 分析：
  - 顶点数和边数相同。
  - 顶点度数分布相同。
  - 图结构完全一致。

路径与回路在图同构中的应用

路径和回路在判断图同构中的作用

在判断两个图是否同构时，路径和回路可以提供有力的帮助。
回路，尤其是特定长度的简单回路，作为图的一个不变量，是判断图是否同构的一个有效工具。如果两个图中不存在相同长度的简单回路，那么这两个图一定不可能是同构的。

同构不变量：简单回路的长度

对于简单图来说，一个非常有用的同构不变量是简单回路的长度。
- 简单回路：指的是一个从某个顶点出发经过若干个顶点返回到原点的路径，且不重复经过任何其他顶点。
- 如果两个图具有不同长度的简单回路，那么它们一定不是同构的。

路径的作用

除了回路，路径也可以用于构造可能的同构映射。
- 通过路径，可以为两个图之间构造一个一一对应的映射（即同构映射），从而判断两个图是否同构。

connected

题目1：

问题： 设有7个人：a、b、c、d、e、f、g，他们会讲的语言如下：

a 会讲英语；
b 会讲汉语和英语；
c 会讲英语、西班牙语和俄语；
d 会讲日语和汉语；
e 会讲德语和西班牙语；
f 会讲法语、日语和俄语；
g 会讲法语和德语。

问：这7个人中，是否任意两个都能交谈（必要时可借助其他人的翻译）？

解法：

我们将每个人和每种语言都视为图中的结点。假设每个人会讲某种语言，那么就用一条无向边将该人和语言结点连接起来。例如，a 会讲英语，那么就用一条边将 a 和 "英语" 语言结点连接。

这样，问题转化为判断图是否是连通图。具体来说，若图是连通图，则说明从任意一个人出发，都可以通过直接或间接的语言连接到其他人，即任意两个人都能交谈。

步骤：

构建图：
- 结点： 图中有 7 个结点代表 7 个人（a, b, c, d, e, f, g），另外有 7 个结点代表 7 种语言（英语、汉语、西班牙语、俄语、日语、德语、法语）。
- 边：如果某个人会讲某种语言，那么就用一条无向边连接该人和语言结点。例如，a 会讲英语，那么就将 a 与“英语”语言结点连接。
判断连通性：
- 我们检查图中的连通性。若每两个人之间都可以通过语言连接起来（直接或间接通过其他人的翻译），则图是连通的。
连通图的验证：
- 通过构建图，我们可以看到所有的人都可以通过至少一种语言相互连接。通过间接连接，每个人都能通过他所会讲的语言与其他人建立联系。因此，该图是连通的。

割点与割边

定义

割点（Cut Vertex）：
- 描述： 如果从图中移除一个顶点及与其相关的所有边，导致图的连通分量数量增加，则该顶点称为割点。
- 性质：
  - 如果从一个连通图中移除割点，那么生成的子图将变得不连通。
割边（Cut Edge 或 Bridge）：
- 描述： 如果从图中移除一条边，导致图的连通分量数量增加，则该边称为割边或桥。
- 性质：
  - 割边的移除会直接导致图的连通性被破坏。

割点的特性

作用： 割点的存在表明该顶点对图的整体连通性至关重要。
图示效果：
- 如果割点被移除，剩余的图将分裂为多个连通部分。

割边的特性

作用： 割边的存在表明该边在维持图的连通性方面具有重要作用。
图示效果：
- 如果割边被移除，图将分裂为多个连通部分。

示例

割点示例：
- 图 $ G $ 是一个 Y 型图，顶点 $ v $ 位于 Y 的交点位置。
- 如果移除 $ v $，则原本连通的 Y 型图会分裂为三个部分。
- $ v $ 是图 $ G $ 的割点。
割边示例：
- 图 $ G $ 是一个链式图，边 $ e $ 位于链的中间。
- 如果移除 $ e $，链会分裂为两个不连通的部分。
- $ e $ 是图 $ G $ 的割边。

有向图中顶点之间总有路径的条件

定义 4：强连通图（Strongly Connected Graph）

描述： 如果有向图中任意两个顶点 $a$ 和 $b$ 满足：
- 从 $a$ 到 $b$ 存在路径。
- 从 $b$ 到 $a$ 也存在路径。
则称该有向图是强连通图。
性质：
- 强连通图中的所有顶点之间都可以通过遵循边的方向连通。

定义 5：弱连通图（Weakly Connected Graph）

描述： 如果一个有向图在忽略所有边的方向后，其对应的无向图是连通的，则称该有向图是弱连通图。
换句话说，弱连通图是指：
- 忽略边的方向时，任意两顶点之间都存在路径。
性质：
- 强连通图一定是弱连通图，但弱连通图不一定是强连通图。

比较

性质	强连通图	弱连通图
路径的方向要求	必须有从 $a \to b$ 和 $b \to a$ 的路径	忽略方向后，顶点之间有路径即可
图的连通性条件	更严格	较宽松
强弱关系	强连通图必定是弱连通图	弱连通图不一定是强连通图

有向图的强连通分量

定义：强连通分量（Strongly Connected Component）

描述： 一个有向图 $G$ 的强连通分量（简称强分量）是指图中一个强连通的子图，并且这个子图不能包含在更大的强连通子图中。
- 强连通子图：其中任意两个顶点之间都有路径（不论方向如何）。
- 最大强连通子图：子图是强连通的，并且无法扩展为更大的强连通子图。

特点

强连通分量的构成：
- 强连通分量是有向图 $G$ 的一个子图，其中任意两顶点 $a$ 和 $b$ 都有路径从 $a$ 到 $b$，并且从 $b$ 到 $a$。
- 该子图是最大强连通子图，即不能扩展成更大的强连通子图。
分解成强连通分量：
- 有向图 $G$ 可以通过将其分解为多个强连通分量来研究每个分量的性质。
- 每个强连通分量是一个自包含的强连通子图，不存在顶点能连接到图外的其他部分。

如何识别强连通分量

使用算法如 Kosaraju 算法 或 Tarjan 算法 来查找有向图中的所有强连通分量。

强连通分量的性质

最大性： 强连通分量是不能包含在更大的强连通子图中的。
分解： 图的所有强连通分量可以组成该图的一个分解，即原图中每个顶点都属于某个强连通分量。
有向图的简化： 将强连通分量视为一个单一节点构成的新图，这个新图称为缩点图，该图为一个有向无环图（DAG）。

计数图中顶点间的路径

通过邻接矩阵计数路径

在图中，两个顶点之间的路径数量可以通过图的邻接矩阵来确定。

定理 2：路径计数定理

设图 $ G $ 的邻接矩阵为 $ A $，顶点的顺序为 $ v_1, v_2, , v_n $。对于正整数 $ r $，从顶点 $ v_i $ 到 $ v_j $ 的长度为 $ r $ 的不同路径的数量等于邻接矩阵 $ A $ 的 (i, j) 元素。

证明

从 $ v_i $ 到 $ v_j $ 的长度为1的路径数量就是邻接矩阵 $ A $ 的 (i, j) 元素，因为这个元素表示从顶点 $ v_i $ 到顶点 $ v_j $ 的边的数量。
对于长度为 $ r $ 的路径，$ A^r $ 的 (i, j) 元素表示从 $ v_i $ 到 $ v_j $ 的所有长度为 $ r $ 的路径的数量。

路径计数的推导

通过矩阵的幂次，我们可以得到路径的数量。例如，邻接矩阵的平方 $ A^2 $ 表示从一个顶点到另一个顶点经过两条边的路径数量，$ A^3 $ 表示经过三条边的路径数量，依此类推。
$ A^r $ 的 (i, j) 元素表示从 $ v_i $ 到 $ v_j $ 的路径数，其中路径的长度为 $ r $。

欧拉路径与回路

定义 1：

欧拉回路（Euler Circuit）：在图 G 中，欧拉回路是一个简单回路，包含图 G 中的每一条边，并且每一条边只经过一次。
欧拉路径（Euler Path）：在图 G 中，欧拉路径是一个简单路径，包含图 G 中的每一条边，并且每一条边只经过一次。

1. 欧拉回路： - 是一种特殊的回路，它遍历图中的所有边，每条边只经过一次，且回到起点。

2. 欧拉路径： - 是一种特殊的路径，它遍历图中的所有边，每条边只经过一次，但不一定回到起点。

3. 欧拉回路与欧拉路径的区别： - 欧拉回路要求起点和终点相同，而欧拉路径不要求。

欧拉回路和欧拉路径的存在条件：

欧拉回路的存在条件：
- 一个连通图存在欧拉回路，当且仅当图中每个顶点的度数都是偶数。
欧拉路径的存在条件：
- 一个连通图存在欧拉路径，当且仅当图中恰好有两个奇度数的顶点，或者每个顶点的度数都是偶数。

定理 2：欧拉路径存在的充分必要条件

定理：一个连通的多重图 $ G $ 存在欧拉路径但不存在欧拉回路，当且仅当它恰好有两个奇度数的顶点。

哈密尔顿路径与哈密尔顿回路

定义 2：哈密尔顿路径
在图 $G = <V, E>$ 中，路径 $x_0, x_1, \dots, x_{n-1}, x_n$ 称为哈密尔顿路径，若顶点集合 $V=\{x_0, x_1, \dots, x_{n-1}, x_n\}$ 且对于任意 $0 \leq i < j \leq n$，有 $x_i \neq x_j$。
也就是说，哈密尔顿路径是通过图中每个顶点且每个顶点恰好经过一次的路径。

哈密尔顿回路
哈密尔顿回路是一种特殊的哈密尔顿路径，它不仅通过每个顶点恰好一次，而且起点和终点是同一个顶点，形成一个回路。

历史背景

哈密尔顿路径得名于爱尔兰数学家威廉·罗文·哈密尔顿（Sir William Rowan Hamilton）。哈密尔顿在19世纪发明了一个称为“环游世界”的游戏，这个游戏要求从一个城市出发，沿着五十面体的边旅行，每个城市恰好访问一次，并最终返回起始城市。

哈密尔顿回路的存在性

令人惊讶的是，目前并没有已知的简单必要充分条件来判断一个图是否存在哈密尔顿回路。不过，已经知道一些充分条件。

1. 度为1的顶点无法存在哈密尔顿回路

如果图中存在一个度为1的顶点，则该图不可能有哈密尔顿回路。
这是因为度为1的顶点只能连接到另一个顶点，而哈密尔顿回路要求每个顶点都必须被访问且回路需要包含每个顶点至少两次（一次进入，一次离开）。因此，度为1的顶点不能参与哈密尔顿回路。

2. 哈密尔顿回路不能包含一个较小的回路

如果图中存在一个较小的回路，那么哈密尔顿回路不能包含该较小回路。
哈密尔顿回路要求遍历每个顶点一次，因此，回路中不能包含重复的部分。如果回路中包含一个较小的回路，那么就无法确保所有顶点只被访问一次。

哈密尔顿回路在完全图 $ K_n $ 中的构造

在完全图 $ K_n $ 中，我们可以从任何一个顶点开始构造哈密尔顿回路。

由于在 $ K_n $ 中，任意两个顶点之间都有一条边连接，因此我们可以按照任意顺序访问图中的所有顶点，并构造一个哈密尔顿回路。具体来说：

开始顶点的选择：可以从任意顶点开始，例如选择 $ v_1 $。
访问顺序：我们可以按照任意顺序访问剩余的顶点，保证每个顶点只被访问一次。
回到起点：最后，我们从最后一个访问的顶点返回到起点，形成一个回路。

由于完全图 $ K_n $ 中的每一对不同顶点都有一条边，因此我们在构造回路时不需要担心是否有边可用，所有的顶点都能通过边连接，确保可以构建一个哈密尔顿回路。

### Dirac 定理与 Ore 定理

Dirac 定理：

定理：如果 $ G $ 是一个连接图、简单图，并且 $ G $ 的顶点数 $ n $，且对任意顶点 $ v $，其度 $ (v) $，那么 $ G $ 存在哈密尔顿回路。

解释：Dirac 定理给出了一个关于图中顶点度数的充分条件，指出在满足这些条件的情况下，图 $ G $ 必然包含一个哈密尔顿回路。具体来说，若每个顶点的度数至少是图中顶点数的一半，则图一定具有哈密尔顿回路。

Ore 定理：

定理：如果 $ G $ 是一个连接图、简单图，并且 $ G $ 的顶点数 $ n $，并且对于图中每一对不相邻的顶点 $ u $ 和 $ v $，都有 $ (u) + (v) n $，那么 $ G $ 存在哈密尔顿回路。

Ore 定理提供了与 Dirac 定理类似的条件，但它更为宽松，允许某些顶点之间不直接相连，然而只要这些不相邻的顶点的度数和满足一定的条件，图就一定包含哈密尔顿回路。

Ore 定理的两个结论：

如果对于图中任意一对不相邻的顶点 $ u, v $，有 $ (u) + (v) n - 1 $，则 $ G $ 存在一条哈密尔顿路径。
如果对于图中任意一对不相邻的顶点 $ u, v $，有 $ (u) + (v) n $，则 $ G $ 是一个哈密尔顿图，意味着 $ G $ 存在哈密尔顿回路。

问题1

**在8*8黑白相同的棋盘上跳动一只马，不论跳动方向如何，要使这只马完成每一种可能的跳动恰好一次（即不产生重复的跳动），请问有可能吗？**

问题2：11个学生共进午餐

有11个学生打算在一张圆桌上共进午餐，要求每次午餐时每个学生两旁所坐的人都不同。也就是说，他们每次坐下时都要按照一种汉密尔顿回路的方式坐，并且希望每个学生的邻座在不同的天数中都不重复。

这个问题可以转化为图论中的一个问题：将每个学生看作一个图中的结点，任意两个人之间都有一条边连接。问题要求找到在无向完全图 $ K_{11} $ 中，最多能有多少条无公共边的汉密尔顿回路。

解题思路：

建模为图：
- 将11个学生分别表示为图中的11个结点。
- 由于每个学生都可以与其他任何一个学生邻座，因此图是一个无向完全图 $ K_{11} $，即图中任意两个结点之间都有一条边。
求无公共边的汉密尔顿回路：
- 每次学生们的座位排列可以看作一个汉密尔顿回路。每条汉密尔顿回路沿桌而坐，保证每个学生两旁坐的人不同。
- 为了使两次午餐时邻座不重复，我们要求每次选择的汉密尔顿回路之间没有公共边。
汉密尔顿回路的数量：
- 在无向完全图 $ K_n $ 中，若要求找到无公共边的汉密尔顿回路，可以通过计算这个图中不共享任何边的回路数来解决。
- 对于 $ K_{11} $，通过图论中的结果可知，图中无公共边的汉密尔顿回路数量为 $ $ 条，即 $ = 5 $ 条。
最终解答：
- 这意味着这11个学生最多可以在5天内按照不同的座位安排共进午餐，每天的座位安排都是不同的，并且每个学生两旁的邻座都不同。

最短路径问题

迪杰斯特拉算法的定理

定理 1：
迪杰斯特拉算法可以在一个连通的简单无向加权图中，找到两个顶点之间的最短路径的长度。

定理 2：
迪杰斯特拉算法在一个有 $ n $ 个顶点的连通简单无向加权图中，计算两个顶点之间最短路径的长度时，使用的操作数为 $ O(n^2) $（包括加法和比较操作）。

旅行推销员问题 (TSP)

问题描述：
旅行推销员问题（TSP）是指一个旅行推销员需要访问 $ n $ 个城市，每个城市只访问一次，并且最终返回到起始城市。
旅行推销员问题的目标是找出访问这些城市的顺序，使得总的旅行距离最小。

对于一个 $ n $ 个城市的TSP问题，可能的哈密尔顿回路数量为：
$ $ 其中，$ (n-1)! $ 表示所有的排列，而除以 2 是因为回路是无向的，顺序和反向都被视为同一回路。

例如：
对于一个有 25 个城市的 TSP 问题，该问题将有 25 个顶点，且需要检查的哈密尔顿回路数量为：
$ $ 如果每检查一个哈密尔顿回路花费 1 纳秒（$ 10^{-9} $ 秒），那么检查所有可能的哈密尔顿回路所需的时间将大约为一千万年。

计算复杂度：

由于TSP是一个组合优化问题，暴力破解方法需要检查所有可能的排列。对于较大规模的问题，如25个城市，所需的计算时间极其庞大。因此，这个问题的计算复杂度非常高，甚至对于计算机来说也几乎不可能在合理的时间内解决。

算法与挑战：

尽管旅行推销员问题在实践和理论上都具有重要意义，许多高效的算法已经被提出用于求解此问题。然而，迄今为止，没有已知的具有多项式最坏情况时间复杂度的算法可以解决这个问题。

重要性：

如果发现了一种具有多项式最坏情况时间复杂度的TSP求解算法，那么许多其他难解问题也将得到解决，因为TSP被认为是一个NP-hard问题，解决它将影响许多类似的组合优化问题。

平面图的定义

平面图：
一个图被称为平面图，如果它可以在平面中绘制，且在绘制过程中没有任何边相交。这里，边的交叉是指图中的边在表示它们的线或弧相交的地方，且这个交点不是边的共同端点。

平面表示：
这样的绘制称为图的平面表示。

在任何 $ K(3,3) $ 的平面表示中，顶点 $ v_1 $ 和 $ v_2 $ 必须同时与顶点 $ v_4 $ 和 $ v_5 $ 相连。

平面图的欧拉公式与相关定理

平面图表示
平面图的表示将平面分割成多个区域，包括一个无界区域。欧拉定理表明，所有平面图的表示将平面分割成相同数量的区域。
定理 1
设 $ G $ 是一个连接的平面简单图，$ e $ 是边数，$ v $ 是顶点数，$ r $ 是平面表示中的区域数。根据欧拉定理，
$ r = e - v + 2 $
例题
设 $ G $ 是一个连接的平面简单图，顶点数 $ v = 20 $，每个顶点的度数为 3。求该图的平面表示分割平面的区域数。
该图有 15 个顶点，每个顶点的度数为 4，因此 $ v = 15 $，
因为 $ 2e = 15 = 60 $，所以 $ e = 30 $。根据定理 1，$ r = e - v + 2 = 30 - 15 + 2 = 17 $
推论 1
如果 $ G $ 是一个连接的平面简单图，且 $ v $，则边数 $ e $ 满足
$ e 3v - 6 $
推论 2
如果 $ G $ 是一个连接的平面简单图，则 $ G $ 必有一个度数不超过 5 的顶点。
推论 3
如果 $ G $ 是一个连接的平面简单图，且 $ v $，并且没有长度为 3 的回路，则边数 $ e $ 满足
$ e 2v - 4 $

证明 $ K_5 $ 不是平面图

解答过程：

图 $ K_5 $ 的基本信息：
- $ K_5 $ 是一个完全图，包含 5 个顶点，每个顶点与其它所有顶点相连，因此边数为 10。
- 所以 $ v = 5 $ 和 $ e = 10 $。
应用推论 1： 根据推论 1，如果 $ G $ 是一个连接的平面简单图且 $ v $，则边数 $ e $ 必须满足
$ e 3v - 6 $

对于 $ K_5 $，我们代入 $ v = 5 $，得到$ 3v - 6 = 3 - 6 = 9 $ 也就是说，对于平面图来说，最大允许的边数是 9。
验证是否满足条件： 然而，$ K_5 $ 的边数是 10，这显然大于 9，因此不满足
$ e 3v - 6 $
结论： 由于 $ K_5 $ 不满足平面图的边数条件，因此 $ K_5 $ 不是平面图。

平面图和同胚图

定义：

平面图：
如果一个图是平面的，意味着它可以嵌入到平面中，没有边的交叉。
初等细分（Elementary Subdivision）：
如果一个图是平面图，可以通过移除一条边 $\{u, v\}$ 并添加一个新顶点 $w$，使得新的图包含边 $\{u, w\}$ 和 $\{w, v\}$。这个操作叫做初等细分。

这个操作的意义在于，图的结构并没有发生实质性的变化，只是将原来的边替换成了由新顶点 $w$ 连接的两条边。
同胚图（Homeomorphic Graphs）：
两个图 $G_1 = (V_1, E_1)$ 和 $G_2 = (V_2, E_2)$ 被称为同胚图，如果它们能够通过一系列初等细分从同一个图获得。

换句话说，两个图如果在经过若干次初等细分操作后变得相同，那么它们就是同胚图。每一次初等细分操作实际上是在将一条边分成两条边并引入一个新的顶点。

例子：

图 $G_1$ 和 图 $G_2$ 是同胚图的条件是，能通过相同的初等细分过程将一个图变为另一个图。这意味着它们的结构本质上是一样的，只是通过顶点和边的重新配置形成了不同的表示。

非平面图的判定

定理：
一个图是非平面图，当且仅当它包含一个同胚于 $ K_{3,3} $ 或 $ K_5 $ 的子图。

解释：

同胚子图：
如果一个图包含一个同胚于 $ K_{3,3} $ 或 $ K_5 $ 的子图，意味着它通过初等细分（即将边拆分并引入新顶点的操作）能够转换为 $ K_{3,3} $ 或 $ K_5 $ 的结构。
$ K_{3,3} $ 和 $ K_5 $：** - **$ K_{3,3} $**：这是一个完全二分图，包含两个顶点集，每个集有3个顶点，每个顶点与另一个集中的所有顶点相连。 - **$ K_5 $：这是一个包含5个顶点的完全图，每个顶点与其他4个顶点相连。
非平面图的判定：
如果一个图中包含一个同胚于 $ K_{3,3} $ 或 $ K_5 $ 的子图，那么这个图一定是非平面图。这是因为，$ K_{3,3} $ 和 $ K_5 $ 都是不可嵌入平面图中的，它们不能在没有交叉的情况下被绘制在平面上。

图的着色问题：四色定理

问题描述：
在地图着色问题中，要求为一个地图的各个区域着色，使得相邻的区域颜色不同。虽然可以使用不同的颜色为每个区域着色，但这样做可能会导致颜色相似区域之间的区分困难。因此，我们的目标是使用尽可能少的颜色，以确保相邻区域的颜色不同。

最小颜色数：
这个问题的关键是确定给定地图中至少需要多少种颜色，以保证相邻区域永远不会有相同的颜色。

四色定理：
根据 四色定理，任何地图都可以使用至多 四种颜色 来进行着色，且相邻区域的颜色不同。

定理内容：
四色定理声明：在平面上，任何地图的区域都可以通过不超过四种颜色来着色，使得相邻的区域颜色不同。

解释：

地图的着色：
地图由多个区域组成，区域之间通过共享边界相邻。我们需要为每个区域分配颜色，且相邻的区域颜色不能相同。
四色定理的意义：
该定理告诉我们，尽管地图上有许多区域，只需要四种颜色即可保证相邻区域的颜色不同。这个定理已经得到了严格的数学证明，且可以应用于任何形式的地图，不论其复杂度如何。

地图的图论表示与对偶图

地图与图的关系：
每个地图都可以通过图论来表示。具体来说，地图上的每个区域都对应图中的一个顶点，而如果两个区域有共同的边界，它们之间就通过一条边连接。如果两个区域只通过一个点相接触，那么它们不会被认为是相邻的。

对偶图：
在这种图的表示下，可以定义一个与原图相关的对偶图。对偶图的构造方法如下：

顶点对应关系：
对偶图中的每个顶点对应于原地图中的一个区域。也就是说，原图中的每个区域在对偶图中都有一个顶点。
边的连接：
如果原地图中的两个区域有共同的边界，那么在对偶图中，这两个区域对应的顶点之间就有一条边连接。即原图中两个区域之间存在边界，表示它们在对偶图中的顶点之间存在边。

对偶图的性质：

对偶图通常也是平面图，即它可以在平面上绘制，而不会有任何边的交叉。
对偶图与原图之间有着紧密的关系。在原图上，每条边代表原地图中的两个相邻区域；在对偶图中，每条边代表原图中相邻区域之间的连接。

对偶图的应用：

对偶图的概念在地理学和图论中有广泛应用，尤其是在地图着色、网络分析和空间优化等领域。
例如，通过构建对偶图，能够更容易地理解地图上区域之间的关系，甚至用于计算区域的连通性和可达性。

圆圈图的着色问题

定义：
给定一个圆圈图 $ C_n $，其中 $ n $ 表示图中的顶点数。如果两个顶点之间有边相连，则这两个顶点是相邻的。

圆圈图 $ C_n $ 的着色规则：

当 $ n $ 为偶数时：
- 需要两种颜色来着色 $ C_n $。
- 可以将第 $ n $ 个顶点涂成蓝色，而与之相邻的顶点（即第 $ n-1 $ 个顶点和第 1 个顶点）则涂成红色。
- 由于相邻的顶点必须使用不同的颜色，所以当 $ n $ 是偶数时，只需要两种颜色即可完成着色。
当 $ n $ 为奇数且 $ n > 1 $ 时：
- 需要三种颜色来着色 $ C_n $。
- 证明的思路是：假设我们从一个初始顶点开始着色。如果只使用两种颜色，则在顺时针方向上交替着色。然而，因为顶点数是奇数，最后一个顶点和第一个顶点会相邻，且它们应该是不同颜色，但由于交替着色，最终顶点无法满足这个条件。因此，至少需要三种颜色才能保证所有相邻的顶点使用不同的颜色。

结论：

偶数顶点数 $ C_n $ 图的色数是 2，即仅需要两种颜色来完成着色。
奇数顶点数 $ C_n $ 图的色数是 3，需要三种颜色来完成着色，确保相邻的顶点有不同的颜色。

性质	强连通图	弱连通图
路径的方向要求	必须有从 \(a \to b\) 和 \(b \to a\) 的路径	忽略方向后，顶点之间有路径即可
图的连通性条件	更严格	较宽松
强弱关系	强连通图必定是弱连通图	弱连通图不一定是强连通图