20.500.12556/DKUM-41208 Problem izomorfizma podgrafov ravninskih grafov Subgraph isomorphism problem in planar graphs 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. 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. izomorfizem podgrafov ravninski graf drevesna dekompozicija dinamično programiranje subgraph isomorphism planar graph tree decomposition dynamic programming true true false [A. Kelenc] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2013-08-11 22:30:37 2013-09-19 11:01:10 2022-05-04 03:06:42 2021-04-24 03:35:54 2013 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.172.2(043.2) 20051208 URN:SI:UM:DK:SCY8EUV9 MAG_Kelenc_Aleksander_2013.pdf MAG_Kelenc_Aleksander_2013.pdf 1 3BBF6BD76DEE270E7AC8764700FAC2A9 85d0a55676c4bfb51947e40cac20a77cad59836d6dea08021a4cbb52310ab1d3 1fa62e9e-7c0a-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=56846 Fakulteta za naravoslovje in matematiko 0 0 0