20.500.12556/RUL-150175 Problem realizacije grafov, različice in algoritmi Graph realization problem, variations and algorithms 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. 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. realizacija grafa zaporedje stopenj problem naštevanja graph realization degree sequence enumeration problem true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2023-09-14 12:50:07 2023-09-14 12:50:10 2023-11-20 10:01:36 0000-00-00 00:00:00 2023 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 36761 168446467 Simovska_Ljubica_-_Problem_realizacije_grafov,_razlicice_in_algoritmi.pdf Simovska_Ljubica_-_Problem_realizacije_grafov,_razlicice_in_algoritmi.pdf 1 7BDE96BBF0B0E3D99BEE8F9119E52DCE b378ba616294e8b9591443a1075ccae2e6d65cd52fed4236b71c056b4b003241 79a5b579-52ec-11ee-b233-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=174737 Fakulteta za računalništvo in informatiko Fakulteta za matematiko in fiziko 0 0 0