Кодирование ориентированного графа как числа

Question

Предположим, что у меня есть ориентированный граф с одним корнем и без циклов. Я хотел бы добавить тип на каждом узле (например, как целое с некоторой пользовательской упорядоченности) со следующим свойством:

if Node1.type <= Node2.type then there exists a path from Node1 to Node2 

Заметим, что топологическая сортировка фактически удовлетворяет обращенную свойство:

if there exists a path from Node1 to Node2 then Node1.type <= Node2.type 

поэтому его здесь нельзя использовать.

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

Итак, вот пример. Предположим, что граф имеет 4 узла A, B, C, D и 4 стрелы:

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

Так что это бриллиант. Теперь мы можем поставить

A.type = 00 
B.type = 01 
C.type = 10 
D.type = 11 

где с правой стороны у нас есть целые числа в двоичном формате. Сравнение определяется побитовое:

(X <= Y) if and only if (n-th bit of X <= n-th bit of Y for all n) 

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

UPDATE: Поскольку существуют некоторое недопонимание о терминологии, которую я использую, позвольте мне быть больше Явным: Я заинтересован в ориентированном ациклическом графе, что существует ровно один узел без предшественников (он же корень) и есть в одна стрелка между любыми двумя узлами. Примером может служить алмаз. Он не должен иметь один лист (т. Е. Узел без преемников). Каждый узел может иметь несколько предшественников и несколько преемников. Вы можете сказать, что это частично упорядоченный набор с наименьшим элементом (т. Е. Уникальный глобально минимальный элемент).

Answer 1

Для любого DAG вы можете определитьx <= y как «есть путь от x до y». Это соотношение является частичным порядком. Я полагаю, что вопрос заключается в том, как эффективно представлять это отношение.

Для каждой вершины X определите ¡X как множество вершин, доступных из X (включая сам X). Два утверждения

• ¡Х представляет собой подмножество ¡Y
• X достижима из Y

эквивалентны.

Кодировать эти наборы как биты (N-битные двоичные числа), и вы настроены.

Answer 2

Вы называете соотношение <=, но это обязательно не полный (то есть: это может быть, что для данной пары a и b, ни a <= b ни b <= a).

Вот одна идея, как определить его.

Если узлы пронумерованы от 0, 1, ..., N-1, то вы можете определить type так:

type(i) = (1 << i) + sum(1 << (N + j), for j such that Path(i, j)) 

И определить <= вроде этого:

type1 <= type2 if (type1 >> N) & type2 != 0 

То есть , type(i) кодирует значение i в самом нижнем N битах и ​​множество всех достижимых узлов в наивысшем N битах. Отношение <= ищет целевой узел в кодированном наборе достижимых узлов.

Это определение работает независимо от того, существуют ли на графике циклы или нет, и на самом деле просто кодирует произвольное отношение к вашему набору узлов.

Вы можете сделать определение немного более эффективным, используя ceil(log2(N)) бит для кодирования номера узла (всего N + ceil(log2(N)) бит за type).

Answer 3

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

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

В дереве, направленном от корня, для любых двух вершин u и v множества листьев L (u) и L (v), достигаемые из u и v соответственно, должны быть либо непересекающимися, либо должны быть быть подмножеством другого. Если они не пересекаются, то u не достижимо из v (и наоборот); если один является собственным подмножеством другого, то с меньшим множеством можно достичь от другого (и в этом случае тот, у которого меньший набор, обязательно будет иметь строго большую глубину). Если L (u) = L (v), то u можно достичь из v тогда и только тогда, когда глубина (v) < depth (u), где глубина (u) - это количество ребер на пути от корня до u. (В частности, если L (u) = L (v) и глубина (u) = глубина (v), то u = v.)

Мы можем кодировать эти отношения лаконично, заметив, что все листья достижимы от заданного вершина v занимает смежный отрезок листьев, выводимых путем обхода дерева. Поэтому для любой заданной вершины v этот набор листьев может быть представлен парой целых чисел (first, last), где first идентифицирует первый лист (в порядке обхода порядка) и last последний. Тест для того, существует ли путь от I до J тогда очень просто - в псевдо-C++:

bool doesPathExist(int i, int j) { 
    return x[i].first <= x[j].first && x[i].last >= x[j].last && depth[i] <= depth[j]; 
} 

Обратите внимание, что если каждый не-лист вершин в дереве имеет по крайней мере 2-х детей, то вы не» t нужно беспокоиться о глубинах, так как L (u) = L (v) в этом случае означает u = v. (Моя первоначальная версия сообщения сделала это предположение: теперь я исправил ее работу, даже если это не так).