Çizgelerde baskınlık ve soenerji

Bu tez çalışmasında, ayrık matematiğin temel alanlarından biri olan çizge teorisi kapsamında, çizgelerde baskınlık kavramı derinlemesine incelenmiştir. Çizge teorisi; düğümler (noktalar) ve bu düğümleri birbirine bağlayan kenarlardan oluşan yapılara dayalı olarak, sistemler arasındaki ilişkileri modelleyen ve analiz eden matematiksel bir disiplindir. Çizgeler, karmaşık sistemlerin yapısal özelliklerini anlamada ve bu sistemler üzerinde analizler gerçekleştirmede son derece güçlü bir modelleme aracı olarak kabul edilmektedir. Bu yönüyle çizge yapıları; sosyal ağlar, iletişim ve ulaşım sistemleri, biyolojik etkileşim ağları, bilgisayar ağları ve lojistik planlama gibi çok sayıda alanda kullanılmaktadır. Çizgeler üzerinde yapılan çalışmaların önemli bir kısmını oluşturan baskınlık kuramı, çizgedeki belirli nokta alt kümeleri aracılığıyla tüm çizgenin kapsanmasını ya da kontrolünü sağlayan yapıları incelemektedir. Baskın kümeler, sadece teorik anlamda değil, aynı zamanda pratik uygulamalarda da yaygın biçimde kullanılan kavramlardır. Baskın küme kavramının tarihsel gelişimi incelendiğinde, bu konunun kökeninin Beş Vezir Problemi olarak bilinen satranç tabanlı klasik bir probleme dayandığı görülmektedir. Bu problemde amaç, bir satranç tahtasına mümkün olan en az sayıda vezir yerleştirerek tüm karelerin kontrol edilmesini sağlamaktır. Bu fikir, çizgelerdeki baskınlık problemlerine temel oluşturan bir yaklaşımdır. Zamanla bu kavram, bağımsız baskın kümeler, toplam baskınlık, bağlantılı baskınlık gibi birçok alt başlıkta detaylandırılmıştır. Baskınlıkla ilgili temel sorulardan biri, çizgedeki en küçük baskın kümenin boyutunu yani baskınlık sayısını belirlemektir. Bu sayı, çizgenin kapsama açısından verimliliğini ölçen önemli bir değişkendir. Ancak bu problemin zorluk derecesi, çizgenin türüne göre önemli ölçüde değişmektedir. Bazı özel çizge sınıflarında (örneğin ağaçlar, döngüler) baskınlık sayısı etkin algoritmalarla bulunabilirken, genel çizgelerde bu problemler çoğunlukla NPzor sınıfında yer almakta ve çözüm süreçleri yüksek hesaplama maliyeti gerektirmektedir. Bu bağlamda tez çalışmasının temel amacı; çizgelerde baskınlıkla ilgili kavramları teorik ve uygulamalı yönleriyle birlikte ele alarak hem literatüre katkı sunmak hem de olası uygulama alanları açısından çözümleyici bir yaklaşım ortaya koymaktır. Bu kapsamda tezin ikinci bölümünde çizge teorisinin temel kavram ve tanımları sunulmuş, üçüncü bölümde çeşitli baskınlık türleri ile ilgili teoremler, tanımlar ve sınırlar ele alınmıştır. dördüncü ve son bölümde ise çizgelerdeki baskın kümelerle ilişkili bir değişmez olan soenerji kavramı açıklanmış ve çeşitli çizgeler üzerinde soenerji hesaplamaları gerçekleştirilmiştir. Ayrıca çalışmada, çizge problemlerinin hesaplama karmaşıklığı teorisi açısından değerlendirilmesi yapılmış, özellikle baskınlık problemlerinin çözümünde karşılaşılan zorluklar ve bu problemlere yönelik geliştirilen yaklaşık ve parametrik algoritmalara da değinilmiştir. Elde edilen sonuçlar, çizge teorisi kapsamında baskınlık kavramına ilişkin hem teorik temelleri güçlendirmekte hem de farklı alanlarda yapılacak ileri uygulamalar için zemin oluşturmaktadır. Bu yönüyle çalışma, hem matematiksel kuramsal katkı hem de çeşitli mühendislik ve bilimsel problemlerdeki uygulama potansiyeli açısından anlamlı bir bütünlük sunmaktadır. Anahtar Kelimeler: Çizge teorisi, baskın küme, baskınlık sayısı, NP-zorluk, soenerji