Как преобразовать неориентированный граф в группу доступности баз данных?

Question

Страница Wiki говорит

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

Но я не знаю, как получить полный порядок неориентированного графа.Должен ли я использовать DFS?Если так, как мне поступить?

Дополнительная информация : я работаю над неориентированным графом, который имеет один источник и один приемник.Я пытаюсь направить эти ребра так, чтобы, следуя направлению ребра, я мог добраться от источника до раковины.

Answer 1

Общий порядок - это, в основном, просто расположение всех вершин в некотором порядке - думайте об этом как о маркировке каждой вершины числом от 1 до | V (G) |.Это дает нам непротиворечивый способ узнать, какая вершина выше для любой пары рассматриваемых нами вершин.

Да, вы можете получить полное упорядочение с помощью поиска в глубину.Просто присвойте каждой вершине значение инкрементного счетчика каждый раз, когда вы исследуете вершину в DFS.Вот как вы можете получить общий порядок.

Но вам не нужно явно указывать общий порядок для получения DAG.Если мы используем вышеуказанное время исследования в качестве нашего порядка, то мы можем действовать следующим образом: Ориентировать края, как вы делаете обход DFS, направляя каждый неориентированный край от вершины, которую вы в данный момент расширяете.

В основном, у нас есть вершины, которые мы исследовали ранее, указывающие на вершины, которые мы исследовали позже.

например.если у вас было

  A
 / \
B---C

, и вы начали с исследования A, вы бы сориентировали края, падающие на A, от A:

A --> B
A --> C
B --- C

Теперь скажем, что вы выбрали B, чтобы исследовать следующий в вашей DFSВТП.Тогда вы оставите ребро между A и B в одиночку, потому что вы уже ориентировали это ребро (A уже полностью развернуто).Грань между B и C была нетронутой, так что отошли от нашей текущей вершины, B, чтобы получить:

A --> B
A --> C
B --> C

Когда вы исследуете C, все его соседи полностью развернуты, поэтому ничего не происходитосталось сделать для C, и больше нет вершин для исследования.

Ответ на "More Info":

В этом случае, просто убедитесь, что вы расширилиисходная вершина сначала и просто не исследуйте приемник.Например.для

A-B-C
|/
D

, где D - источник, а B - приемник, вы можете: развернуть D, затем A, затем C. Вы получите:

D --> A
D --> B
A --> B
C --> B

Answer 2

Проблема в том, что после того, как мы изменим наши неориентированные ребра на направленные, мы не хотим, чтобы оставались циклы.

Например, предположим, что у нас есть полный граф треугольников

A -- B
  \  |
   \ |
     C

Мы могли бы выбрать ориентацию для ребер как A -> B, B -> C и C -> A

A -> B
 \\  |
   \ v
     C

Но тогда мы получили бы цикл, и это не Направленный Ациклический График.

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

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

Answer 3

На самом деле, я думаю, что это означает на вики-странице, что «выбор общего заказа» означает определение общего заказа самостоятельно.Другими словами, если мы проверим простейший неориентированный граф:

A----B

Преобразование этого неориентированного графа в группу доступности базы данных явно зависит от того, выберете ли вы порядок A до B или A после B. Если вы выберите A до Bзатем он становится:

A--->B

В противном случае он становится:

B--->A

Это именно то, что он означает, «ориентируя каждое ребро» от конечной точки «РАННЕЕ» (появляются конечные точкиранее в итоговом порядке) до конечной точки «ПОЗЖЕ».

Аналогично для:

    A
   / \
  /   \
 B-----C

Если вы определяете общий порядок как:

B A C

Тогдаориентированный граф должен быть примерно таким:

B->A, B->C, A->C

Answer 4

Вы можете получить общий заказ и превратить неориентированный граф в узлы нумерации DAG в обратный пост-порядок .

Выполнить Глубину после заказа первый обход присвоение номера каждому узлу , когда вы его оставляете , в последовательности от 1 до n.Порядок посещения соседних узлов определяет направление ребер в группе обеспечения доступности баз данных.Не пересекайте ребра, которые ведут от узла с более высоким номером к узлу с более низким номером - это разбивает циклы, эффективно определяя, что в конечном DAG этот край будет в противоположном направлении.

Этот порядок дает топологическую сортировкуграфика, это полный порядок, и поскольку существует топологический порядок, график превращается в DAG.

EDIT : чтобы уточнить, как только вы пометили узлы с их RPO-для каждого ребра a <-> b в исходном графике ребро в группе обеспечения доступности баз данных будет a -> b тогда RPO-number(a) < RPO-number (b), в противном случае ребро будет b -> a.

EDIT :выше этого - избыточное убийство, однако, оно будет работать, если некоторые ребра направлены, а некоторые нет, если все они не направлены, как указано @missingno, достаточно любого порядка.