Направленный граф с максимальной степенью вершины - PullRequest
Новая
       23

Направленный граф с максимальной степенью вершины

6 голосов
/ 17 ноября 2011

Я пытался взглянуть на несколько приложений сетевого потока, когда натолкнулся на эту проблему:

Начнем с ориентированного графа, G = (V,E). Нам нужно добавить больше ребер на график, чтобы у нас было \forall u,v \in V, e = (u -> v) or e = (v -> u) but not both. то есть мы хотим добавить больше ребер в граф так, чтобы каждая пара вершин графа была связана друг с другом (либо с исходящим ребром, либо с входящим ребром, но не обоими). Итак, всего у нас будет |V||V-1|/2 ребер. Пока мы строим этот граф, нам нужно убедиться, что степень данной вершины, скажем, w, является максимальной среди всех вершин графа (если это возможно, учитывая исходный граф). Обратите внимание, что мы не можем изменить ориентацию ребер в исходном графике.

Я пытаюсь решить эту проблему с помощью сетевого потока путем построения сети без вершины w (и с 2 новыми вершинами для source, s и sink, t). Но я не уверен, как представить емкости и направление потока в новом графике, чтобы упростить задачу для сетевого потока, чтобы найти ориентации ребер в графике. Возможно, то, что я делаю, неправильно, но я просто написал, если кто-то может получить подсказку от этого.

1 Ответ

2 голосов
/ 18 ноября 2011

Когда я решаю проблему такого рода, я обычно пишу математическую программу, а затем массирую ее.Ясно, что мы должны сориентировать все отсутствующие ребра с участием w в направлении w.Пусть d будет результирующей степенью w.Для всех различных i, j, пусть x_{ij} = 1, если дуга i-> j появляется в решении, и пусть x_{ij} = 0, если дуга j-> i появляется. 

forall j. sum_i x_{ij} <= k
forall i <> j. x_{ij} = 1 - x_{ji}
forall i <> j. x_{ij} in {0, 1}

Перепишите, чтобы использоватьx_{ij} только если i 

(*) forall j. sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) <= k
forall i < j. x_{ij} in {0, 1}

Теперь (*) начинает напоминать ограничения сохранения, поскольку каждая переменная появляется один раз отрицательно и один раз положительно.Давайте изменим неравенство на равенство. 

(*) forall j. x_{si} + sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) = k
              ^^^^^^                                           ^
forall i < j. x_{ij} in {0, 1}
forall i. x_{si} >= 0
^^^^^^^^^^^^^^^^^^^^^

Мы почти все до потока LP - нам просто нужно очистить константы 1 и k.Я позволю вам разобраться с остальным (это включает введение t).

...