Különböző gráfelméleti és gyakorlati alkalmazások kapcsán gyakran felmerül, hogy mennyire robusztus egy gráf, azaz ha elhagyjuk valamilyen részét, néhány pontját vagy élét, akkor hány és milyen komponensre esik a gráf. Például számítógéphálózatoknál, ha meghibásodik a rendszer egy része, mennyire marad mûködőképes a maradék rendszer. A robusztusság mérésére többféle módszer ismeretes, a két legismertebb a többszörös összefüggőség és a szívósság (toughness). A kutatás célja további ismereteket szerezni a különböző mérőszámok összefüggéseiről, kapcsolatukról a faktorokkal, Hamilton-körrel. Megvizsgálni, kiterjeszthetők-e ezek a definíciók hipergáfokra is.
Egy gráf k-szorosan összefüggő, ha akárhogyan is hagyunk el a gráfból k-nál kevesebb pontot, még összefüggő marad. Viszont k pont elhagyásával már akár nagyon sok komponensre eshet a gráf. Ennek a problémának a kezelésére született a szívós (tough) gráfok definíciója. 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 . Rögtön adódik, hogy egy t-szívós gráf 2t-szeresen összefüggő. Vannak más hasonló definíciók is. Különböző alkalmazásokban más változatok bizonyultak hasznosnak. Érdekes volna felderíteni ezek közötti pontos kapcsolatokat.
A szívósság legelőször a Hamilton körök elméletében merült fel. Ugyanis világos, hogy ha egy gráfban van Hamilton kör, akkor 1-szívós. Fordítva ez nem igaz, viszont hosszú ideje megoldatlan kérdése Chvátalnak, hogy van-e olyan t, amire igaz, hogy minden t-szívós gráfban van Hamilton-kör. Sokáig élt az a feltételezés, hogy létezik ilyen t, sőt t=2. Néhány évvel ezelőtt azonban 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átalán. Hasznos lenne megjavítani ezt a konstrukciót. Ennek egyik nehézsége, hogy be kell látni, hogy a konstruált gráfban nincs Hamilton-kör. Ennek bizonyításához volna szükség valami új ötletre.
Irodalom:
Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward (2006). "Toughness in graphs—a survey". Graphs and Combinatorics 22 (1): 1–35.
Bejelentkezés
