Gráfok robusztusságának vizsgálata

Boros Benedek
bboros@math.bme.hu

Szívósság, a robusztusság egyik mérőszáma

Definíció: Egy gráf t-szívós, ha akárhogyan is hagyunk el S ponthalmazt a gráfból, nem esik több komponensre mint ((|S |)/( t)) .

Chvátal megoldatlan kérdése

Kérdés: Létezik-e olyan t, amire igaz, hogy minden t-szívós gráf tartalmaz Hamilton-kört?
Sejtés:  Sokáig élt az a feltételezés, hogy létezik ilyen t, sõt t = 2.

A sejtés cáfolata

2000-ben született egy konstrukció: olyan gráfot adtak, melyben nincs Hamilton-kör, viszont közel (9/4)-szívós. Ebből következik, hogy t ≥ (9/4), ha létezik egyáltalán.
A konstrukció egy olyan kis 8 pontú gráfon alapszik, aminek a szívóssághoz hasonló mérőszáma nagy.

A program célja

A program ehhez a gráfhoz hasonló "kicsi" gráfok vizsgálatát, kicsi és szívós gráfok keresését végezné.