Povečanje povezavne povezanosti grafaGeršak, Jan (Avtor) Žitnik, Arjana (Mentor) grafkaktusna reprezentacijapovečanje povezavne povezanostirazcepljanje povezavFrankov algoritemMaderjev izrek.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.20182018-11-07 12:39:57Diplomsko delo/naloga105180VisID: 22263sl