Bejelentkezés
 Fórum
 
 
Témakiírás
 
Katona Gyula Y.
Gráfok robosztussága

TÉMAKIÍRÁS

Intézmény: Budapesti Műszaki és Gazdaságtudományi Egyetem
informatikai tudományok
Informatikai Tudományok Doktori Iskola

témavezető: Katona Gyula Y.


A kutatási téma leírása:

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.

felvehető hallgatók száma: 1

Jelentkezési határidő: 2008-05-20

 
Minden jog fenntartva © 2007, Országos Doktori Tanács - a doktori adatbázis nyilvántartási száma az adatvédelmi biztosnál: 02003/0001. Program verzió: 1.2357 ( 2017. V. 15. )