Teoria grafów

Trojan90 · Post autor: **Trojan90** » 23 lip 2008, o 16:08

Witam!
Jestem w klasie licealnej z matura międzynarodową i jednym z elementów programu matury międzynarodowej jest napisanie pracy z wybranego przedmiotu na max 4000 słów. Zdecydowałem się na matematykę i dział teorii grafów. Na razie wstępnie zorientowałem się w tym dziale, lecz muszę wybrać konkretne zagadnienie. Myślałem o kolorowaniu mapy (4 kolory i te sprawy) lub o algorytmach (na razie znam Kruskala, Prima oraz Dijkstry). Moja prośba brzmi następująco: chciałbym, żeby ktoś, kto jest zorientowany w teorii grafów, polecił mi jakieś CIEKAWE, INTERESUJĄCE (ważne!) zagadnienie z tego działu matematyki, które nadawałoby się do opisania. Część pracy poświęcę na odpowiedni wstęp do teorii grafów, a część na to zagadnienie, więc nie może być to małe zagadnienie, bo praca musi mieć prawie 4000 słów. Z góry dziękuję za wszelką pomoc.

dabros · Post autor: **dabros** » 23 lip 2008, o 22:43

polecam problem znajdowania cyklu (tudzież drogi, bo jest różnica) Eulera lub Hamiltona w grafach;
o ile problem Eulera posiada rozwiązanie, o tyle Hamiltona jest rozwiązany dla niektórych tylko grafów - tak więc problem warty rozważenia

Trojan90 · Post autor: **Trojan90** » 25 lip 2008, o 14:53

Może być ciekawe. Ma ktoś jeszcze jakieś propozycje?

mol_ksiazkowy · Post autor: **mol_ksiazkowy** » 25 lip 2008, o 18:23

Trojan90 napisal:

Może być ciekawe. Ma ktoś jeszcze jakieś propozycje?

Mozna tez-pomysł ciekawy-zajac sie ogolnym przedstawieniem grafu (macierz sasiedztwa, incydencji, etc), rysunkowa i inna. jak tez samym pojeciem grafu i jego "uogolnien" (tj np miltigraf, pseudograf , pseudograf mieszany, graf-faktor ) i pojeciami liczbowym zwiazanymi z grafem np (grubosc grafu. liczba chromatyczna, etc) Na koniec mozna dac kilka przykladow najczesciej spotykanych grafów, np graf Petersena, Herschela, K3,3 etc, Mozliwosci jest w zasadzie ogrom
zobacz tez link