Diplomová práce na MFF UK

prosinec 1999

Tato práce se zabývá spojovacím problémem v teorii grafů. Mějme orientovaný graf G a množinu C uspořádaných dvojic vrcholů grafu, která představuje začátky a konce plánovaných cest. Z každého a do každého vrcholu je plánována maximálně jedna cesta. Množinu C nazveme spojitelnou, jestliže se dvojice dají spojit hranově disjunktními cestami. Graf G se nazývá spojitelný, jestliže je spojitelný pro každou množinu C.

V této práci jsme zjistili, že všechny de Bruinovy grafy Bnk, kde n<=2k-3, jsou nespojitelné. Navíc graf B32 také není spojitelný. Permutace REVERSE+, která se řadí k těžším zadáním, je spojitelná na všech grafech Bn2, pro n>2.