Traktowanie grafów niekierowanych jako podkategorii grafów ukierunkowanych

10

Z grubsza, wykres bezkierunkowy jest bardzo podobny do wykresu skierowanego, gdzie dla każdej krawędzi (v, w) zawsze jest krawędź (w, v). To sugeruje, że akceptowalne może być wyświetlanie nieukierunkowanych wykresów jako podzestawu kierowanych wykresów (być może z dodatkowym ograniczeniem, że dodawanie / usuwanie krawędzi można wykonać tylko w pasujących parach).

Jednak podręczniki zwykle nie są zgodne z tym traktowaniem i wolą definiować nieukierunkowane wykresy jako osobną koncepcję, a nie podkategorię kierowanych wykresów. Czy jest jakiś powód tego?

max
źródło
2
Zauważ, że istnieją również „mieszane wykresy”: wykres, na którym można skierować krawędzie lub nie. W tym przypadku para skierowanych krawędzi nie jest tym samym, co nieukierowana krawędź między dwoma węzłami. Na przykład: rozważ ulice: możesz mieć parę ulic jednokierunkowych między dwoma punktami idącymi w przeciwnych kierunkach lub jedną ulicę dwukierunkową. Jest to ważne w niektórych przypadkach: np. Nie chcesz, aby urządzenie nawigacyjne informowało użytkownika o zawracaniu między dwiema ulicami jednokierunkowymi, jeśli na środku znajduje się bariera, podczas gdy może to być możliwe w jednokierunkowa dwukierunkowa ulica.
Bakuriu

Odpowiedzi:

8

Masz absolutną rację; jest to całkowicie poprawny sposób na wyświetlanie niekierowanych wykresów.

Czasami na niekierowanych grafach niektóre rzeczy stają się łatwiejsze i bardziej zrozumiałe. Na przykład nie musisz się martwić różnicą między słabo połączonymi a silnie połączonymi komponentami w niekierowanych grafach. Algorytmy dla grafów bezkierunkowych mogą czasami być bardziej wydajne lub prostsze niż gdybyśmy zastosowali odpowiedni algorytm dla grafów ukierunkowanych.

Tak więc: być może niektóre podręczniki wybierają takie postępowanie, ponieważ pozwala im to najpierw wprowadzić problem w (łatwiejszym) kontekście niekierowanych grafów, a następnie uogólnić na (trudniejszy) przypadek ukierunkowanych wykresów. To tylko spekulacja.

DW
źródło
3

Zobacz tę stronę, aby zapoznać się z przykładami problemów, dla których forma wykresu niekierowanego jest w rzeczywistości trudniejsza niż forma wykresu skierowanego. Obejmują one na przykład znalezienie cyklu ujemnej masy i zliczenie liczby cykli Eulera. Dla mnie te problemy wydają się być trudniejsze na niekierowanych grafach, ponieważ część zadania można sformułować jako wybranie odpowiedniego „kierunku” dla każdej krawędzi - co oczywiście jest „już dla nas zrobione”, gdy wykres jest skierowany.

j_random_hacker
źródło
1
No tak. Na przykład cykl Eulera, gdy jest zdefiniowany w kategoriach grafów ukierunkowanych, musiałby wymagać, aby „z każdej pary (v, w), (w, v)” nie użyto więcej niż jednej krawędzi - tworząc ideę przedstawienia wykresu niekierowanego jako digrafin mniej atrakcyjny.
maks.
0

Trudno jest zmotywować coś bardzo ogólnego; może to uprościć proofy i podręczniki, ale niekoniecznie łatwiejsze do zrozumienia i intuicyjnego naśladowania.
Ludzie zwykle bardziej intuicyjnie uczą się prostej koncepcji, a następnie uogólniają ją na coś bardziej abstrakcyjnego, niż definiują jakieś superogenerowane i abstrakcyjne koncepcje, a następnie tworzą poszczególne przypadki. To prawdopodobnie jeden z tych przypadków.

użytkownik541686
źródło