Részgráf izomorfia probléma vizsgálata
2021-2022 tavasz
Nincs megadva
Téma leírása
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.
Maximális létszám:
1 fő