Преобразование орграфа в неориентированный граф обратимым способом

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

Кто-нибудь знает, как это сделать или может предложить какие-либо ссылки? Заранее спасибо.

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

Обновление после комментария DW: я считаю вершины графиков немаркированными. Если решение включает в себя маркировку вершин (как это делает AdrianN), то оно должно давать один и тот же (изоморфный) неориентированный граф независимо от того, как выполняется маркировка. Мое определение «изоморфного» для графов с помеченными вершинами состоит в том, что существует перестановка маркировки, которая связывает два графа, но я не уверен в точном определении для немаркированных графов ...

Для каждого направленного ребра добавьте новые вершины и замените ребрами , , , , , .v е 1 , ... , v е 5 е х V е 1 v е 1 v $e=(x,y)$$v^e_1, \dots, v^e_5$$e$$xv^e_1$$v^e_1v^e_2$$v^e_1v^e_3$$v^e_3v^e_4$$v^e_4v^e_5$$v^e_3y$

Для декодирования каждый лист (вершина степени 1), сосед которого имеет степень 2, должен быть  для некоторого ребра ; его сосед  а другой сосед  -  .  есть уникальный сосед, имеющий как степень 3, так и смежный с листом: сосед -  а его лист -  (если у есть два соседа листа, выберите один из них произвольно, чтобы он был ). Другой сосед - это  а другой сосед - это $v^e_5$v e 4 v e 4 v e 3 v e 3 v e 1 v e 2 v e 1 v e 2 v e 1 x v e 3$e=(x,y)$$v^e_4$$v^e_4$$v^e_3$$v^e_3$$v^e_1$$v^e_2$$v^e_1$$v^e_2$$v^e_1$$x$$v^e_3$$y$, Восстановите направленное ребро и удалите вершины v e 1 , … , v e 5 .$(x,y)$$v^e_1, \dots, v^e_5$

Ответ Дэвида Ричерби (который был принят) хорош.

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

(Я бы опубликовал это как комментарий к ответу Дэвида, но у меня нет необходимых очков репутации.)

Чтобы преобразовать ориентированный граф в неориентированный граф G, нужно сделать следующее:$D$$G$

1. Нумерация узлов $D$
2. Создайте два неориентированных графа , G ″ в той же вершине, что и $G'$$G''$$D$
3. Для каждого ребра , v в D добавьте ребро в G ′, если u < v , иначе добавьте ребро в G $u$$v$$D$$G'$$u<v$$G''$
4. G является непересекающимся объединением и G $G'$$G''$

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

А как насчет функции идентичности? Т.е. каждый орграф можно рассматривать как неориентированный двудольный граф с равными по размеру разбиениями и наоборот.

Вот удар в этом:

Замените информацию о направлении дополнительными вершинами в неориентированном графе. Другими словами, используйте дополнительные вершины в неориентированном графе для «кодирования» информации о направлении. Например, для каждой направленной вершины, имеющей хотя бы одно ребро, добавьте количество неориентированных вершин, равное 1 + количество «входящих» ребер. Вершины с нулевыми ребрами остаются без изменений.

Чтобы выполнить обратное направление, создайте направленную вершину для каждой вершины, имеющей 0 или более 1 ребра. (Вершины с ровно одним ребром являются вершинами "кодирования направления"). Каждое ребро, соединяющее другую многогранную вершину, является связью в ориентированном графе. Теперь есть сложная часть, для которой я не могу объяснить алгоритм (но я думаю, что он существует): вы должны определить направление стрелок, учитывая только количество входящих стрелок для каждой вершины.

Я думаю, что сложная часть похожа на игру тральщика :-) Выясните, где бомбам (входящим ребрам) дают количество смежных бомб для каждого квадрата (вершины).