Název:
Kružnice a párování v grafech
Překlad názvu:
Circuits and matchings in graphs
Autoři:
Tesař, Karel ; Pangrác, Ondřej (vedoucí práce) ; Šámal, Robert (oponent) Typ dokumentu: Bakalářské práce
Rok:
2013
Jazyk:
cze
Abstrakt: O grafu řekneme, že je k-linkovaný, pokud pro každých k dvojic jeho vrchol· existují navzájem disjunktní cesty, které dané dvojice spojují. Existuje vztah mezi k-linkovaností a vrcholovou souvislostí grafu. V této práci hledáme vztah mezi vrcholovou souvislostí grafu a vlastností, že každých k jeho disjunktních hran leží na společné kružnici. Tento problém se dá řešit pomocí k-linkovanosti. Naším cílem je dosáhnout lepších odhad· na souvislost, resp. jiných postačujících podmínek než těch, které jsou známe pro k-linkovanost. 1
Klíčová slova:
grafy; k-linkované grafy; kružnice; párování; souvislost; circuit; connectivity; graph; k-linked graph; matching