magistrsko delo
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: |
2013 |
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
|
Št. ogledov: |
1851 |
Št. prenosov: |
190 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
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 |