Konwersja digrafu na niekierowany wykres w odwracalny sposób

10

Szukam algorytmu do konwersji digrafu (grafu kierunkowego) na graf niekierowany w sposób odwracalny, tzn. Digraf powinien być odtwarzalny, jeśli otrzymamy wykres niekierowany. Rozumiem, że przyjdzie to kosztem niekierowanego wykresu mającego więcej wierzchołków, ale nie mam nic przeciwko.

Czy ktoś wie jak to zrobić lub może zasugerować jakieś referencje? Z góry dziękuję.

Aktualizacja: w odniesieniu do odpowiedzi AdrianN poniżej. To może być dobry punkt wyjścia, ale nie sądzę, aby działał w obecnej formie. Oto obraz, dlaczego uważam, że tak nie jest: wprowadź opis zdjęcia tutaj

Aktualizacja po komentarzu DW: Uważam, że wierzchołki wykresów są nieopisane. Jeśli rozwiązanie wymaga oznakowania wierzchołków (jak robi to AdrianN), powinno dać ten sam (izomorficzny) niekierowany wykres, bez względu na to, jak to się robi. Moja definicja „izomorficzna” dla grafów z etykietowanymi wierzchołkami polega na tym, że istnieje permutacja etykietowania, która dotyczy dwóch grafów, ale nie jestem pewna dokładnej definicji grafów bez etykiet ...

algorithms graph-theory graphs

— Heterotyczny
źródło

1

Myślę, że to pytanie jest zbyt ogólne. Jakie są twoje ograniczenia?

— adrianN

Na razie nie mogę wymyślić żadnych ograniczeń. Sądzę, że jakikolwiek sposób na zakodowanie informacji z ukierunkowanego wykresu w niekierowanym grafie byłby wystarczający, o ile jest on odwracalny. Myślę, że mam na myśli najprostszy rodzaj niekierowanych grafów, więc szukam rozwiązania, które nie używa kolorów ani dla wierzchołków, ani krawędzi.

— Heterotic

Myślę, że powinieneś sprecyzować w pytaniu, co rozumiesz przez „ten sam wykres”. Czy masz na myśli, że wierzchołki są oznaczone, czy że wierzchołki są nieoznakowane? Czy masz na myśli, że jest taki sam dla obu, lub że dwa wykresy są izomorficzne? Wygląda na to, że masz na myśli to drugie. Czy na pewno jest to wymagane w Twojej aplikacji? Jeśli możesz zachować etykiety, problem staje się łatwiejszy i odpowiedź AdrianN działa (ponieważ krawędź nie jest taka sama jak krawędź ).

(V, E)

$(V,E)$

(3, 4)

$(3,4)$

(1^{'}, 2^{'})

$(1',2')$

— DW

2

Proszę włączyć aktualizacje w rachubę. W dowolnym momencie posty SE powinny być czytelne od góry do dołu, bez zastanawiania się nad historią; które są archiwizowane osobno.

— Raphael

6

Dla każdej skierowanej krawędzi dodaj nowe wierzchołki i zamień na krawędzie , , , , , . $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$

Aby zdekodować, każdy liść (wierzchołek stopnia 1), którego sąsiad ma stopień 2, musi mieć dla pewnej krawędzi ; jego sąsiadem jest a drugim sąsiadem jest . ma unikalnego sąsiada, który ma oba stopnie 3 i przylega do liścia: sąsiad jest a jego liść to (jeśli ma dwóch sąsiadów liści, wybierz jednego arbitralnie, aby być ). Drugim sąsiadem jest a drugim sąsiadem jest . Przywróć ukierunkowaną krawędź $v^e_5$ $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$ $(x,y)$ i usuń wierzchołki . $v^e_1, \dots, v^e_5$

— David Richerby
źródło

7

Odpowiedź Davida Richerby'ego (która została zaakceptowana) jest dobra.

Postępowałem zgodnie z jego instrukcjami na prostym przykładowym digrafie i mam nadzieję, że to komuś pomoże.

digraph a <-> b, c -> a, b -> c

(Chciałbym zamieścić to jako komentarz do odpowiedzi Davida, ale nie mam wymaganych punktów reputacji).

— William
źródło

1

Reprezentacja graficzna stanowi ogromną poprawę w stosunku do pierwotnej odpowiedzi. Dziękujemy za opublikowanie go jako odpowiedzi, a nie komentarza.

— OrangeSherbet,

1

Zawsze czuję się przytłoczony, gdy patrzę na formalne wyjaśnienie lub formułę w pracy matematycznej. Muszę tylko pokonać ten lęk i powoli patrzeć na każde zdanie - patrząc na rzeczy, których nie znam. Piszę taki przykład, aby się upewnić, że rozumiem. Do końca zawsze jestem oszołomiony tym, jak proste to wszystko było długie i trochę przerażone, ile wysiłku zajęło mi zrozumienie tego. Czasami wydaje mi się, że jestem z innej planety. Cieszę się, że mogłem pomóc ci zrozumieć to szybciej. Kiedy to zobaczysz, jest to łatwe.

— William

2

Aby przekonwertować skierowany wykres na niekierowany wykres wykonaj następujące czynności: $D$ $G$

Numeruj węzły $D$
Utwórz dwa niekierowane wykresy , na tym samym zestawie wierzchołków co $G'$ $G''$ $D$
Dla każdej krawędzi , in dodaj krawędź do jeśli , w przeciwnym razie dodaj krawędź do $u$ $v$ $D$ $G'$ $u<v$ $G''$
G jest rozłącznym związkiem i $G'$ $G''$

Wykonując rozłączny związek, należy zadbać o to, aby był on odwracalny.

Przykład

— adrianN
źródło

To dobra próba i jest zgodna z wytycznymi, które miałem na myśli, ale odpowiedź nie działa, ponieważ odwrotność nie jest wyjątkowa. Na przykład wykres O <-> OOO zostanie przekonwertowany na wykres OO OO OO OO, ale wówczas ten ostatni mógł również pochodzić z ukierunkowanego wykresu O-> O O-> OOO, więc proces nie jest odwracalny.

— Heterotic

Dodałem zdjęcie, aby było wyraźniejsze.

— adrianN

-1

Co z funkcją tożsamości? Oznacza to, że każdy digraf może być postrzegany jako niekierowany, dwustronny wykres z jednakowymi rozmiarami partycji i odwrotnie.

— muede
źródło

Zakładam, że masz zamiar zakodować znak za pomocą wykresu . To nie działa, ponieważ nie radzi sobie z dwukierunkowymi krawędziami, a jeśli jest wynikiem odwrócenia wszystkich krawędzi w , wówczas i mają kodowanie izomorficzne, ale same niekoniecznie są izomorficzne.

G = (V, E)

$G=(V,E)$

(V \times {0, 1}, {(⟨ u, 0 ⟩, ⟨ v, 1 ⟩) ∣ (u, v) \in E})

$(V\times\{0,1\}, \{(\langle u,0\rangle, \langle v,1\rangle)\mid (u,v)\in E\})$

G^{'}

$G'$

G

$G$

G

$G$

G^{'}

$G'$

— David Richerby

-1

Oto dźgnięcie w tym:

Zamień informacje o kierunku na dodatkowe wierzchołki na niekierowanym wykresie. Innymi słowy, użyj dodatkowych wierzchołków na niekierowanym wykresie, aby „zakodować” informacje o kierunku. Na przykład dla każdego skierowanego wierzchołka z co najmniej jedną krawędzią dodaj liczbę nieukierowanych wierzchołków równą 1 + liczbę „przychodzących” krawędzi. Wierzchołki o zerowych krawędziach pozostają niezmienione.

Aby wykonać odwrotny kierunek, utwórz skierowany wierzchołek dla każdego wierzchołka, który ma 0 lub więcej niż 1 krawędź. (Wierzchołki z dokładnie jedną krawędzią są wierzchołkami „kodującymi kierunek”). Każda krawędź łącząca inny wierzchołek z wieloma krawędziami jest połączeniem na skierowanym wykresie. Teraz jest trudna część, dla której nie potrafię wyjaśnić algorytmu (ale myślę, że taki istnieje): musisz wydedukować kierunek strzałek, biorąc pod uwagę tylko liczbę strzałek przychodzących dla każdego wierzchołka.

Myślę, że podchwytliwa część przypomina grę w trałowie :-) Dowiedzieć się, gdzie bomby (nadchodzące krawędzie) mają liczbę sąsiadujących bomb dla każdego kwadratu (wierzchołka).

— Aaron
źródło

Co to jest „skierowany wierzchołek”? W każdym razie nie jest to jednoznacznie dekodowalne. Załóżmy, że do wierzchołka jest przymocowana wiązka wierzchołków stopnia-1 wraz z wiązką wierzchołków innych stopni. Jak byś powiedział, ile z nich reprezentuje przychodzące krawędzie od wierzchołków stopnia 1, a ilu koduje stopień ? W każdym razie rozwiązanie Saper jest trudne, rozwiązanie nie zawsze jest wyjątkowe i nie jest oczywiste, że można je w ogóle rozwiązać, gdy kwadraty niekoniecznie są ułożone w ładną siatkę.

x

$x$

x

$x$

— David Richerby

Przez „ukierunkowany wierzchołek” rozumiem wierzchołek na ukierunkowanym wykresie (w przeciwieństwie do równoważnego niekierowanego wykresu). Można odróżnić krawędzie „rzeczywiste” od krawędzi „kodujących stopnie”, ponieważ tylko wierzchołki „kodujące stopnie” mają jedną krawędź. To był powód „1 +” w moim opisie. Wierzę ci o minesweeperesque „podstępną część”. Nie wiem, czy to dokładnie ekwiwalent trałowca, ale wierzę, że może kopnąłem wiadro w dół drogi :-)

— Aaron

Nie do końca zrozumiałem twoje rozwiązanie, kiedy go przeczytałem, ale widzę, jak teraz działa. Sprytny!

— Aaron

Niech będzie wierzchołkiem na oryginalnym wykresie, który nie ma krawędzi wejściowych i dokładnie jednej krawędzi wyjściowej. Na zakodowanym wykresie pojawia się jako wierzchołek z dokładnie jedną krawędzią wychodzącą z niego. Jak odróżnić ten rodzaj wierzchołka stopnia-1 od rodzaju wierzchołka stopnia-1, który koduje stopień?

x

$x$

x

$x$

— David Richerby

Myślę, że teraz jest to „trałowiec-moot”, ale moim pomysłem było wzięcie ukierunkowanej krawędzi i przekonwertowanie jej na i . Zatem będzie miał dwie krawędzie, a nie 1. Każdy wierzchołek, który ma tylko 1 krawędź, koduje stopnie. ma dwa wierzchołki kodujące stopnie, wskazujące stopień 1. W tym prostym przykładzie dekodowanie jest łatwe, ponieważ wiemy, że są tylko dwa wierzchołki i mają one odpowiednio stopień 0 i 1, a zatem

(x, y)

$(x,y)$

(x_{0}, x), (x, y), (y, y_{0})

$(x_0,x), (x,y), (y,y_0)$

(y, y_{1})

$(y,y_1)$

x

$x$

y

$y$

(x, y)

$(x,y)$

— Aaron