K-connectivity 反射的、对称的、传递的

Question

我要证明以下几点：

在有向图中，如果从向量 x 到 y 有 k 条不同的路径（不使用相同的边）并且从向量 y 也有 k 条不同的路径（不使用相同的边）对x 我们这样表示它：x ≡ y 我们称它们为 k-连通向量。

我要证明这个关系是反射的、对称的和传递的。

另外，如果路径使用不同的向量和边在一起，会有什么变化吗？

Answer 1

• Reflexive 属性:

  如果您考虑 k 包含节点 x 的不同（不使用相同边）循环的数量，那么对于每个 x，我们有一些 k 满足 x ≡ x。

• Symmetric 属性:

  (x ≡ y) 表示：

  （从x到y有k条不同的路径。）和（从y到x有k条不同的路径。）

  (y ≡ x) 表示：

  （从y到x有k条不同的路径。）和（从x到y有k条不同的路径。）

  所以由于Logical Conjuction的对称性，(x ≡ y) 意味着 (y ≡ x) 反之亦然。

• Transitive 属性:

  假设我们有 (x ≡ y) 和 (y ≡ x)

  第一个暗示（从 x 到 y 有 k 条不同的路径；我们以任意顺序将它们命名为 a_1 到 a_k） 和 （k 个不同的路径来自 y 到 x；我们将它们命名为 a'_1 到 a'_k).

  第二个意味着（从y到z有k条不同的路径；我们以任意顺序将它们命名为 b_1 到 b_k） 和 （k 个不同的路径 z 到 y；我们将它们命名为 b'_1 到 b'_k).

  我们可以通过连接 a_1 和 b_1 构造 c_1 因为 a_1 结束于 y 和 b_1 从 y 开始。所以 c_1 是从 x 到 z 的路径。这样我们也可以构建 c_2 到 c_k。对于任何 i 和 j，c_i 和 c_j 没有相同的边，因为它们的部分 (a_i and a_j and b_i and b_j) 不共享相同的边缘。所以从 x 到 z.

  有 k 个不同的路径

  我们可以用同样的方法从 a'_1 到 a'_k 和 b'_1 到 b'_k 构造 c'_1 到 c'_k。所以有 k 从 z 到 x.

  的不同路径

  所以我们可以暗示 (x ≡ z).

如果路径也不共享向量，则证明成立。因为这意味着，它们不共享边，这是此证明的假设。