Povečanje povezavne povezanosti grafa

Geršak, Jan (author), Ž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.

• Language: Slovenian
• Keywords: graf, kaktusna reprezentacija, povečanje povezavne povezanosti, razcepljanje povezav, Frankov algoritem, Maderjev izrek.
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2018
• PID: 20.500.12556/RUL-105180
• Publication date in RUL: 07.11.2018

Secondary language

• Language: English
• Title: Edge-connectivity augmentation of a graph

Abstract

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.

• Keywords: graph, cactus representation, edge connectivity augmentation, edge splitting, Frank's algorithm, Mader's theorem.