子图、图运算、路与连通性

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Mar.8 2022

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

目录

有特定需要的内容直接跳转到相关章节查看即可。

正在加载目录...

子图

    如果 `V(H) \subseteq V(G)`, `E(H) \subseteq E(G)`, 且 `H` 中边的重数不超过 `G` 中对应边的条数，则称 `H` 为 `G` 的 子图 (Subgraph)，记为 `H \subseteq G`。

    如果 `H \subseteq G` 且 `H \ne G`，则称 `H` 为 `G` 的 真子图 (Proper Subgraph)，记为 `H \subset G`。

导出子图

点导出子图

    如果 `V' \subseteq V(G)`，则以 `V'` 为顶点集，以两个端点均在 `V'` 中的边集组成的子图，称为图 `G` 的 点导出子图 (Induced Subgraph)，记为 `G[V']`。

    事实上，`G[V'] = G - \bar{V'}`。

边导出子图

    如果 `E' \subseteq E(G)`，则以 `E'` 为边集，以 `E'` 中边的所有端点为顶点集组成的图, 称为图 `G` 的 边导出子图 (edge-induced subgraph)，记为 `G[E']`。

生成子图

    如果图 `G` 的一个子图包含 `G` 的所有顶点, 称该子图为 `G` 的一个 生成子图(Spanning Subgraph)，有时候也称 支撑子图。

简单图 `G=(n,m)` 的所有生成子图个数为 `2^m`

图运算

删点运算

    删点运算: 设 `V' \subseteq V(G)`, 在 `G` 中删去 `V'` 中的顶点和 `G` 中与之关联的所有边的操作，记为 `G-V'`。

删边运算

    删边运算: 设 `E' \subseteq E(G)`, 在 `G` 中删去 `E'` 中的所有边的操作，记为 `G-E'`。

    删点、删边后得到的图均是原图的子图。

并运算

    并运算: 设 `G_1`, `G_2` 是 `G` 的两个子图, `G_1` 与 `G_2` 并是指以 `V(G_1) \cup V(G_2)` 为顶点集, 以 `E(G_1) \cup E(G_2)` 为边集组成的子图，记为: `G_1 \cup G_2`。特别地, 如果 `G_1`, `G_2` 不相交(没有公共顶点), 称它们的并为 不交并, 可以记为 `G_1+G_2`。

交运算

    交运算: 设 `G_1`, `G_2` 是 `G` 的两个子图, `G_1` 与 `G_2` 交是指以 `V(G_1) \cap V(G_2)` 为顶点集, 以 `E(G_1) \cap E(G_2)` 为边集组成的子图，记为: `G_1 \cap G_2`。

差运算

    差运算: 设 `G_1`, `G_2` 是两个图, `G_1` 与 `G_2` 的差是指从 `G_1` 中删去 `G_2` 中的边得到的新图，记为 `G_1−G_2`。

对称差运算

    对称差运算/异或: 设 `G_1`, `G_2` 是两个图, `G_1` 与 `G_2` 的对称差定义为 `G_1\DeltaG_2 = (G_1 \cup G_2) - (G_1 \cap G_2)`。简单来说，`G_1\DeltaG_2` 仅包含那些恰好在 `G_1` 或 `G_2` 出现一次的边, 而不包含在 `G_1` 和 `G_2` 中都出现的边。

联运算

    联运算: 设 `G_1`, `G_2` 是两个不相交的图，作 `G_1+G_2` (i.e. 不交并)，并且将 `G_1` 中每个顶点和 `G_2` 中的每个顶点连接，这样得到的新图称为 `G_1` 与 `G_2` 的联图。记为 `G_1\veeG_2`。

Cartesian 积图

    Cartesian 积图: 记图 `G_1`, `G_2` 的Cartesian 积 为 `G=G_1 □ G_2`。首先我们设顶点集 `V=V_1 \times V_2 = {(v_1, v_2)|v_1\inV_1, v_2\inV_2}`，它是一个二元有序组，且 `|V|=|V_1| \cdot |V_2|`。设点 `v=(v_1,v_2)`, `u=(u_1,u_2)` 是 `G=G_1 □ G_2` 的两个点，`u` 和 `v` 当且仅当满足以下条件之一时，它们在 `G` 中相邻:

• `u_1 = v_1` 且 `u_2 \leftrightarrow v_2`
• `u_2 = v_2` 且 `u_1 \leftrightarrow v_1`

    Cartesian 积图满足交换律: `G_1 □ G_2 \cong G_2 □ G_1`。

    Cartesian 积图是构造新图的重要方法，其对原图的性质进行了很好的保持: 若 `G_1`, `G_2` 正则/二部/点传递/欧拉/哈密尔顿/k-连通，则 `G_1 □ G_2` 亦然。

图的合成/字典积

    图的 合成 (composition) 或者 字典积: 记为 `G_1[G_2]`。这种图相当于松弛了 Cartesian 积图的条件。设点 `v=(v_1,v_2)`, `u=(u_1,u_2)` 是 `G=G_1[G_2]` 的两个点，`u` 和 `v` 当且仅当满足以下条件之一时，它们在 `G` 中相邻:

• `u_1 \leftrightarrow v_1`
• `u_1 = v_1` 且 `u_2 \leftrightarrow v_2`

    图的合成不满足交换律。

    值得区分导出子图 `G[V’]`, 边导出子图 `G[E’]`, 合成图 `G1[G2]` 记号的区别。

张量积

    张量积 (tensor product): 设 `G_1=(V_1,E_1)`, `G_2=(V_2,E_2)` 是两个图. 对点集 `V=V_1\timesV_2` 的任意两个点 `u=(u_1,u_2)`, `v=(v_1,v_2)`，当 `u_1 \leftrightarrow v_1` 且 `u_2 \leftrightarrow v_2` 时，把 `u` 和 `v` 相连，如此得到的新图称为 `G_1` 与 `G_2` 的张量积图，记为 `G_1 \times G_2`。

超立方体

    图的积运算是网络构造的常用方法. 并行计算机中的网络拓扑常采用所谓的 超立方体 (Hypercube/n-cube) 结构. 采用该结构可使网络具有较好的可靠性、较小的通信延迟和很好的可扩展性以及便于并行编程等优点。

    超立方体可以使用以下积图来递归构造:

• 1 方体定义为 `Q_1 = K_2`
• n 方体定义为 `Q_n = K_2 □ Q_{n-1}`

    在上述的超立方体的递归构造方法中，我们计算的方法卡式乘积乘以 `k_2`，在作图上反映出来就是: 把原图复制一份，然后把对应的点连接起来。如上图所示。

    我们还可以有超立方体的另一种更直观的构造方法。由超立方体的定义可知: `V(Q_n)=2^n`，因此我们可以个超立方体 `Q_n` 的各个顶点表上长度为 `n` 的二进制码。由 `n−1` 方体 `Q_(n−1)` 构造 `Q_n` 的方法是: 将 `Q_(n−1)` 拷贝一个，将原 `Q_(n−1)` 每个顶点的码前再添加一个 0，将拷贝得来的 n−1 方体每个顶点的码前面再添加一个 1，然后在两个 n−1 方体之间连线: 当且仅当两个顶点码只有一位对应位数字不同时，该两点连线，如此得到的图即为 n 方体。