-
Algoritmi za iskanje nekaterih podgrafov v grafu : diplomsko deloAmbrož, Gregor, [1984-]Diplomsko delo 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 pod grafe 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 pod grafov 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 pod grafe 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.Type of material - undergraduate thesis ; adult, seriousPublication and manufacture - Maribor : [G. Ambrož], 2009Language - slovenianCOBISS.SI-ID - 17466376
Author
Ambrož, Gregor, [1984-]
Other authors
Vesel, Aleksander
Topics
Univerzitetna in visokošolska dela |
matematika |
algoritmi |
grafi |
podgrafi |
pogozdenost |
polni podgrafi |
neodvisne množice |
štirikotniki |
trikotniki |
klika |
diplomska dela |
mathematics |
algorithms |
graphs |
subgraphs |
forestation |
full subgraphs |
independent masses |
quadrilaterals |
triangles |
click |
theses
Library | Call number – location, accession no. ... | Copy status |
---|---|---|
Miklošič Library FPNM, Maribor | M DIPL 51 AMBROŽ G. Algoritmi IN: 920100010 |
available - reading room |
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Ambrož, Gregor, [1984-] | |
Vesel, Aleksander | 11666 |
Select pickup location:
Material pickup by post
Notification
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.