Název: Souvislost a resilience grafů
Překlad názvu: Souvislost a resilience grafů
Autoři: Novotná, Jitka ; Pangrác, Ondřej (vedoucí práce) ; Šámal, Robert (oponent)
Typ dokumentu: Diplomové práce
Rok: 2015
Jazyk: eng
Abstrakt: [eng] [cze]
A graph is k-resilient if it is possible to construct local routing tables for each vertex such that we can reach a specified destination vertex from anywhere in the graph. There is a conjecture that k-resilience is equivalent to (k+1)-connectivity. We prove this for 3-edge-connected graphs and 4-edge-connected planar triangulations. In the proof we use independent directed spanning trees. Two spanning trees are independent if they share no common edge with the same direction. For k=3,4 we show that a graph has k independent spanning trees if and only if it is k-edge-connected. We search for the spanning trees constructively through reductions of parts of the graph. Some of these reductions can also be used in a general k- connected case. Powered by TCPDF (www.tcpdf.org) 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)
Klíčová slova: graf; kostry; podgraf; resilience; souvislost; connectivity; graph; resilience; spanning trees; subgraph

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/81835

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-351529


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce