Traktowanie grafów niekierowanych jako podkategorii grafów ukierunkowanych

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?

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.

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.

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.