Generování grafů

• Název práce v češtině: Generování grafů
• Název v anglickém jazyce: Generating graphs
• Klíčová slova: grafy, generování
• Klíčová slova anglicky: graph, generation
• Akademický rok vypsání: 2011/2012
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 14.11.2011
• Datum zadání: 14.11.2011
• Datum potvrzení stud. oddělením: 01.12.2011
• Datum a čas obhajoby: 18.06.2012 00:00
• Datum odevzdání elektronické podoby: 21.05.2012
• Datum odevzdání tištěné podoby: 23.05.2012
• Datum proběhlé obhajoby: 18.06.2012
• Oponenti: doc. RNDr. Vít Jelínek, Ph.D.

Zásady pro vypracování

Při testování a porovnávání grafových algoritmů a při ověřování hypotéz v teorii grafů potřebujeme testovací množiny grafů s danými vlastnostmi. Při návrhu pravděpodobnostních algoritmů je také často nutné umět generovat náhodné grafy s předepsanými vlastnostmi a pravděpodobnostní distribucí (nejčastěji uniformní). Cílem práce je prostudovat a shrnout známé techniky pro generování či náhodný výběr grafů z důležitých tříd (regulární grafy, rovinné grafy, ...) a pokusit se o jejich aplikaci pro další takové třídy; případně také jejich praktická implementace a porovnání různých přístupů.

Seznam odborné literatury

Béla Bollobás - Random graphs, Cambridge University Press, 2001.
Jeong Han Kim, Van H. Vu - Generating random regular graphs, Annual ACM, 2003
Donald E. Knuth - The Stanford GraphBase: A Platform for Combinatorial Computing.
další časopisecká