Algoritmusok a gráfelméletben

Abstract

Diplomamunkám során a graceful címkézést vizsgáltam meg különböző gráfcsaládoknál. Először is ismertettem mely algoritmussal lehet könnyen belátni kevés csúcsú gráfok esetén, hogy létezik graceful címkézése a gráfoknak, majd ezeket a gráfokat implementáltam. Az implementálás a SageMath programcsomag segítségével történt, amelynek alapja a Python programozási nyelv. Többek között foglalkoztam speciális körgráfokkal, illetve fagráfokkal is, de vizsgáltam olyan gráfcsaládot is, amelyek két komponensből álltak. Végül a gráfok szomszédsági mátrixaként azt vizsgáltam, hogy hogyan néznek ki azok a gráfok, amelyeknek a szomszédsági mátrixa módosított Hadamard-mátrix, illetve ezek graceful tulajdonságát vizsgáltam.