Hamiltonovské vlastnosti permutačních grafů
| Thesis title in Czech: | Hamiltonovské vlastnosti permutačních grafů |
|---|---|
| Thesis title in English: | Hamiltonian properties of permutation graphs |
| Academic year of topic announcement: | 2017/2018 |
| Thesis type: | diploma thesis |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. RNDr. Jiří Fiala, Ph.D. |
| Author: |
| Guidelines |
| Cílem práce je prozkoumat souvistlost mezi existencí hamiltonovských struktur (cest, cyklů, pokrytím cestami apod.) a existencí řezů na permutačních grafech, případně na příbuzných třídách.
Strukturální vlstnosti by měly být východiskem pro návrh algoritmů. |
| References |
| Matoušek, Nešetřil: Kapitoly s diskrétní matematiky
Harary: Graph Theory Diestel: Graph Theory relevantní časopisecká literatura |
| Preliminary scope of work |
| U příbuzné třídy intervalových grafů je podobný vztah znám. Pro permutační grafy je známo několik algoritmů, některé jsou překvapivě jednoduché pro zápis, ale netriviální pro dokazování korektnosti (opakované prohledávání do šířky).
Pěkné téma pro studenta nebo studentku, kteří mají rádi - rychlé netriviální grafové algoritmy, jejich složitost, - třídy grafů se zajímavou geometrickou i kombinatorickou reprezentací. |