Zacznijmy od tego, czym w ogóle jest graf.
Wiemy, że w pierwszym skojarzeniu większości przychodzą nam na myśl kółeczka z podstawówki, gdy porządkowaliśmy różne przedmioty według jakiegoś klucza. My zajmiemy się jednak "grafem" jako zagadnieniem matematyki dyskretnej. Brzmi tajemniczo? No to zaczynamy!
W uproszczeniu graf to zbiór wierzchołków, które mogą być połączone krawędziami w taki sposób, że każda krawędź kończy i zaczyna się w którymś z wierzchołków.
Gdy znane nam już jest pojęcia grafu, warto zainteresować się zagadką, którą rozpoczyna się prawie każdy wykład z Teorii Grafów:
W osiemnastym wieku mieszkańcy Królewca lubili spacerować po mostach na rzece Pregole, których mieli w mieście siedem. Plan mostów pokazuje rysunek.
Ale takie zwykłe spacerowanie po jakimś czasie im się znudziło, i zaczęli zastanawiać się czy jest taka trasa spacerowa, która przechodzi przez każdy most dokładnie raz, żadnego nie omija, i pozwala wrócić do punktu wyjścia.
Nie potrafili sami rozwiązać tego problemu, więc napisali do znanego już wtedy matematyka Leonharda Eulera. Euler pokazał, że nie istnieje rozwiązanie tego zadania. (Jeśli wejdzie się po raz trzeci na wyspę, nie ma możliwości wyjścia z niej.)
Można tę sytuację przedstawić jako graf o wielokrotnych krawędziach:
Trzeba w tym grafie znaleźć cykl Eulera, czyli cykl przechodzący przez wszystkie wierzchołki i wszystkie krawędzie tego grafu, ale przez każdą krawędź tylko raz.
W opublikowanej w 1736 roku pracy Euler sformułował pierwsze twierdzenie teorii grafów, które dziś zapisujemy następująco:
W grafie można znaleźć cykl Eulera wtedy i tylko wtedy, gdy graf jest spójny i każdy jego wierzchołek ma parzysty stopień.
Znając to twierdzenie, zawsze można stwierdzić, czy łamigłówka typu "narysuj figurę, nie odrywając ołówka od kartki" ma rozwiązanie.
http://pl.wikipedia.org/wiki/Graf_(matematyka)
http://www.cs.put.poznan.pl/aurbanski/prezentacja-Teoriagrafowdlamalolatow.pdf
Dla osób szczególnie zainteresowanych polecamy ten wykład:
http://math.uni.lodz.pl/~marmaj/Files/grafyLic.pdf
Jeśli przeczytaliście artykuł ze zrozumieniem, to już wiecie, że nie da się rozwiązać naszego czwartkowego problemu architekta :D Czasem nawet matma nie pomoże...;)
Pozdrawiamy, Matblog! :D
Brak komentarzy:
Prześlij komentarz