magistrsko delo
Aleksander Kelenc (Avtor), Andrej Taranenko (Mentor)

Povzetek

V problemu izomorfizma podgrafov imamo podana dva grafa G in H. Za njiju je potrebno ugotoviti, ali graf G vsebuje podgraf, ki je izomorfen grafu H. Problem je v splošnem NP-poln. V magistrskem delu se omejimo na problem izomorfizmov podgrafov ravninskih grafov. V prvem poglavju so opisani osnovni pojmi in definicije, ki jih potrebujemo v nadaljevanju. V drugem poglavju so najprej opisani drevesna dekompozicija, delni izomorfizem, meja delnega izomorfizma in konsistentnost. Potem je opisan postopek za učinkovito iskanje izomorfizmov podgrafov v ravninskih grafih z omejeno drevesno širino. Nadalje predstavimo, kako pokrijemo poljuben ravninski graf s podgrafi, ki imajo omejeno drevesno širino. Na koncu je podan algoritem za iskanje izomorfizmov podgrafov ravninskih grafov, ki teče v linearnem času za vsak povezan graf H z omejeno velikostjo.

Ključne besede

ravninski grafi;podgrafi;izomorfizem;drevesna širina;dinamično programiranje;magistrska dela;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
Založnik: [A. Kelenc]
UDK: 519.172.2(043.2)
COBISS: 20051208 Povezava se bo odprla v novem oknu
Št. ogledov: 1851
Št. prenosov: 190
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Subgraph isomorphism problem in planar graphs
Sekundarni povzetek: In the subgraph isomorphism problem two graphs G and H are given as input. We must determine whether G contains a subgraph isomorphic to H. In general, the problem is NP-complete. In this thesis we present a linear algorithm for the subgraph isomorphism problem in planar graphs. The first section describes the basic concepts and definitions. The second chapter describes the tree decomposition, partial isomorphism, partial isomorphism boundary and consistency. Then it describes how to efficiently search for subgraph isomorphisms in planar graphs with bounded tree-width. Furthermore, we present how to cover any planar graph with subgraphs that have bounded tree-width. At the end, we present an algorithm for subgraph isomorphism problem in planar graphs, which runs in linear time for any connected graph H of a constant size.
Sekundarne ključne besede: planar graph;subgraphs;isomorphism;tree width;dynamic programming;master theses;
URN: URN:SI:UM:
Vrsta dela (COBISS): Magistrsko delo/naloga
Komentar na gradivo: Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani: 34 f.
ID: 8726840