离散数学 - 有关图的更多信息
图形着色
图着色是为图 G 的每个顶点分配颜色的过程，使得相邻顶点没有相同的颜色。目标是在给图表着色时尽量减少颜色的数量。为图 G 着色所需的最小颜色数称为该图的色数。图着色问题是一个NP完全问题。
给图表着色的方法
为具有 n 个顶点的图 G 着色所需的步骤如下 -
步骤 1 - 按某种顺序排列图的顶点。
步骤 2 - 选择第一个顶点并用第一种颜色为其着色。
步骤 3 - 选择下一个顶点，并使用未在与其相邻的任何顶点上着色的最低编号颜色对其进行着色。如果所有相邻顶点都用该颜色着色，则为其指定新颜色。重复此步骤，直到所有顶点都着色。
例子
在上图中，首先顶点 $a$ 被涂成红色。由于顶点 a 的相邻顶点再次相邻，因此顶点 $b$ 和顶点 $d$ 分别被涂上不同的颜色，绿色和蓝色。然后顶点 $c$ 被着色为红色，因为 $c$ 没有相邻顶点被着色为红色。因此，我们可以用 3 种颜色为图表着色。因此，该图的色数为3。
图形着色的应用
图形着色的一些应用包括 -
图遍历
图遍历是按照某种系统顺序访问图的所有顶点的问题。遍历图主要有两种方法。
- 广度优先搜索
- 深度优先搜索
广度优先搜索
广度优先搜索 (BFS) 从图 $G$ 的起始 0 级顶点 $X$ 开始。然后我们访问 $X$ 的邻居的所有顶点。访问后，我们将顶点标记为“已访问”，并将它们放入 level-1。然后我们从 1 级顶点开始，对每个 1 级顶点应用相同的方法，依此类推。当图的每个顶点都被访问过时，BFS 遍历终止。
广度优先搜索算法
这个概念是在访问邻居顶点的其他邻居顶点之前访问所有邻居顶点。
将所有节点的状态初始化为“Ready”。
将源顶点放入队列并将其状态更改为“等待”。
重复以下两个步骤，直到队列为空 -
从队列中删除第一个顶点并将其标记为“已访问”。
将已删除顶点的状态为“就绪”的所有邻居添加到队列的末尾。将他们的状态标记为“等待”。
问题
让我们拿一个图（源顶点是“a”）并应用 BFS 算法来找出遍历顺序。
解决方案-
将所有顶点的状态初始化为“Ready”。
将其放入队列并将其状态更改为“等待”。
从队列中删除一个，将其标记为“已访问”。
将a处于“就绪”状态的邻居b、d和e添加到队列末尾，并将它们标记为“等待”。
从队列中删除b，将其标记为“已访问”，将其“就绪”邻居c放在队列末尾，并将c标记为“等待”。
从队列中删除d并将其标记为“已访问”。它没有处于“就绪”状态的邻居。
从队列中删除e并将其标记为“已访问”。它没有处于“就绪”状态的邻居。
从队列中删除c并将其标记为“已访问”。它没有处于“就绪”状态的邻居。
队列已空，所以停止。
所以遍历顺序是 -
$a \右箭头 b \右箭头 d \右箭头 e \右箭头 c$
交替的遍历顺序是 -
$a \rightarrow b \rightarrow e \rightarrow d \rightarrow c$
或者，$a \rightarrow d \rightarrow b \rightarrow e \rightarrow c$
或者，$a \rightarrow e \rightarrow b \rightarrow d \rightarrow c$
或者，$a \rightarrow b \rightarrow e \rightarrow d \rightarrow c$
或者，$a \rightarrow d \rightarrow e \rightarrow b \rightarrow c$
广度优先搜索的应用
- 寻找最短路径
- 未加权图的最小生成树
- GPS导航系统
- 检测无向图中的循环
- 查找一个连接组件内的所有节点
复杂性分析
令 $G(V, E)$ 为具有 $|V|$ 个顶点和 $|E|$ 个边的图。如果广度优先搜索算法访问图中的每个顶点并检查每个边，那么它的时间复杂度将是 -
$$O( | V | + | E | )。O( | E | )$$
它可能在 $O(1)$ 和 $O(|V2|)$ 之间变化
深度优先搜索
深度优先搜索 (DFS) 算法从顶点 $v$ 开始，然后遍历到之前未访问过的相邻顶点（例如 x）并标记为“已访问”，然后继续搜索 $x$ 的相邻顶点，很快。
如果在任意顶点处，遇到所有相邻顶点都被访问过，则回溯，直到找到具有之前未遍历过的相邻顶点的第一个顶点。然后，它遍历该顶点，继续遍历其相邻顶点，直到遍历所有访问过的顶点并且必须再次回溯。这样就会遍历从初始顶点$v$开始可达的所有顶点。
深度优先搜索算法
这个概念是在访问其他邻居顶点之前先访问邻居顶点的所有邻居顶点。
初始化所有节点状态为“Ready”
将源顶点放入堆栈并将其状态更改为“等待”
重复以下两个步骤，直到堆栈为空 -
从堆栈中弹出顶部顶点并将其标记为“已访问”
将已删除顶点的状态为“就绪”的所有邻居推入堆栈顶部。将他们的状态标记为“等待”。
问题
让我们拿一个图（源顶点是“a”）并应用 DFS 算法来找出遍历顺序。
解决方案
将所有顶点的状态初始化为“Ready”。
将a压入堆栈并将其状态更改为“等待”。
弹出a并将其标记为“已访问”。
将a处于“就绪”状态的邻居e、d和b推入堆栈顶部，并将它们标记为“等待”。
从堆栈中弹出b ，将其标记为“已访问”，将其“就绪”邻居c压入堆栈。
从堆栈中弹出c并将其标记为“已访问”。它没有“就绪”邻居。
从堆栈中弹出d并将其标记为“已访问”。它没有“就绪”邻居。
从堆栈中弹出e并将其标记为“已访问”。它没有“就绪”邻居。
堆栈为空。所以停止。
所以遍历顺序是 -
$a \右箭头 b \右箭头 c \右箭头 d \右箭头 e$
交替的遍历顺序是 -
$a \rightarrow e \rightarrow b \rightarrow c \rightarrow d$
或者，$a \rightarrow b \rightarrow e \rightarrow c \rightarrow d$
或者，$a \rightarrow d \rightarrow e \rightarrow b \rightarrow c$
或者，$a \rightarrow d \rightarrow c \rightarrow e \rightarrow b$
或者，$a \rightarrow d \rightarrow c \rightarrow b \rightarrow e$
复杂性分析
令 $G(V, E)$ 为具有 $|V|$ 个顶点和 $|E|$ 个边的图。如果 DFS 算法访问图中的每个顶点并检查每条边，则时间复杂度为 -
$$\circleddash ( | V | + | E | )$$
应用领域
- 检测图中的循环
- 寻找拓扑排序
- 测试图是否是二分图
- 寻找连接的组件
- 寻找图表的桥梁
- 寻找图中的双连通性
- 解决骑士之旅问题
- 仅用一种解决方案解决难题