在一组完整的图表中查找顶点

Question

问题：对于一个完整的图kN的有序的边缘E，给定边缘EI，找到边缘的顶点（v，w）_ei。

注意：这可能不是图理论的特定问题，尽管仅由于熟悉程度而被选择以表达问题。对于引入任何不正确的符号表示歉意。

假设由完整的图k5构造，该图由顶点1、2、3、4、5组成，我们有图形边缘的有序集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)

Answer 2

让我重申我认为您要问的问题，以便如果这完全是偏离主题，您可以让我知道：

给定一个整数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，小于8。然后，我们将k -2 = 3添加到获得7，仍然少于八个。但是，添加k -3 = 2会给我们九个超过八个，因此我们停止。我们一起添加了两个数字，因此第一个数字必须为3。

一旦我们知道第一个数字是什么，您就可以很容易地获得第二个数字。在执行第一个数字的步骤时，我们从本质上列出了第一个数字更改的对的索引。例如，在上面的情况下，我们的系列0、4、7。在每个情况下添加一个，给出1、5、8，这确实是以数字1、2和3的开头的第一对。 。一旦知道了第一个数字是什么，您还知道与该数字的介绍从哪里开始，因此您可以从该位置减去数字的索引。这告诉您，通过零索引，您从该元素中走了多少个步骤。此外，您知道第一个元素的第二个值是什么，因为它是第一个元素，因此您可以说第二个值是由第一个数字给出的，再加上一个，再加上您的索引超出了索引的步骤数第一对以给定的数字开头。在我们的情况下，由于我们正在查看索引8，并且我们知道以三个位置为8的第一对，因此我们得到第二个数字是3 + 1 + 0 = 4，而我们的一对是（3，4） 。

该算法实际上很快。给定任何K，此算法最多需要K步骤完成，因此在O（k）中运行。将此与扫描所有内容的天真方法进行比较，这需要O（K²).

Answer 3

为了使我的生活更轻松，我将做我的数学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. 。二进制搜索可以很好地工作，或者您可以使用二次公式解决二次搜索，然后再下降（也许必须考虑到这是否有效）。

鉴于v，找到W很容易：

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

Answer 4

好吧，简单的方法是循环并减去与第一个顶点相对应的值，如下（在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值，如果性能很重要，您可能需要考虑一个预定的查找表。