Vlastnosti grafů velkého obvodu
Název práce v češtině: | Vlastnosti grafů velkého obvodu |
---|---|
Název v anglickém jazyce: | Properties of graphs with large girth |
Klíčová slova: | obvod, kubický graf, náhodné grafy, maximální řez, nezávislá množina, zlomkové obarvení |
Klíčová slova anglicky: | girth, cubic graph, random graphs, maximum cut, independent set, fractional coloring |
Akademický rok vypsání: | 2010/2011 |
Typ práce: | diplomová práce |
Jazyk práce: | angličtina |
Ústav: | Katedra aplikované matematiky (32-KAM) |
Vedoucí / školitel: | prof. RNDr. Daniel Kráľ, Ph.D., DSc. |
Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 02.11.2010 |
Datum zadání: | 02.11.2010 |
Datum a čas obhajoby: | 19.09.2011 00:00 |
Datum odevzdání elektronické podoby: | 04.08.2011 |
Datum odevzdání tištěné podoby: | 05.08.2011 |
Datum proběhlé obhajoby: | 19.09.2011 |
Oponenti: | prof. Jean Sébastien Sereni |
Zásady pro vypracování |
Student se seznámí s pravděpodobnostními metody používaný ke studiu vlastností grafů velkého obvodu a pokusí se pomocí těchto metod vyřešit některé otevřené problémy v této oblasti. |
Seznam odborné literatury |
N. Alon, J. Spencer: The probabilistic method, Wiley, 2008.
M. Molloy, B. Reed: Graph colouring and the probabilistic method, Springer, 2002. N.C. Wormald: Analysis of greedy algorithms on graphs with bounded degrees, , EuroComb '01 (Barcelona), Discrete Math. 273 (2003), 235-260. |