Problem realizacije grafov, različice in algoritmi

diplomsko delo

Ljubica Simovska (Avtor), Uroš Čibej (Mentor)

Povzetek

Pri delu z grafi pogosto potrebujemo predstavitev grafa iz danega zaporedja stopenj, bodisi za ustvarjanje vzorčnih modelov pri analizi omrežij ali za iskanje izomerov iste molekulske formule. Zanima nas, ali za dano zaporedje pozitivnih celih števil obstaja graf s tem zaporedjem stopenj. Če tak graf obstaja, si želimo ustvariti eno takšno realizacijo. Vendar pa v resničnem svetu ni vedno potrebna katerakoli realizacija grafa. Pogosto postavimo različne omejitve na graf, zato se problem omeji na povezane grafe, drevesa, dvodelne grafe in usmerjene grafe. Za reševanje problema naštevanja uporabimo izčrpno metodo in predstavimo naše rezultate za naštevanje vseh realizacij za dano zaporedje stopenj, ob upoštevanju različnih omejitev grafov.

Ključne besede

realizacija grafa;zaporedje stopenj;problem naštevanja;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2023
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[L. Simovska]
UDK:	519.17:004(043.2)
COBISS:	168446467
Št. ogledov:	115
Št. prenosov:	9
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Graph realization problem, variations and algorithms
Sekundarni povzetek:	Many times when working with graphs, we need a graph representation from a given degree sequence. Whether that is for generating a sample network for world models or to find the different structural isomers of the same molecular formula. For a given sequence of positive integers, we would like to know if a graph with that degree sequence exists, if so we want to construct a realization. But in the real world, we are not always interested in any such graph realization. Many times we require different restrictions on the graph. We thus limit the problem to connected graphs, trees, bipartite graphs and directed graphs. With an exhaustive method we then tackle the enumeration problem. We present our results for the enumeration of all realizations for a given degree sequence, with the different graph restrictions in mind.
Sekundarne ključne besede:	graph realization;degree sequence;enumeration problem;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Teorija grafov;Matematika;Računalništvo;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	55 str.
ID:	19933589