20.500.12556/RUL-105180 Povečanje povezavne povezanosti grafa Edge-connectivity augmentation of a graph 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. 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. graf kaktusna reprezentacija povečanje povezavne povezanosti razcepljanje povezav Frankov algoritem Maderjev izrek. graph cactus representation edge connectivity augmentation edge splitting Frank's algorithm Mader's theorem. true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2018-11-07 12:39:57 2018-11-07 12:40:00 2022-08-17 03:47:07 0000-00-00 00:00:00 2018 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 22263 Gersak_Jan_-_Povecanje_povezavne_povezanosti_grafa.pdf Gersak_Jan_-_Povecanje_povezavne_povezanosti_grafa.pdf 1 ABD6D145D1594E8F09171BB8A0DAB085 2b033e7d9ec1b1e06cfb4f320797649de6d2fc3e8906b41db29ee86fec8a8caf 22435554-a1b6-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=115784 Fakulteta za računalništvo in informatiko 0 0 0