Povezanost grafov

diplomsko delo

Aljaž Nunčič (Avtor), Borut Robič (Mentor)

Povzetek

Povezanost grafa nam pove, koliko povezav oziroma vozlišč moramo odstraniti, da graf postane nepovezan. Tako poznamo povezavno povezanost in vozliščno povezanost grafa. Na začetku bom predstavil nekaj izrekov, ki se nanašajo na povezanost grafov. Nato bom opisal algoritme za preverjanje povezanosti grafov, ki služijo tudi kot orodje za preverjanje uspešnega razbitja grafov. V zadnjem delu pa bom najprej predstavil reševanje problema minimalnega prereza z algoritmom za največji pretok, nato pa še druge naprednejše in bolj prilagojene algoritme za ta problem. V zaključku bom povzel vse ključne ugotovitve. Diplomska naloga tako predstavlja osnovni pregled problema povezanosti grafov.

Ključne besede

graf;povezanost;povezavna povezanost;vozliščna povezanost;računalništvo in informatika;univerzitetni študij;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2019
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[A. Nunčič]
UDK:	004(043.2)
COBISS:	1538319299
Št. ogledov:	679
Št. prenosov:	228
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Graph Connectivity
Sekundarni povzetek:	Graphs connectivity tells us how many edges or vertices must be removed from a graph so that the graph becomes disconnected. This induces the notations of the edge and vertex connectivity of a graph. In this thesis, I will first present some of the theorems related to graph connectivity. Then I will describe algorithms for checking whether or not a graph is connected, which can also be used to check whether or not a graph has been successfully split. Next, I will show how the min-cut problem is solved using the algorithm for maximum flow. Then, I will continue with presentation of some advanced and more adapted algorithms for the considered problem. Finally, I will conclude the thesis with a summary of the key findings. The thesis is thus a basic overview of the problem of graph connectivity.
Sekundarne ključne besede:	graph;connectivity;edge connectivity;vertex connectivity;computer and information science;diploma;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000468
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	62 str.
ID:	11220281