Povečanje povezavne povezanosti grafa

Geršak, Jan (avtor), Žitnik, Arjana (mentor)

V diplomski nalogi obravnavamo problem povečanja povezavne povezanosti grafa. V prvem delu diplomske naloge predstavimo kaktusno reprezentacijo grafa in opišemo njeno konstrukcijo, za katero predstavimo tudi algoritem. V drugem delu diplomske naloge predstavimo povezavo med povezanostjo grafa in povezanostjo njegove kaktusne reprezentacije. S pomočo te povezave določimo spodnjo mejo za število potrebnih povezav za povečanje povezavne povezanosti grafa za ena in dokažemo, da je vedno doseŽena. Nato podamo algoritem, ki s pomočjo normalne kaktusne reprezentacije cikličnega tipa poveča povezavno povezanost grafa za ena. V tretjem delu diplomske naloge predstavimo splošno metodo razcepljanja povezav in jo uporabimo v Frankovem algoritmu za povečanje povezavne povezanosti grafa na dano vrednost. Tu tudi dokažemo Maderjev izrek, ki nam omogoča uporabo metode razcepljanja povezav za izvajanje Frankovega algoritma.

• Jezik: Slovenski jezik
• Ključne besede: graf, kaktusna reprezentacija, povečanje povezavne povezanosti, razcepljanje povezav, Frankov algoritem, Maderjev izrek.
• Vrsta gradiva: Diplomsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2018
• PID: 20.500.12556/RUL-105180
• Datum objave v RUL: 07.11.2018

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Edge-connectivity augmentation of a graph

Izvleček

In this thesis we consider the edge-connectivity augmentation problem. In the rst part of the thesis we present a cactus representation of a graph and describe its construction for which we present an algorithm. In the second part of the thesis we consider the relation between edge-connectivity of a graph and its cactus representation. Using this relation we give a lower bound for the least number of edges to be added to increase the edge-connectivity of a graph by one. We also prove that the lower bound is always achievable. Then we give an algorithm for edge-connectivity augmentation by one by applying properties of the cycle-type normal cactus representation. In the third part of the thesis we present general edge splitting method which is used in Frank's algorithm for solving edge-connectivity augmentation problem. We also prove Mader's theorem which is needed to prove niteness of edge splitting in Frank's algorithm.

• Ključne besede: graph, cactus representation, edge connectivity augmentation, edge splitting, Frank's algorithm, Mader's theorem.