Hlavní stránka > Výsledky hledání: keywords:"podgraf"
Hledej:
Tipy pro vyhledávaní :: Rozšířené hledání
Hledej ve sbírkách:
Seřadit podle: Zobrazit výsledky: Výstupní formát:
Národní úložiště šedé literatury Nalezeno 2 záznamů.  Hledání trvalo 0.00 vteřin. 
Souvislost a resilience grafů
 Novotná, Jitka ; Pangrác, Ondřej (vedoucí práce) ; Šámal, Robert (oponent)
Graf je k-resilientní, jestliže pro každý jeho vrchol existují lokální routovací tabulky takové, že podle nich lze z každého vrcholu dojít do jednoho označeného jako cíl. Existuje domněnka, že k-resilience je ekvivalentní hranové (k+1)-souvislosti. Toto dokazujeme pro hranově 3-souvisle grafy a hranově 4-souvislé rovinné triangulace. Při důkazu používáme nezávislé orientované kostry. Dvě kostry jsou nezávislé, pokud žádnou hranu nepoužijí ve stejné orientaci. Pro k=3,4 ukazujme, že graf má k nezávislých koster, právě tehdy když je hranově k-souvislý. Kostry hledáme konstruktivně pomocí redukcí částí grafu. Některé redukce mohou být použity i pro obecný k-souvislý případ. Powered by TCPDF (www.tcpdf.org)
Úplný záznam
Rozložitelnost grafů na souvislé podgrafy
 Musílek, Jan ; Pangrác, Ondřej (vedoucí práce) ; Fiala, Jiří (oponent)
V roce 2003 prezentovali J. Barát a C. Thomassen na konferenci Eurocomb definici a základní výsledky z oblasti hranové rozložitelnosti grafů. Rozložitelností rozumíme možnost pokrytí množiny hran grafu disjunktními souvislými podgrafy předepsaných velikostí. Graf je rozložitelný, existuje-li takové pokrytí pro všechny možné předepsané velikosti podgrafů. Naše práce se zabývá především rozložitelností hranovou, o níž je známo méně výsledků, než o vrcholové rozložitelnosti. Dokážeme, že rozložitelnost je implikovaná existencí dominujícího tahu a tedy i hranovou 4-souvislostí. Dále se zabýváme omezenou variantou rozložitelnosti, definujeme pojem spektra rozložitelnosti a dokazujeme o něm několik tvrzení platných pro všechny grafy. Omezenou rozložitelnost pak podrobněji zkoumáme na některých specifických třídách grafů.
Úplný záznam

Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.
Digitální repozitář :: Hledej :: Nový záznam :: Personalizace :: Nápověda
Powered by Invenio v1.1.2
Spravuje admin.invenio@techlib.cz
Tato stránka je dostupná také v následujících jazycích:
Česky  English