Részgráf izomorfia probléma vizsgálata

2021-2022 ősz

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: 2 fő