Эффективный алгоритм вычисления линейного орграфа из орграфа

Кто-нибудь знает эффективный алгоритм для вычисления линейного орграфа из орграфа? См. http://en.wikipedia.org/wiki/Line_graph (в статье Википедии упоминается случай орграфа внизу (в разделах «Обобщения») В идеале я хотел бы сделать это за линейное время.

Из этого раздела:

  • Если G — ориентированный граф, его ориентированный линейный граф или линейный орграф имеет по одной вершине для каждого ребра графа G.
  • Две вершины, представляющие направленные ребра от u до v и от w до x в G, соединены ребром от uv до wx в линейном орграфе, когда v = w.

Пусть G — ориентированный граф. Пусть L(G) — линейный ориентированный граф.

Алгоритм, который я могу придумать для получения L(G) при заданном G:

  • Перебрать все ребра G, чтобы получить узлы L(G)
  • Перебрать все пары узлов (uv, wx) в L(G) и соединиться, если v = w

Это алгоритм O (n ^ 2).

Похоже, должен быть способ сократить это время до O(n). Я собираюсь подумать об этом, но я решил спросить переполнение стека на всякий случай, если есть какой-то известный (или не очень известный) алгоритм для этого, о котором я не знаю.


algorithm linegraph graph-theory
person stonea    schedule 03.06.2009    source источник
comment
Я предполагаю, что лучший способ сделать это - изменить второй шаг итерации по всем парам узлов (uv, wc) в L (G)...), чтобы вместо этого он выполнял итерацию по всем узлам v в G.   -  person stonea    schedule 04.06.2009
comment
Тогда для каждого входящего ребра uv и исходящего ребра vx будет ребро в L(G) (между узлами uv и vx). Хотя это все еще звучит как алгоритм O (n ^ 2). Может быть есть какой-то амортизированный анализ для этого?   -  person stonea    schedule 04.06.2009

Ответы (2)


arrow_upward
1
arrow_downward

Хм... Я думаю, что после некоторых размышлений может быть более эффективный алгоритм... но для этого потребуется изрядное количество бухгалтерского учета и кусок дополнительной памяти.

Мои основные мысли заключаются в том, что вы перебираете все узлы в G и создаете связанные узлы из ребер, связанных с каждым узлом. С дополнительной ссылкой для отслеживания G (ребро) в L (G) (узел) вы можете обойтись всего одним циклом через узлы на G.

person workmad3    schedule 03.06.2009

arrow_upward
1
arrow_downward

Вы не можете вычислить из O(n^2), потому что есть некоторый граф с линейным графом с мощностью ребер, равной квадрату мощности вершин исходного: подумайте, например, в граф с n + 1 вершинами, с одной вершиной, соединенной со всеми остальными вершинами: затем вам нужно построить клику с n вершинами, то есть с (n-1) ^ 2 ребрами.

Сложность алгоритма ограничена снизу размером выходных данных, которые он производит.

Это, конечно, не означает, что нам не нужно искать умные алгоритмы. Я подумал при этом:

LG(LN,LE) getLinearGraph(G(N,E)) {
  LN = EmptySet();
  LE = EmptySet();
  for (Vertex v : N) {
    verticesToAdd = EmptySet()
    for (Vertex i : out-degree(v) {
      toAdd += textual-rep((v,i));
    }
    LN += toAdd;
    LE += make-clique(toAdd);
  }
}
person akappa    schedule 03.06.2009
comment
Я не совсем уверен, что понимаю ваш пример. Вы имеете в виду, что G это: www.cs.colostate.edu/~stonea/stkimg/g.png (я не знаю, как здесь вставлять изображения в комментарии). В этом случае линейный график будет состоять только из узлов {ab, ac, ad, ...} и без ребер. - person stonea; 04.06.2009
comment
Хотя я подозреваю, что вы правы в том, что в L(G) может быть квадратичное раздутие ребер. Я могу вспомнить случаи, когда L(G) имеет больше ребер, чем G (например, в статье в Википедии). - person stonea; 04.06.2009
comment
Линейный граф ориентирован, а исходный — нет, так что да, если вы считаете эти ребра неориентированными, у вас есть мой пример. - person akappa; 04.06.2009
comment
Вы можете видеть, что я имею в виду на примере из Википедии: 3 связано с 1 и 4, а в линейном графе у нас есть встроенная клика с узлами (1,3), (1,4), (3,4). - person akappa; 04.06.2009
comment
Окей, я вижу. Правильно, вы получите клику с этим: www.cs.colostate.edu/~stonea/stkimg/g2.png - person stonea; 04.06.2009
comment
Итак, если у вас есть один узел, соединенный со всеми остальными узлами (и никаких других ребер), вы просто получите гигантскую клику. - person akappa; 04.06.2009
comment
Или на самом деле нет, я бы не получил клик с этим изображением g2, которое я только что связал. В L(G) было бы ребро ba,ab, но не было бы ребра ab,ac). Но это все равно O(n^2) ребер. - person stonea; 04.06.2009
comment
Но я не понимаю, почему вы говорите об ориентированных графах, когда проблема связана с неориентированными. - person akappa; 04.06.2009
comment
Конкретная проблема, с которой я сталкиваюсь, заключается в преобразовании ориентированного графа в ориентированный линейный граф. Статья в Википедии в основном посвящена неориентированным графам, но алгоритм, который мне нужно написать, предназначен для ориентированного случая. - person stonea; 04.06.2009
comment
О, тогда вы должны более четко указать, что по этому вопросу я только прочитал статью в Википедии;) - person akappa; 04.06.2009
comment
Думал, что это ясно из названия вопроса :-), но я только что отредактировал свой вопрос, чтобы попытаться сделать его более понятным. Тем не менее, спасибо за ваш вклад, сегодня я кое-что узнал о теории графов, и даже в направленном случае может быть O (n ^ 2) раздутие ребер (изображение g2 пример такого). - person stonea; 04.06.2009