Original title: Souvislost a resilience grafů
Translated title: Souvislost a resilience grafů
Authors: Novotná, Jitka ; Pangrác, Ondřej (advisor) ; Šámal, Robert (referee)
Document type: Master’s theses
Year: 2015
Language: eng
Abstract: [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)
Keywords: connectivity; graph; resilience; spanning trees; subgraph; graf; kostry; podgraf; resilience; souvislost

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/81835

Permalink: http://www.nusl.cz/ntk/nusl-351529


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses