Leírás
SZTE, TTIK, Bolyai Intézet, Kombinatorika szeminárium
Absztrakt. A kisvilág gráfok vizsgálatában az egyik alapvető kérdés, hogyan osztályozhatóak a pontjaik, mit jelentenek az osztályok, mennyire gyorsan kaphatók meg stb. A klaszterezők jobbára azt célozzák, hogy a klasztereken belül sok, köztük kevés él húzódjon. Ún. szociális hálózatokban ez megfelelő és a kapott eredmények jók. Technológiai hálózatok esetén más a helyzet és ez a terület kevésbé fejlődött. A pollinátor ill. bolt-beszállító páros gráf modell alapján újfajta klaszterezési szempontokat javaslunk, amelyek bizonyos feltételeket teljesítő színezések színosztályain alapulnak.
Ha adott egy $H$ páros gráf, akkor $G$ olyan jó színezéseit tekintjük, amelyekben bármely két színosztály között a $H$ nem jelenik meg feszített részgráfként. A magyarázó erő maximalizálása céljából minimális színnel akarunk színezni, ezt $\chi_H(G)$-vel jelöljük. Ahogy lenni szokott, a legtöbb esetben NP-teljes problémákhoz jutunk, bár néhány esetben van egyszerű megoldás.