Algoritmi za iskanje nekaterih podgrafov v grafuAmbrož, Gregor (Avtor) Vesel, Aleksander (Mentor) Pogozdenostpolni podgrafneodvisna množicaštirikotniktrikotnikklikaalgoritem za iskanje podgrafov.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.[G. Ambrož]20092010-02-01 00:45:49Diplomsko delo13097UDK: 51(043.2)COBISS_ID: 17466376NUK URN: URN:SI:UM:DK:GI5YFP4Asl