0

问题：对于一个完全图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)

这是怎么做到的？

4

4 回答 4

3

为了解决封闭形式的问题，我们需要第一个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)
于 2011-01-19T22:20:44.280 回答
1

让我重申一下我认为您要问的问题，以便如果这完全偏离主题，您可以告诉我：

给定一个整数 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，仍然小于 8。但是，添加 k - 3 = 2 将得到 9，大于 8，因此我们停止。我们将两个数字相加，所以第一个数字一定是 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 2 )。

于 2011-01-19T21:55:24.213 回答
1

为了让我的生活更轻松，我将以 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
于 2011-01-19T22:09:23.660 回答
0

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

于 2011-01-19T21:49:02.940 回答