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

问题：对于完全图Kn的边E的有序集，给定一个边Ei，找到边的顶点（v，w）Ei。
注：这可能不是图论特有的问题，尽管选择它来表示问题仅仅是因为熟悉。对引入的错误符号表示歉意。
假设由顶点1，2，3，4，5构成的完整图k5，我们有一个图的边的有序集e，共有10条边。已知集合E总是按如下顺序排列：
ei=（0

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)

怎么做到的？

最佳答案

要以封闭形式解决这个问题，我们需要第一个k数之和的公式：1 + 2 + ... + k = (k + 1) * k / 2。这为我们提供了从edge(i, j)到edge index的映射：

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)