szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 20 maja 2016, o 14:39 
Użytkownik

Posty: 108
Lokalizacja: Frankfurt
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"?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 20 maja 2016, o 14:56 
Użytkownik

Posty: 491
Lokalizacja: Sucha/Wrocław
Trzeba wskazać sposób takiego sortowania i pokazać że jest ono poprawne.
Góra
Mężczyzna Offline
PostNapisane: 20 maja 2016, o 18:17 
Użytkownik

Posty: 322
Lokalizacja: Toruń
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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Drzewo, graf  Karol12  1
 Graf spójny - minimalna ilość krawędzi  pingwindyktator  4
 Kolorowanie wierzchołków (graf z petlami)  sputnik1957  3
 Graf pełny trójdzielny.  klaudiak  1
 Graf eulerowski a półeulerowski  Crave  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl