图和图模型

---

前一部分介绍了推理、证明和解决问题的不同工具。在这一部分中，我们将研究离散结构，这些结构构成了制定许多现实生活问题的基础。

我们将介绍的两种离散结构是图和树。图是一组称为节点或顶点的点，它们通过一组称为边的线互连。图或图论的研究是数学、工程和计算机科学领域许多学科的重要组成部分。

什么是图表？

定义- 图（表示为 $G = (V, E)$）由一组非空顶点或节点 V 和一组边 E 组成。

示例- 让我们考虑，图是 $G = (V, E)$ 其中 $V = \lbrace a, b, c, d \rbrace $ 和 $E = \lbrace \lbrace a, b \rbrace, \lbrace a、c \rbrace、\lbrace b、c \rbrace、\lbrace c、d \rbrace \rbrace$

顶点的度数- 图 G 的顶点 V 的度数（用 deg (V) 表示）是与顶点 V 关联的边的数量。

偶数和奇数顶点- 如果顶点的度为偶数，则该顶点称为偶顶点，如果顶点的度为奇数，则该顶点称为奇顶点。

图的度- 图的度是该图的最大顶点度。对于上图，该图的阶数为 3。

握手引理- 在图中，所有顶点的所有度数之和等于边数的两倍。

图表类型

有不同类型的图表，我们将在下一节中学习。

空图

空图没有边。$n$ 个顶点的空图用 $N_n$ 表示

简单图

如果图是无向的并且不包含任何环或多边，则该图被称为简单图/严格图。

多图

如果在图中允许同一组顶点之间存在多条边，则称为多重图。换句话说，它是具有至少一个环或多条边的图。

有向图和无向图

如果图 $G = (V, E)$ 的边集由有序的顶点对组成，则称为有向图；如果边集由无序的顶点对组成，则称为无向图。

连接图和断开图

如果图的任意两个顶点通过路径连接，则该图是连通的；如果图的至少两个顶点没有通过路径连接，则图是断开的。如果图 G 是断开的，则 $G$ 的每个最大连通子图称为图 $G$ 的连通分量。

正则图

如果图的所有顶点具有相同的度数，则该图是正则图。在度为 $r$ 的正则图 G 中，$G$ 每个顶点的度为 r。

完整图

如果每两个顶点对恰好由一条边连接，则图称为完全图。具有 n 个顶点的完整图用 $K_n$ 表示

循环图

如果一个图由单个循环组成，则称为循环图。有 n 个顶点的循环图用 $C_n$ 表示

二分图

如果图 G 的顶点集可以分为两个不相交的集 $V_1$ 和 $V_2$，这样图中的每条边都将 $V_1$ 中的顶点连接到 $V_2$ 中的顶点，且 G 中不存在连接 $V_1$ 中的两个顶点或 $V_2$ 中的两个顶点的边，则图 $G$ 称为二分图。

完全二分图

完全二分图是其中第一组中的每个顶点都连接到第二组中的每个单个顶点的二分图。完整的二部图由 $K_{x,y}$ 表示，其中图 $G$ 包含第一组中的 $x$ 顶点和第二组中的 $y$ 顶点。

图的表示

主要有两种表示图的方法 -

• 邻接矩阵
• 邻接表

邻接矩阵

邻接矩阵 $A[V][V]$ 是大小为 $V \times V$ 的二维数组，其中 $V$ 是无向图中的顶点数。如果$V_x$ 到$V_y$ 之间存在边，则$A[V_x][V_y]=1$ 和$A[V_y][V_x]=1$ 的值，否则该值为零。而对于有向图，如果$V_x$到$V_y$之间有边，那么$A[V_x][V_y]=1$，否则该值为零。

无向图的邻接矩阵

让我们考虑以下无向图并构造邻接矩阵 -

上述无向图的邻接矩阵为 -

有向图的邻接矩阵

让我们考虑以下有向图并构造其邻接矩阵 -

上述有向图的邻接矩阵为 -

邻接表

在邻接表中，链表数组$(A[V])$用于表示具有$V$个顶点的图G。条目$A[V_x]$表示与第$Vx-th​​$顶点相邻的顶点的链表。无向图的邻接表如下图所示 -

平面图与非平面图

平面图- 如果图 $G$ 可以在没有任何边交叉的平面上绘制，则该图称为平面图。如果我们在平面上绘制图且没有边交叉，则称为将图嵌入平面中。

非平面图- 如果图不能在没有图边交叉的平面上绘制，则该图是非平面的。

同构

如果两个图 G 和 H 包含相同数量的以相同方式连接的顶点，则它们称为同构图（记为 $G \cong H$）。

检查非同构比检查同构更容易。如果发生以下任何条件，则两个图是非同构的 -

• 连接的组件数量不同
• 顶点集基数不同
• 边集基数不同
• 度数顺序不同

例子

下面的图是同构的 -

同态

从图 $G$ 到图 $H$ 的同态是一个映射（可​​能不是双射映射）$ h: G \rightarrow H$ 使得 - $(x, y) \in E(G) \rightarrow (h(x), h(y)) \in E(H)$。它将图 $G$ 的相邻顶点映射到图 $H$ 的相邻顶点。

同态的性质

• 如果同态是双射映射，那么它就是同构。

• 同态总是保留图的边和连通性。

• 同态的组合也是同态。

• 找出另一个图是否存在同态图是一个NP完全问题。

欧拉图

如果存在一条包含图 $G$ 的每条边的闭合路径，则连通图 $G$ 称为欧拉图。欧拉路径是只使用图的每条边一次的路径。欧拉路径在不同的顶点开始和结束。

欧拉电路是一种仅使用图的每条边一次的电路。欧拉回路总是在同一顶点开始和结束。连通图 $G$ 是欧拉图当且仅当 $G$ 的所有顶点都是偶数时，连通图 $G$ 是欧拉图当且仅当其边集可以分解为环。

上图是欧拉图 $“a\: 1\: b\: 2\: c\: 3\: d\: 4\: e\: 5\: c\: 6\: f\: 7 \: g”$ 覆盖了图的所有边。

哈密​​顿图

连通图 $G$ 称为哈密顿图，如果存在包含 $G$ 的每个顶点的环，并且该环称为哈密顿环。图 $G$ 中的哈密顿步行是仅通过每个顶点一次的步行。

如果 $G$ 是一个有 n 个顶点的简单图，其中 $n \geq 3$ 如果每个顶点 $v$ 为 $deg(v) \geq \frac{n}{2}$，则图 $G$ 为哈密​​顿图。这就是所谓的狄拉克定理。

如果 $G$ 是一个具有 $n$ 个顶点的简单图，其中 $n \geq 2$ 如果对于每对不相邻的顶点 x 和 y 为 $deg(x) + deg(y) \geq n$，则图 $G$ 是哈密顿图。这就是所谓的奥雷定理。