Graf acyklicyny a sortowanie topologiczne
-
- Użytkownik
- Posty: 106
- Rejestracja: 31 paź 2015, o 22:06
- Płeć: Kobieta
- Lokalizacja: Frankfurt
- Podziękował: 34 razy
Graf acyklicyny a sortowanie topologiczne
Mam do wykazania, ze w każdym grafie acyklicznym istnieje przynajmniej jedna opcja sortowania topologicznego. Jest to oczywiste, gdy się nad tym zastanowić, ale jak to wykazać "formalnie"?
-
- Użytkownik
- Posty: 318
- Rejestracja: 14 maja 2016, o 16:25
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Pomógł: 90 razy
Graf acyklicyny a sortowanie topologiczne
Już dawno się takim czymś nie zajmowałem, ale spróbuję pomóc.
Jak rozumiem, jest to graf skierowany. Należałoby wykazać, że w takim grafie istnieje wierzchołek, do którego nie dochodzi żadna krawędź. (*)
On będzie naszym pierwszym wierzchołkiem.
Następnie usuwamy ten wierzchołek z grafu, a więc rozażamy nowy graf o mniejszej o 1 liczbie wierzchołków. On będzie znów acykliczny, więc będzie można kontynuować proces, znajdując kolejne wierzchołki w kolejności. Ma to sens?
Odn. (*) Tak sobie myślę, że gdyby nie było takiego wierzchołka, to nie dałoby się uskutecznić sortowania topologicznego. Chyba, że rozważa się też nieskończone grafy.
Jak rozumiem, jest to graf skierowany. Należałoby wykazać, że w takim grafie istnieje wierzchołek, do którego nie dochodzi żadna krawędź. (*)
On będzie naszym pierwszym wierzchołkiem.
Następnie usuwamy ten wierzchołek z grafu, a więc rozażamy nowy graf o mniejszej o 1 liczbie wierzchołków. On będzie znów acykliczny, więc będzie można kontynuować proces, znajdując kolejne wierzchołki w kolejności. Ma to sens?
Odn. (*) Tak sobie myślę, że gdyby nie było takiego wierzchołka, to nie dałoby się uskutecznić sortowania topologicznego. Chyba, że rozważa się też nieskończone grafy.