Részgráf-izomorfia vizsgálata dinamikus gráfokon

A gráf- és a részgráf-izomorfia vizsgálatának számos alkalmazási területe van kezdve a szociális hálózatok analíizisétől az áramkörök tervezéséig. 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. A problémára azonban számos state-of-the-art megoldás létezik, melyek különböző módokon próbálják minimalizálni az adott eljárás lépésszámát.

A valóságban léteznek olyan gráfok is, melyek időben változhatnak. Folyamatosan új csúcsok, élek keletkezhetnek és törlődhetnek. A dolgozat célja a részgráf-izomorfia vizsgálata ilyen dinamikusan változó gráfok esetén.

szerzők

• 
  Sári László
  Villamosmérnöki szak, mesterképzés
  mesterképzés (MA/MSc)
• 
  Lauter Kinga Csilla
  Villamosmérnöki szak, mesterképzés
  mesterképzés (MA/MSc)

konzulens

• 
  Dr. Szegletes Luca
  egyetemi adjunktus, Automatizálási és Alkalmazott Informatikai Tanszék