algorithm - 图连通性证明

Question

假设我们有一个表示 n 节点图的邻接矩阵 G。所以 G[i, j] 如果存在从 i 到 j 的边则为 1，否则为 0。我们可以将每个条目视为一张翻过来的纸条，上面有 1 或 0。

我的文字声称我们需要查询矩阵以确定图形是否连通的次数的下限是 n * (n-1)/2。我对这个证明有点困惑。

证明:这是对手的策略:当算法要求我们翻转一张纸条时，我们返回 0，除非这会强制断开图形。

1) 这似乎暗示在某些情况下，如果我们返回一个 0，我们以后不可能添加边，从而导致一条从 u 到 v 的路径。但肯定图仍然可以连接即使我们在上面返回 0...对吧？

声明:我们保持不变，即对于 y 个未询问的对 (u, v)，到目前为止显示的图没有从 u 到 v 的路径

证明:假设有一条从 u 到 v 的路径。然后我们可以删除该路径上显示的最后一条边 (u', v')。我们可以为此回答 0 并通过具有边 (u, v) 在图中保持相同的连通性。这与我们的对手策略的定义相矛盾。

证明结束:假设有一个算法在没有检查每张纸条的情况下完成。考虑一些未被询问的对 (u, v)。如果算法声称图是连通的，我们会为剩余的未询问边显示全零这意味着没有从 u 到 v 的路径，所以算法是错误的。

<强>2。有人可以解释斜体吗？我没有看到连接...

另一方面，如果算法说断开连接，我们会为剩余边显示全 1，并且根据我们对手策略的定义，算法是错误的。

<强>3。即使我们显示所有的图形是否仍然断开连接？

谢谢!

Answer 1

1. 假设我们有一个四节点图。如果算法已经查询并得到了 13 和 14 的“0”答案，然后它询问了 12，那么如果答案是“0”，则意味着该图无法连接，因为 1 没有连接到 2(有没有直接路径，并且 1 没有其他可能的连接)。

2. 在任何给定时间，您都可以将边缘视为"is"、“可能”或“否”。最初所有边都是“可能”。每当算法询问边缘时，它都会变成"is"或“否”。带有 yes 和 maybe 边的图是与观察结果一致的连接最紧密的输入。仅具有 yes 边的图是与观察结果一致的连接最少的输入。只有当这些图具有相同的连接状态时，算法才能返回。