Generování grafů
| Thesis title in Czech: | Generování grafů |
|---|---|
| Thesis title in English: | Generating graphs |
| Key words: | grafy, generování |
| English key words: | graph, generation |
| Academic year of topic announcement: | 2011/2012 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 14.11.2011 |
| Date of assignment: | 14.11.2011 |
| Confirmed by Study dept. on: | 01.12.2011 |
| Date and time of defence: | 18.06.2012 00:00 |
| Date of electronic submission: | 21.05.2012 |
| Date of submission of printed version: | 23.05.2012 |
| Date of proceeded defence: | 18.06.2012 |
| Opponents: | doc. RNDr. Vít Jelínek, Ph.D. |
| Guidelines |
| 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ů. |
| References |
| 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á |