证明使用邻接矩阵进行二部测试具有 Ω(n^2)
Proof that using adjacency matrix for bipartite testing has Ω(n^2)
所以在我的一次讲座中，我遇到了以下证明：
: 判断一个图是否是二分图的算法
它的输入是一个无向图 = (, ) 表示
作为 × 邻接矩阵，具有 Ω(^2)
的 运行 时间
我们假设一个算法 ALG 测试二分性（returns 真或假）。我们还假设我们有一个图 0 = (, 0) = {1,2, … , } 和 0 = { 1, : 2 ≤ ≤ }（因为这是一颗星，所以它是一个二分图）
在证明中有一个步骤说：
“对于给定的算法 ALG，我们将构造另一个图 1 st：如果 ALG 对 0 的邻接矩阵执行少于 (−1)C2 次访问，
那么 ALG 就不会区分 0 和 1，1 不是二分的。"
我的问题是 (n-1)C2 访问是什么意思。它是说，例如，如果我们有一个不同的 V = {A,B,C,D} 那么 ALG 将查看所有节点对，除了 D 和其他节点之间的节点对？
抱歉，如果不清楚，这个证明真的让我很困惑。
G0 是一个 n 顶点 star graph。它是二分的，但如果您向它添加任何其他边，则生成的图形就不是。有 n−1 选择 2 = (n−1)(n−2)/2 = Ω(n2) 其他我们可以添加的边。每个正确的算法都必须检查每个算法，以验证 G0 是二分的。
所以在我的一次讲座中，我遇到了以下证明：
: 判断一个图是否是二分图的算法 它的输入是一个无向图 = (, ) 表示 作为 × 邻接矩阵，具有 Ω(^2)
的 运行 时间我们假设一个算法 ALG 测试二分性（returns 真或假）。我们还假设我们有一个图 0 = (, 0) = {1,2, … , } 和 0 = { 1, : 2 ≤ ≤ }（因为这是一颗星，所以它是一个二分图）
在证明中有一个步骤说： “对于给定的算法 ALG，我们将构造另一个图 1 st：如果 ALG 对 0 的邻接矩阵执行少于 (−1)C2 次访问， 那么 ALG 就不会区分 0 和 1，1 不是二分的。"
我的问题是 (n-1)C2 访问是什么意思。它是说，例如，如果我们有一个不同的 V = {A,B,C,D} 那么 ALG 将查看所有节点对，除了 D 和其他节点之间的节点对？
抱歉，如果不清楚，这个证明真的让我很困惑。
G0 是一个 n 顶点 star graph。它是二分的，但如果您向它添加任何其他边，则生成的图形就不是。有 n−1 选择 2 = (n−1)(n−2)/2 = Ω(n2) 其他我们可以添加的边。每个正确的算法都必须检查每个算法，以验证 G0 是二分的。