Problem realizacije grafov, različice in algoritmi

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2023
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[L. Simovska]
UDC:	519.17:004(043.2)
COBISS:	168446467
Views:	115
Downloads:	9
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Graph realization problem, variations and algorithms
Secondary abstract:	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.
Secondary keywords:	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;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	55 str.
ID:	19933589