Részgráf izomorfia probléma vizsgálata
Dolgozatomban a részgráf izomorfia problémáját mutatom be. A gráfok és a részgráf keresés több területen is hasznosítható, például bioinformatikában, szociális hálók esetén az adatok feldolgozásánál, gyógyszerkutatásnál, illetve áramkörök tervezésénél.
A gráfok csúcspontokból és csúcspontokat összekötő élekből állnak. A részgráf izomorfia azt jelenti, hogy G1 és G2 gráfokat nézve van-e olyan G2’részgráfja G2-nek, amelyik izomorf G1-gyel, azaz létezik egy-egyértelmű megfeleltetés (bijekció) G2’ és G1 csúcsai és élei között. Ez a probléma NP-teljes, vagyis nem ismerünk polinomiális idejű algoritmust a megoldására, így fontos a lehető legjobb keresési módszer megtalálása, főleg nagy gráfok esetén.
Dolgozatomban Julian R. Ullmann 1976-os algoritmusát, Luigi P. Cordella és munkatársai 2004-es VF2 algoritmusát, Jüttner Alpár és Madarasi Péter 2018-as VF2++ algoritmusát, valamint Myoungji Han és munkatársai 2019-es, dinamikus programozáson alapuló DAF algoritmusát mutatom be és hasonlítom össze különböző gráf adatbázisokon, ezeken megvizsgálom működésüket, teljesítményüket.
szerző
-
Lauter Kinga Csilla
Mérnök informatikus szak, alapképzés
alapképzés (BA/BSc)
konzulens
-
Dr. Szegletes Luca
egyetemi adjunktus, Automatizálási és Alkalmazott Informatikai Tanszék
