2-összefüggő gráfok konstrukciója

OData támogatás
Konzulens:
Dr. Tapolcai János
Távközlési és Médiainformatikai Tanszék

A kommunikációs hálózatok különböző topológiája gráfokkal modellezhető. Az ilyen típusú hálózatban megköveteljük az összefüggőséget, hogy az egyes hálózati elemek kommunikálni tudjanak egymással. Azonban a hálózatban lehetnek hibák, amelyek tönkretehetik a folyamatos kommunikációt, így érdemes többszörösen összefüggővé tenni azokat. A hálózati topológia időről időre változik, ezek a változások azonban nem ronthatják el a hálózat tulajdonságait. Ezért szükségünk van olyan módszerekre, amelyekkel ezek a változások megvalósíthatók.

A dolgozat bevezetője után az első fejezetben gráfelméleti alapfogalmakkal ismerkedhetünk meg, amelyek segítenek bizonyos fogalmak és tételek megértésében, amik előkerülnek a dolgozat során. A második fejezet egyszerű gráfalgoritmusokat mutat be, amelyek segítenek a későbbi algoritmusok megértésében. A harmadik fejezet két részből áll. Az első fele a 2-összefüggő gráfok konstrukciójával foglalkozik, különösképp a gráfok lebontására koncentrálva. A 2-összefüggő gráfok lebontásához megismerkedünk a fülfelbontó algoritmussal, valamint bemutatjuk azt, hogyan alkalmazható a gráf lebontására. A harmadik fejezet második fele egy kis kitekintőt ad a 3-összefüggő gráfok konstrukciója felé. Ebben a részben azt szeretnénk megmutatni, hogy a 3-összefüggő gráfok is bizonyos szabályok szerint konstruálhatók, azonban jóval bonyolultabb módszerekkel, mint 2-összefüggő esetben.

A negyedik fejezetben kerül bemutatásra egy gráfokkal foglalkozó magyar fejlesztésű program, a LEMON (Library for Efficient Modeling and Optimization in Networks). Először az alapfunkcióival, valamint a használatával ismerkedhetünk meg, majd a LEMON segítségével implementált fülfelbontó algoritmus lépéseit és a kapott eredményeket követhetjük nyomon. A forráskód részletesen kommentezve a Függelékben található. Az utolsó, ötödik fejezetben a dolgozat rövid értékelése, és továbbfejlesztési lehetőségei találhatók.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.