Částečné k-stromy na plochách

• Název práce v češtině: Částečné k-stromy na plochách
• Název v anglickém jazyce: Partial k-trees on surfaces
• Akademický rok vypsání: 2008/2009
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. RNDr. Jan Kratochvíl, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 11.11.2008
• Datum zadání: 11.11.2008
• Datum a čas obhajoby: 15.09.2009 00:00
• Datum odevzdání elektronické podoby: 15.09.2009
• Datum proběhlé obhajoby: 15.09.2009
• Oponenti: doc. RNDr. Pavel Valtr, Dr.

Zásady pro vypracování

Student se sznámí s pojmem "k-strom" a "částečný k-strom", nastuduje důkaz tvrzení "Každý rovinný částečný 3-strom je podgrafem rovinného 3-stromu" a zjistí, zda je toto tvrzení možno zobecnit pro jiná k a jiné plochy.

Seznam odborné literatury

Arnborg, S.; Corneil, D. & Proskurowski, A. (1987), "Complexity of finding embeddings in a k-tree", SIAM Journal on Matrix Analysis and Applications 8 (2): 277?284
Arnborg, S. & Proskurowski, A. (1989), "Linear time algorithms for NP-hard problems restricted to partial k-trees", Discrete Applied Mathematics 23 (1): 11?24

Předběžná náplň práce

Úkolem je zjistit, pro která čísla k a které plochy S je pravda, že každý částečný k-strom vnořitelný na plochu S je podgrafem úplného k-stromu vnořitelného na plochu S.

Předběžná náplň práce v anglickém jazyce

The goal is to find for which numbers k and which surfaces S it is true that every partial k-tree embeddable on S is a subgraph of a partial k-tree embeddable on S.