20.500.12556/DKUM-13097 Algoritmi za iskanje nekaterih podgrafov v grafu Algorithms for searching some subgraphs in a graph Diplomska naloga je sestavljena iz treh poglavij. V prvem poglavju predstavimo osnovne pojme teorije grafov in algoritmov. Predstavimo definicijo časovne in prostorske zahtevnosti ter obravnavamo predstavitev grafov s seznami sosedov in matriko sosednosti. V naslednjem poglavju podamo predpostavke in predstavimo pogozdenost, ki nastopa v časovni zahtevnosti algoritmov, ki poiščejo določene podgrafe v nekem grafu. Te algoritme podrobneje obravnavamo v zadnjem poglavju. V tretjem poglavju opišemo enostavno strategijo, ki je uporabna za različne probleme,ki jim je skupno iskanje podgrafov v danem grafu. Z uporabo te strategije opišemo naslednje štiri algoritme. Prvi algoritem poišče vse trikotnike grafa G v času O(a(G)m). Drugi algoritem poišče vse štirikotnike v času O(a(G)). Ker je pogozdenost grafa G, a(G), kvečjemu 3 v ravninskem grafu G, oba algoritma potrebujeta linearni čas za ravninske grafe. Tretji algoritem poišče vse polne podgrafe Kl , v času O(la(G)l-2m). Četrti algoritem pa poišče vse klike v času O(a(G)m) za kliko. Pokazali bomo,da vsi ti algoritmi potrebujejo linearni prostor. Poglavje zaključimo z algoritmom za iskanje trikotnikov v grafu G,realiziranim v programskem jeziku Borland Delphi oz. z izdelanim računalniškim programom,ki ga prilagamo na zgoščenki k diplomskem delu. The thesis consists of three chapters. In the first chapter basic concepts in theory of graphs and algorithms are presented. We explain the definition of time and space complexity and deal with the presentation of graphs by means of adjacency lists and adjacency matrix. The following chapter provides assumptions and introduces arboricity occuring in time complexity of algorithms which search for specific subgraphs in a graph. These algorithms are dealt with in greater detail in the last chapter of the thesis. In the third chapter we describe asimple strategy useful for different problems which have a common search for subgraphs in a given graph. Using this strategy the following four algorithms are described. The first algorithm looks for all triangles of graph G in time O(a(G)m). The second algorithm searches all quadrangle in time O(a(G)). Due to the arboricity of graph G, which is at the utmost 3 in planar graph G, both algorithms need linear time for planar graphs. The third algorithm finds all complete subgraphs Kl, in time O(la(G)l−2m) and the fourth algorithm looks for all cliques in time O(a(G)m) for the clique. We will demonstrate that all these algorithms need linear space. The chapter concludes with analgorithm for the search of triangles in graph G realized in the programming language Borland Delphi i.e. a computer programme, which is enclosed on a compact disc in the thesis. Pogozdenost polni podgraf neodvisna množica štirikotnik trikotnik klika algoritem za iskanje podgrafov. Arboricity complete subgraph independent set quadrangle triangle clique subgraph listing algorithm true true false [G. Ambrož] Slovenski jezik Angleški jezik Diplomsko delo 2010-02-01 00:45:49 2010-03-03 14:13:56 2023-11-20 13:41:27 2023-11-21 03:08:32 2009 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 17466376 URN:SI:UM:DK:GI5YFP4A UNI_Ambroz_Gregor_2010.pdf UNI_Ambroz_Gregor_2010.pdf 1 C191EEDF6475176382BD1DCD0DA3881A c83f9da3a2032a08068596574441024e0cc5181e59ab644ae7fdda9d1d01f5fa d19c9ea0-7c03-11eb-bb7a-00155d0001ca 20.500.12556/dkum/2aca9988-dfb7-449d-9231-867925ab0527 https://dk.um.si/Dokument.php?lang=slv&id=13008 Fakulteta za naravoslovje in matematiko 0 0 0