Problem izomorfizma podgrafov ravninskih grafov

magistrsko delo

Aleksander Kelenc (Author), Andrej Taranenko (Mentor)

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2013
Typology:	2.09 - Master's Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[A. Kelenc]
UDC:	519.172.2(043.2)
COBISS:	20051208
Views:	1851
Downloads:	190
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Subgraph isomorphism problem in planar graphs
Secondary abstract:	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.
Secondary keywords:	planar graph;subgraphs;isomorphism;tree width;dynamic programming;master theses;
URN:	URN:SI:UM:
Type (COBISS):	Master's thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	34 f.
ID:	8726840