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

问题：对于完整图Kn的一组有序边E，给定边Ei，找到边的顶点（v，w）_Ei。 注意：这可能不是图论特有的问题，尽管选择它仅仅是因为熟悉而表达问题。对任何不正确的符号表示歉意。 假设由包含顶点1,2,3,4,5的完整图K5构造，我们有一个图的边的有序集E，总共10个边。已知集合E总是如下排序： Ei =（0＆lt; v＆lt; n，v＆lt; w =＆lt; 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)
这是怎么做到的？     
2019-09-09 5 条评论
分享

没有找到相关结果

    已邀请:

    嗓瑰

    为了解决封闭形式的问题，我们需要第一个
    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)
        
    2019-09-09 0 0
    分享

    捐焦

    让我重申一下我认为你问的问题，如果这完全偏离主题，你可以告诉我：   给定整数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将给我们九，大于八，所以我们停止。我们将两个数字加在一起，因此第一个数字必须是3。 一旦我们知道第一个数字是什么，您就可以很容易地获得第二个数字。在执行获取第一个数字的步骤时，我们基本上列出了第一个数字发生变化的对的索引。例如，在我们的上述情况中，我们有系列0,4,7。在这些中添加一个给出1,5,8，这实际上是分别以数字1,2和3开头的第一对。一旦你知道了第一个数字是什么，你也知道这个数字的对在哪里开始，所以你可以从那个位置中减去你的数字的索引。这告诉您，使用零索引，您从该元素中采取了多少步骤。而且，你知道第一个元素的第二个值是什么，因为它是一个加上第一个元素，所以你可以说第二个值是由第一个数字加一个加上你的索引超出的步数第一对以给定数字开头。在我们的例子中，因为我们正在查看索引8并且我们知道以3开头的第一对是在第8位，我们得到第二个数字是3 + 1 + 0 = 4，我们的对是（3,4） 。 这个算法实际上非常快。给定k，该算法最多需要k步才能完成，因此在O（k）中运行。将此与扫描一切的天真方法相比较，需要O（k2）。     
    2019-09-09 0 0
    分享

    替秀宝

    为了让我的生活更轻松，我将按照你的问题从0开始，而不是从1开始。 首先，我们推导出一个术语
    (v,v+1)
    （第一个以
    v
    开头）的公式。这只是
    n-1 + n-2 + ... + n-v
    的算术和，即
    v(2n-v-1)/2
    。 因此，在索引
    i
    的情况下找到
    v
    ，只需求解方程
    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
        
    2019-09-09 0 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的中等值，如果性能很重要，您可能需要考虑预先计算的查找表。     
    2019-09-09 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.03532600402832