izpis_h1_title_alt

Povečanje povezavne povezanosti grafa
Geršak, Jan (Avtor), Žitnik, Arjana (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (487,21 KB)

Izvleček
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 (mb11)
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2018
Število ogledov:32
Število prenosov:11
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na: Bookmark and Share

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.

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj