Regisztráció és bejelentkezés

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