algorithm - 在完整图的有序集中查找顶点

Question

问题:对于完全图Kn的一组有序边E，给定边Ei，求边的顶点(v, w)_Ei。

注意:这可能不是图论特有的问题，尽管选择它来表达问题仅仅是因为熟悉。对引入的任何不正确的符号表示歉意。

假设由一个由顶点1、2、3、4、5组成的完备图K5构造，我们有一个图的边的有序集合E，共10条边。已知集合 E 总是按如下方式排序:

Ei = (0 < v < n, v < w =< n)

E1 = (1, 2)
E2 = (1, 3)
E3 = (1, 4)
E4 = (1, 5)
E5 = (2, 3)
E6 = (2, 4)
E7 = (2, 5)
E8 = (3, 4)
E9 = (3, 5)
E10 = (4, 5)

对于任何给定的 Ei，我们现在必须单独使用 i 找到顶点 (v, w)_Ei。例如，给定 6 我们应该得到 (2, 4)。

更新:表达这个问题的另一种可能更简单的方法是:

n = 5
i = 0

for v = 1 to n - 1
    for w = v + 1 to n
        i++
        print "E" + i + " = " + v + ", " w 


print "E6 = " + findV(6) + ", " + findW(6)

这是怎么做到的？

Answer 1

要解决封闭形式的问题，我们需要前 k 个数之和的公式:1 + 2 + ... + k = (k + 1) * k/2。这为我们提供了从边 (i, j) 到边索引的映射:

from math import ceil, sqrt

def edge_to_index((i, j)):
    return n * (i - 1) + j - i * (i + 1) / 2

我们可以推导出逆映射:

def index_to_edge(k, n):
    b = 1.0 - 2 * n
    i = int(ceil((-b - sqrt(b**2 - 8 * k)) / 2))
    j = k - n * (i - 1) + i * (i + 1) / 2
    return (i, j)

一个测试:

n = 5

print "Edge to index and index to edge:"
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        k = edge_to_index((i, j))
        print (i, j), "->", k, "->", index_to_edge(k, n)

输出:

Edge to index and index to edge:
(1, 2) -> 1 -> (1, 2)
(1, 3) -> 2 -> (1, 3)
(1, 4) -> 3 -> (1, 4)
(1, 5) -> 4 -> (1, 5)
(2, 3) -> 5 -> (2, 3)
(2, 4) -> 6 -> (2, 4)
(2, 5) -> 7 -> (2, 5)
(3, 4) -> 8 -> (3, 4)
(3, 5) -> 9 -> (3, 5)
(4, 5) -> 10 -> (4, 5)