Нахождение вершин в упорядоченном множестве полного графа

Question

Задача: Для упорядоченного множества ребер E полного графа Kn, заданного ребром Ei, найти вершины ребра (v, w) _Ei.

Примечание. Вероятно, это не проблема, специфичная для теории графов, хотя она была выбрана для выражения проблемы исключительно из-за фамильярности. Извинения за любые неправильные обозначения введены.

Предположим, что построенный из полного графа K5, состоящего из вершин 1, 2, 3, 4, 5, мы имеем упорядоченное множество 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 теперь мы должны найти вершины (v, w) _Ei, используя только i. Например, учитывая 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, что меньше восьми. Затем мы добавляем 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. Бинарный поиск будет работать хорошо, или вы можете решить квадратик, используя квадратную формулу, и округлить (возможно, придется подумать, если это сработает).

Найти W легко, учитывая V:

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 ...).Для умеренных значений n вы можете рассмотреть таблицу с предварительно вычисленными значениями, если важна производительность.