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.