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:
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 ...
źródło
Odpowiedzi:
Dla każdej skierowanej krawędzi dodaj nowe wierzchołki i zamień na krawędzie , , , , , .e=(x,y) ve1,…,ve5 e xve1 ve1ve2 ve1ve3 ve3ve4 ve4ve5 ve3y
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źve5 e=(x,y) ve4 ve4 ve3 ve3 ve1 ve2 ve1 ve2 ve1 x ve3 y (x,y) i usuń wierzchołki .ve1,…,ve5
źródło
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.
(Chciałbym zamieścić to jako komentarz do odpowiedzi Davida, ale nie mam wymaganych punktów reputacji).
źródło
Aby przekonwertować skierowany wykres na niekierowany wykres wykonaj następujące czynności:D G
Wykonując rozłączny związek, należy zadbać o to, aby był on odwracalny.
źródło
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.
źródło
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).
źródło