Gimnazjalistka rozłożyła resztę świata na łopatki

Jubileuszową - XX - edycję Konkursu Prac Młodych Naukowców Unii Europejskiej (EUCYS - European Union Contest for Young Scientists), który odbył się pod koniec września 2008 w Kopenhadze, wygrała nie tylko praca z matematyki, nie tylko polskiej autorki, ale na dodatek uczennicy gimnazjum (!) z Warszawy - Magdaleny Bojarskiej. Pokonała nią 77 innych prac nadesłanych z 30 krajów i otrzymała nagrodę w wysokości 7 tys. euro.

Pozostałe dwie pierwsze nagrody zdobyli ex aequo:

• Brytyjka Elisabeth Muller w dziedzinie geologii, za wnioskowanie o budowie Księżyca na podstawie analizy meteorytu księżycowego,
• Słowak Martin Tkác w dziedzinie techniki, za projekt urządzenia do grawitacyjnego rozładunku materiałów sypkich z wagonów kolejowych.

Laureatów I nagród prezentujemy na zdjęciach poniżej.

Wyróżnienie w tym samym konkursie otrzymał Paweł Maryniak z LO "Carolinum" w Nysie za pracę nt. "Orientacji i pamięci przestrzennej u karaczanów madagaskarskich". Dzięki tym osiągnięciom bilans udziału Polaków w tym najbardziej prestiżowym na świecie konkursie badawczym dla uczniów zwiększył się do 4 pierwszych, 6 drugich, 6 trzecich miejsc i 11 wyróżnień.

Magda Bojarska - stypendystka Krajowego Funduszu na rzecz Dzieci (patrz www.fundusz.org), obecnie uczennica XIV LO w Warszawie - napisała pracę z teorii grafów będąc jeszcze w Gimnazjum Przymierza Rodzin w Warszawie,  pod kierunkiem swojego szkolnego nauczyciela, matematyka z Uniwersytetu Warszawskiego - Wojciecha Guzickiego - specjalisty w zakresie matematyki dyskretnej. Jej praca wygrała Konkurs Uczniowskich Prac z Matematyki organizowany przez miesięcznik "Delta" oraz eliminacje krajowe do EUCYS. Wszyscy po cichu liczyli, że zdobędzie również jedną z głównych nagród w europejskim finale.

Prace zgłaszane na Europejski Konkurs Prac Młodych Naukowców muszą
być oryginalnymi wynikami naukowymi, tzn. muszą zawierać rozwiązanie problemu dotychczas nierozwiązanego lub istotnie nowe, ulepszone rozwiązanie problemu już znanego. Praca Magdy została bardzo wysoko oceniona przez recenzenta konkursu ogólnopolskiego, członka Polskiej Akademii Nauk - prof. Łuczaka z Uniwersytetu Adama Mickiewicza w Poznaniu, wybitnego specjalistę z teorii grafów. Napisał on, że reprezentuje ona wysoki poziom prac magisterskich i powinna być opublikowana w jakimś czasopiśmie naukowym.

Tematem zwycięskiej rozprawy były "Cykle Hamiltona w uogólnionych grafach Halina". Graf to zbiór wierzchołków połączonych krawędziami. Cyklem nazywamy zamkniętą ścieżkę złożoną z niepowtarzających się krawędzi. Jeśli taka ścieżka przechodzi przez wszystkie wierzchołki grafu, przez każdy tylko jeden raz, to graf nazywamy hamiltonowskim. Do badania takich grafów sprowadza się m.in. tzw. problem komiwojażera, polegający na ustaleniu najkrótszej trasy przejazdu do wszystkich klientów. Do dziś nie jest znany żaden oszczędny algorytm wyznaczania takiej trasy dla dowolnego grafu (jest to jeden z tzw. problemów millenijnych ogłoszonych w 2000 roku, za rozwiązanie których przewidziana jest nagroda w wysokości miliona dolarów za każdy). Dlatego matematycy próbują rozwiązać to zagadnienie dla szczególnych rodzajów grafów. Magda zrobiła to dla tzw. grafów Halina.

Grafy Halina powstają z drzew (czyli grafów, w których nie ma cykli) przez połączenie ich liści (tzn. wierzchołków, do których dochodzi dokładnie jedna krawędź) krawędziami tworzącymi okrąg. O takich grafach wiadomo było, że istnieją w nich cykle Hamiltona. Magda uogólniła to pojęcie wprowadzając definicję grafów Halina stopnia n (gdy liście drzewa są rozmieszczone na n rozłącznych okręgach). Następnie dla stopnia 2 udowodniła warunek konieczny i wystarczający bycia hamiltonowskim i podała algorytm pozwalający szybko wyznaczyć szukany cykl.

Drugie twierdzenie udowodnione przez Magdę dotyczyło istnienia cykli Hamiltona w grafach Halina przechodzących przez zadane z góry krawędzie grafu. Było ono znane już wcześniej, ale Magda podała bezpośredni dowód kombinatoryczny, znacznie prostszy od tego tego stosowanego dotychczas.

Skróconą wersję pracy Magdaleny Bojarskiej opublikowana w miesięczniku Delta nr 5/2008 można znaleźć tutaj.

Poniżej prezentujemy zdjęcia z ceremonii wręczenia nagród w Kopenhadze.