Graflarda Roma baskınlık sayısı

Bir graf G=(V,E), V tepeler kümesi ve E ayrıtlar kümesi olacak şekilde, tepe ikililerinden oluşan bir küme ikilisidir. Zedelenebilirlik, bir G grafı birleştirilmemiş bir graf olana kadar bazı tepe veya ayrıtların kaldırılmasına karşı grafın dayanıklılığıdır. Graf teorisinde, zedelenebilirlikle ilgili birçok parametre vardır. Son yıllarda dikkat çeken bir graf teorisi parametresi graflarda baskınlıktır. Graflarda birçok baskın küme modelleri vardır. Bu tezde, graflarda özel bir baskınlık türü olan Roma baskınlığı üzerine çalışılmıştır. Yapılan çalışmada literatürde henüz Roma Baskınlık sayıları yer almayan bazı grafların Roma Baskınlık sayıları hesaplanarak, hesaplama sonuçları genelleştirilmiş ve genel sonuçlar ispatları ile verilmiştir. Bu tez, beş bölümden oluşmaktadır. İlk olarak graf teorisinin temellerinin nasıl atıldığına, bilinen uygulama alanlarına ve bazı zedelenebilirlik ölçümlerine ayrıntılı olarak değinilmiştir. Bilinen ölçüm türlerinden olan baskınlık sayısı ile Roma baskınlık sayısı ele alınmıştır. Bununla birlikte, baskınlık sayısını literatüre kazandıran satranç problemi ve Roma baskınlık sayısını literatüre kazandıran Roma baskınlığı problemi hakkında bilgilere yer verilmiştir. İkinci bölümde graf teorisinin temellerinin oturduğu tanım ve teoremler ayrıntılı bir şekilde verilmiştir. Üçüncü bölümde, materyal ve yöntemler ile graflarda baskınlık, Roma baskınlığı ve Mycielski inşası ile bir grafın Mycielski grafı kavramları açıklanmış ve bir örnek ile konuya ışık tutulmuştur. Dördüncü bölümde, kuyruklu yıldız graf, çift kuyruklu yıldız graf ve tarak graflarda Roma baskınlık sayısına ve bunların Mycielski inşası yöntemi ile elde edilen Mycielski graflarının Roma baskınlık sayılarına ilişkin elde edilen veriler, teoremler ve ispatlar halinde verilmiştir. Ayrıca, herhangi bir graf için Roma baskınlık sayısını hesaplamayı sağlayan Roma baskınlığı algoritması da bu bölümde sunulmuştur. Son bölümde ise çalışmadan elde edilen sonuçlara ve önerilere yer verilmiştir.