Çizgelerde Baskınlık Ve Total Baskınlık,

Proje Özeti

Çizge teorisinin bilgisayar bilimleri, endüstri mühendisliği, ulaşım ağları, enerji dağıtım ağları, biyoloji ve sosyal bilimler gibi pek çok alanda uygulaması vardır. Bilgisayar bilimlerinde çizgeler iletişim ağlarını, veri organizasyonunu, hesaplama akışını ve çeşitli kaynak ataması problemlerini temsil etmek için kullanılırlar. Baskınlık kavramı çizge teorisinde popüler bir konudur ve satranç oyunları ile sosyal ilişkilerde temsilci seçimi gibi uygulamaların yanı sıra veri yayımlama, kümeleme ve bilgisayar ağlarında hata toleransı ile güvenlik gibi konularda da pek çok uygulaması vardır.

Bir G=(V,E) çizgesi, sonlu bir düğüm kümesi V ve V’nin bazı 2 elemanlı alt kümeleri olan kenarlar kümesi E’den oluşan kombinatoryal bir nesnedir. Basit çizgelerde her kenar iki farklı düğümü birbirine bağlar ve her iki farklı düğümün arasında en fazla bir kenar bulunur. Eğer bir G=(V,E) çizgesinde her vÎV düğümü SÍV kümesinin bir elemanı ise ya da S’deki bir elemana bağlı ise S kümesine baskın küme denir. Eğer bir baskın kümenin hiçbir öz alt kümesi bir baskın küme değilse o baskın kümeye minimal denir. G’nin en küçük baskın kümesinin boyuna G’nin baskınlık sayısı denir. Baskınlık sayısını hesaplama, diğer bir deyişle minimum baskın kümeyi bulma problemi NP-zor’dur; yani bu problemi tam olarak polinom zamanda çözen bir algoritma bulmak P=NP olmadığı sürece mümkün değildir. Üst baskınlık sayısı ise en büyük minimal baskın kümenin boyunu ifade eder. Üst baskınlık sayısını hesaplamak da NP-zor bir problemdir. Henüz kanıtlanmamış bir sanıt olsa da P≠NP olduğuna dair bilim dünyasında kuvvetli bir önsezi vardır. Dolayısıyla NP-zor problemler için yapılabilecek en anlamlı yaklaşım, özel hallerini incelemektir; nitekim bu yakşalım literatürde yaygın olarak kullanılan yaklaşımdır. Bir çizgenin tüm minimal baskın kümelerinin boyu birbirine eşitse o çizgeye iyi-baskınlanmış denir; bu nedenle iyi-baskınlanmış bir çizgenin baskınlık sayısını ve üst baskınlık sayısını hesaplamak için (her iki sayı da birbirine eşit olduğu için) herhangi bir minimal baskın kümeyi bulmak yeterlidir. Herhangi bir maksimal bağımsız küme aynı zamanda bir minimal baskın küme olduğu için minimal bir baskın küme açgözlü bir şekilde herhangi bir maksimal bağımsız kümeyi bularak polinom zamanda elde edilebilir. Dolayısıyla, iyi-baskınlanmış çizgeler genel hali NP-zor olan baskınlık sayısını bulma probleminin polinom olarak çözülebildiği bir çizge sınıfıdır. Bu bilimsel motivasyona rağmen literatürde iyi-baskınlanmış çizgelerle ilgili çok az çalışma bulunmaktadır. Bu projede çeşitli iyi-baskınlanmış çizge sınıflarının karakterizasyonu ve tanınması gibi literatürde daha önce çalışılmamış konulara odaklanacağız.

Bir SÍV baskın kümesine G’nin S tarafından endüklenmiş alt çizgesinin izole düğümleri yoksa total baskın küme denir. Diğer bir deyişle, bir total baskın kümedeki her düğümün yine total baskın kümenin içinde olan en az bir komşusu bulunmalıdır. Total baskınlık konusu da pek çok araştırmacının ilgisini çekmiştir ancak bu konuda da hala pek çok açık soru bulunmaktadır. Örneğin, tüm minimal total baskınlanmış kümelerinin boyu aynı olan çizgeler anlamına gelen iyi-total-baskınlanmış çizgelerle ilgili olarak literatür taramamızda sadece iki çalışmaya rastlayabildik. Bu projede, iyi-total-baskınlanmış çizgelerin çeşitli alt sınıfları için yapısal karakterizasyonlar bulmayı amaçlıyoruz. Öte yandan, total baskınlık sayısının üst sınırı baskınlık sayısının iki katıdır. Çizgelerde baskınlık konusuyla ilgili dünyaca ünlü bilim insanı olan Michael Henning’in total baskınlıkla ilgili kitabında da açık bir soru olarak sunulduğu üzere, total baskınlık sayısının bu üst sınırı eşitlikle sağladığı çizgelerin birtakım çizge sınıfları için karakterizasyonu da ele almayı planladığımız bir diğer araştırma problemidir. Bu bağlamda, geçmiş çalışmalarımız üzerine temellendirerek daha büyük çizge aileleri için karakterizasyonlar yapmayı planlıyoruz.

Baskınlıkla ilgili diğer parametrelerden farklı olarak, üst baskınlık sayısının algoritmik yönleriyle ilgili olarak literatürde şaşırtıcı şekilde az çalışma bulunmaktadır. Bu projede üst baskınlığın zayıf kirişli (weakly chordal) çizgeler, permütasyon çizgeleri, tolerans çizgeleri ve ızgaralar (grids) gibi çizge sınıflarındaki hesaplama karmaşıklığını ele almayı amaçlıyoruz. İlave olarak, bu projede iyi-baskınlanmış çizgelerin genişletilmiş bir hali olan ve üst baskınlık sayısıyla baskınlık sayısı arasındaki farkın bir olduğu çizgeler anlamına gelen neredeyse-iyi-baskınlanmış çizgeler üzerine çalışmayı planlıyoruz. Literatür taramamızda bu tür çizgelerle ilgili sadece bir çalışmaya rastlayabildik. Neredeyse-iyi-baskınlanmış çizgelerin bazı alt sınıflarıyla ilgili karakterizasyonlar ve eğer mükünse polinom zamanlı tam algoritmalar tasarlamayı planlıyoruz.