SPRAWOZDANIE ZE SPOTKANIA
Z PRODZIEKANEM WYDZIAŁU MATEMATYKI STOSOWANEJ AGH
Dnia 19 listopada 2010 miało miejsce już kolejne spotkanie z Prodziekanem Wydziału Matematyki Stosowanej AGH, doktorem Rafałem Kalinowskim. Zajęcia odbyły się w ramach realizacju zadań projektu „ Kierunki matematyczno – przyrodnicze kluczem do zrozumienia świata”. Wzięli w nich udział uczniowie pracujący w grupach M -1, M – 6, F – 1 i F – 4. Gościem spotkania była Dyrektor LO Nr I, pani Grażyna Kałamaga.
Wykład dotyczył teorii grafów, działu matematyki dyskretnej zajmującego się między innymi włanościami grafów. Pokazał również zastosowanie tej teorii w matematyce i innych dziedzinach wiedzy, a szczególnie w informatyce.
Jak to się zaczęło?Historia mostów królewieckich.
W Królewcu, na rzece Pregole, są dwie wyspy połączone ze sobą i z brzegami za pomocą siedmiu mostów.Mieszkańcy Królewca lubili spacerować po mostach na rzece.Takie zwykłe spacerowanie po jakimś czasie znudziło im się i zaczęli zastanawiać się, czy jest taka trasa , 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. Napisali więc do Leonharda Eulera, szwajcarskiego matematyka, fizyka i astronoma (XVIII w). Euler pokazał, że nie istnieje rozwiązanie tego zadania.
Tą historyczną opowieścią rozpoczął swój wykład pan dr Kalinowski .Nastęnie przybliżył słuchaczom podstawowe terminy i twierdzenia teorii grafów.
- Określenie grafu, wierzchołek, krawędź i stopień grafu.
- Droga w grafie, droga prosta, droga zamknięta.
- Graf spójny.
- Cykl Eulera.
- Rozwiązanie problemu mostów królewieckich
Na mapie Królewca tworzymy graf. Wierzchołkami tego grafu są poszczególne lądy ,
a krawędziami mosty. Trzeba w tym grafie znaleźć cykl Eulera, co jest niemożliwe.
W opublikowanej w 1736 roku pracy Euler sformułował pierwsze twierdzenie teorii grafów. Wynika z niego, że warunkiem koniecznym na istnienie cyklu Eulera w grafie jest to, aby każdy wierzchołek grafu z wyjątkiem najwyżej dwóch miał parzysty stopień. Są cztery wierzchołki stopnia nieparzystego, stąd graf nie posiada cyklu Eulera.
Twierdzenie Eulera brzmi obecnie:
W grafie można znaleźć cykl Eulera wtedy i tylko wtedy, gdy graf jest spójny i każdy jego wierzchołek jest parzysty.
Pozostałe zagadnienia poruszone w wykładzie:
6. Graf planarny.
- Kolorowanie krawędzi grafu.
- Kolorowanie map. Twierdzenie o czterech kolorach.
Wystąpienie wykładowcy zakończyły gromkie brawa. Kolejne spotkanie z gościem AGH wiosną przyszłego roku.
Opracowanie Ewa Dębicka.