有序集合了完整的图形

Question

问题寻找顶点：对于有序集中完全图的边缘电子商务，给定边EI，找到边缘的顶点（V，W）_Ei。

注意：这很可能不是一个问题，具体到图论，虽然它被选为仅表达熟悉的，因为这个问题。对引入的任何不正确的符号抱歉。

假设从由顶点1，2，3，4，5的一个完全图K5构造，我们有图形的边缘的一组有序的E，共计10层的边缘。集合E是众所周知的总是命令如下：

荣=（0 < v < N时，V<瓦特= < 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，我们现在必须找到顶点（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) 

Answer 2

好了，简单的方法是遍历和减去对应的第一个顶点值，（在python）如下：

def unpackindex(i,n): 
    for v in range(1,n): 
    if v+i<=n: return (v,v+i) 
    i-= n-v 
    raise IndexError("bad index") 

如果你正在寻找一个封闭形式的公式，而不是一个算法，你需要在某一点做一个平方根，所以它很可能是混乱的，有点慢（尽管不像上面的循环那么慢，因为足够大的n ...）。对于n的中等值，如果性能很重要，则可能需要考虑预先计算的查找表。

Answer 3

让我重申，我认为你的要求，这样，如果这完全是题外话，你可以让我知道了一个问题：

给定一个整数k和系列（1,2）， （1，3），...，（1，K），（2,3），（2,4），...，（2，K），（3,4），...，（K - 1，k）和索引n，返回本系列的第n项的值。

下面是一个简单的算法来解决这个问题，可能不是渐近最优。注意第一对（k-1）以1开始，下一个（k-2）以2开始，下一个（k-3）以3开始，等等。为了确定第一个元素的值一对是，你可以不断加起来这些数字（K - 1）+（K - 2）+ ...直到你最终的值大于或等于你的指数。你可以做的次数这一点，再加上一个，让你的第一个数字：

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) 

这里，k = 5。要找到项8的第一个数字，我们首先添加的K - 1 = 4，这少于八个。然后我们加上k - 2 = 3得到7，但仍然小于8。然而，加k - 3 = 2会给我们九个，这个数字大于八，所以我们停下来。我们增加了两个数字加在一起，所以第一个数字必须是3

一旦我们知道了第一个数字是什么，你可以很轻松地获得第二个数字。当进行获取第一个数字的步骤时，我们基本上列出了第一个数字变化对的索引。例如，在我们上面的例子中，我们有0,4,7系列。给它们中的每一个增加一个给出1，5，8，这实际上是分别以数字1,2和3开始的第一对。一旦你知道第一个数字是什么，你也知道与那个数字的配对是从哪里开始的，所以你可以从那个位置中减去你的数字的索引。这会告诉你一个零索引，你从这个元素中取得了多少个步骤。此外，你知道这是什么第一个元素的第二值，因为它是一加的第一个元素，所以你可以说，第二个值由第一个数字定，加一加的步数的指数超出第一对以给定的数字开始。在我们的例子中，因为我们看索引8，并且我们知道以3开始的第一对在位置8，所以我们得到第二个数字是3 + 1 + 0 = 4，并且我们的对是（3,4） 。

这种算法实际上是非常快的。给定任意k，该算法最多需要k个步骤才能完成，因此以O（k）运行。将其与扫描所有内容的幼稚方法相比较，这需要O（k ）。

Answer 4

为了让我的生活更轻松，我将以你的问题为基础进行基于0的数学运算，而不是基于1的数学运算。

首先，我们推导出术语(v,v+1)（首先以v开头）的索引公式。这只是n-1 + n-2 + ... + n-v的算术总和，即v(2n-v-1)/2。

所以要找到v给出索引i，只需解决方程v(2n-v-1)/2 <= i为最大积分v。二进制搜索可以很好地工作，或者你可以使用二次方程式求解二次方程并向下舍入（也许，必须考虑如果结果正常）。

寻找W被容易给出五：

findW(i): 
    v = findV(i) 
    i_v = v(2n-v-1)/2 
    return i - i_v + 1