Souvislost a resilience grafů
| Název práce v češtině: | Souvislost a resilience grafů |
|---|---|
| Název v anglickém jazyce: | Graph connectivity and resilience |
| Klíčová slova: | graf, podgraf, souvislost, resilience, kostry |
| Klíčová slova anglicky: | graph, subgraph, connectivity, resilience, spanning trees |
| Akademický rok vypsání: | 2014/2015 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | RNDr. Ondřej Pangrác, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 18.01.2015 |
| Datum zadání: | 26.01.2015 |
| Datum potvrzení stud. oddělením: | 29.01.2015 |
| Datum a čas obhajoby: | 15.09.2015 09:00 |
| Datum odevzdání elektronické podoby: | 30.07.2015 |
| Datum odevzdání tištěné podoby: | 31.07.2015 |
| Datum proběhlé obhajoby: | 15.09.2015 |
| Oponenti: | doc. Mgr. Robert Šámal, Ph.D. |
| Zásady pro vypracování |
| Student se v práci bude zabývat problémy resilience a resilientního směrování v grafech. Tyto otázky jsou blízké souvislosti grafů. Jde o nalezení přechodových funkcí ve vrcholech grafu, které následně umožňují, po odebrání nějaké podmnožiny hran, dosažení cílového vrcholu bez dalšího prozkoumávání struktury grafu.
Metody pro řešení problému mohou zahrnovat využití vlastností k-souvislých grafů, hledání disjunktních koster a koster s omezenými průniky apod.. Student should study problems related to the resilience of graphs and resilient routings. The topic is closely related to the graph connectivity. The goal is to a mappings on the edges incident with each vertex whose enable to a given target vertex after removing a subset of edges of restricted size. Techniques used to reach a solution can exploit properties of k-connected graphs, finding disjoint spanning trees of a graph and spanning trees with restricted intersections. |
| Seznam odborné literatury |
| W. T. Tutte: On the problem of decomposing a graph into n connected factors (1961)
A. Frank: On disjoint trees and arborescences (1978) S. Fujishige: A note on disjoint arborescences (2010) C. Király: Algorithms for finding a rooted (k,1)-edge-connected orientation (2013) |
| Předběžná náplň práce |
| Student se v práci bude zabývat problémy resilience a resilientního směrování v grafech. Tyto otázky jsou blízké souvislosti grafů. Jde o nalezení přechodových funkcí ve vrcholech grafu, které následně umožňují, po odebrání nějaké podmnožiny hran, dosažení cílového vrcholu bez dalšího prozkoumávání struktury grafu. |
| Předběžná náplň práce v anglickém jazyce |
| Student should study problems related to the resilience of graphs and resilient routings. The topic is closely related to the graph connectivity. The goal is to a mappings on the edges incident with each vertex whose enable to a given target vertex after removing a subset of edges of restricted size. |