Kolorowanie grafu - artykuł

[wiedzmac]

Witam,
Mój nauczyciel zachęcił mnie do pisania pracy naukowej z matematyki na konkurs. Bardzo interesuje mnie matematyka dyskretna, a dokładniej teoria grafów, więc pomyślałem, że warto by było napisać coś o niej. Nie ukrywam, że jestem z tej dziedziny troszkę zielony. Moja główna przygoda z teorią grafów, to zadanka algorytmiczne ze spoja, czy OI. Znam tylko kilka podstawowych cech, zastosowań, czy algorytmów grafowych.

Wybrałem sobie dość oryginalny temat, tego jeszcze na tym konkursie nie było. Chciałbym napisać coś o kolorowaniu grafu. Czytając książkę, uznałem że to ciekawy temat i można się dużo nauczyć.
Tutaj mam do was prośbę. Moglibyście mi doradzić, co wypadało by napisać w takiej pracy?
Jakie ciekawe zagadnienia, przykłady można tam umieścić? Jaka literatura, czy strony www by mi się przydały?

Z góry dziękuje za pomoc i pozdrawiam,
WiedźMAC

[szw1710]

Bo ja wiem, co bym napisał? Ale od razu na myśl przychodzi mi tu twierdzenie Ramseya. Jest opisane w książce Lipskiego i Marka "Analiza kombinatoryczna". Orzeka ono m. in. że jeśli mamy graf pełny \(\displaystyle{ K_6}\) (tzn. każde dwa wiezchołki np. sześciokąta foremnego połączono odcinkiem) i pokolorowano krawędzie (odcinki) dwoma kolorami, to zawsze znajdzie się trójkąt pokolorowany jednym kolorem. Inna rzecz codo numeracji to np. lemat Spernera, mający bardzo ważne konsekwencje w topologii (dowód tw. Brouwera o punkcie stałym). Więc grafu związane są z kombinatoryką, tw. Ramseya ma konsekwencje w teorii grafów, a lemat Spernera wspomniałem, bo też z kombinatoryką się wiąże.

Mam wątpliwości czy to będzie praca naukowa. Bo przecież chyba nie masz zamiaru udowodnić swoich twierdzeń? A może się mylę.

[wiedzmac]

Mam wątpliwości czy to będzie praca naukowa. Bo przecież chyba nie masz zamiaru udowodnić swoich twierdzeń? A może się mylę.

Praca ma zawierać zagadnienia z literatury + moje przemyślenia i ciekawe pomysły, zadania.
Może niepoprawnie nazwałem ją naukową

[pawels]

Rzeczywiście wokół twierdzenia Ramsey'a pojawia się dużo ciekawych rzeczy. Sam czytałem kiedyś skrypt: (daje się go trywialnie wygooglać). Zawiera sporo teorii, ćwiczeń i zadań do rozwiązywania. Wydaja się mieć bardzo zróżnicowany poziom trudności, poczynając od liczenia \(\displaystyle{ R(3,3)}\), aż po problemy otwarte, więc chyba każda zainteresowana osoba znajdzie tam coś dla siebie.

[Ein]

Jeśli chodzi o kolorowanie grafów, to można by pokusić się o opisanie aspektów obliczeniowych (skoro miałeś jakieś doświadczenie w algorytmicznej teorii grafów). Chodzi np. o kwestie typu złożoność obliczeniowa 3COL i podobnych problemów (google i hasło: 3-colouring computational complexity) etc. Jednakże może to być za trudne dla szesnastolatka.

Na pewno zrozumiałe będą kwestie kolorowania map, czyli m.in. problem 4-kolorowania płaszczyzny (i jego komputerowy dowód). Ale nie musisz ograniczać się tutaj tylko do płaszczyzny. Ciekawie można opisać to, co się dzieje na torusie, płaszczyźnie rzutowej itd. Poszukaj pod hasłem: hipoteza Hadwigera (Hadwiger's conjecture; udowodniona jako twierdzenie Ringela-Youngsa).