Çizgelerde baskınlık ve soenerji
Domination and so-energy in graphs
- Tez No: 960001
- Danışmanlar: PROF. DR. SEZER SORGUN
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Çizge teorisi, baskın küme, baskınlık sayısı, NP-zorluk, soenerji, Graph theory, dominating set, domination number, NP-hardness, soenergy
- Yıl: 2025
- Dil: Türkçe
- Üniversite: Nevşehir Hacı Bektaş Veli Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
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.
Özet (Çeviri)
In this thesis, the concept of domination in graphs is examined in depth within the scope of graph theory, which is one of the fundamental areas of discrete mathematics. Graph theory is a mathematical discipline that models and analyzes the relationships between systems based on structures consisting of vertices (nodes) and edges connecting them. Graphs are considered powerful tools for understanding the structural properties of complex systems and for performing analyses on such systems. In this respect, graph structures are widely used in numerous fields such as social networks, communication and transportation systems, biological interaction networks, computer networks, and logistics planning. A significant part of the research conducted on graphs involves domination theory, which focuses on identifying subsets of vertices that can dominate or control the entire graph. Dominating sets are not only of theoretical interest but are also widely applied in practice. In particular, the concept of domination is effectively utilized in applications such as efficient resource allocation, communication network control, sensor placement problems, and bioinformatics analyses. The historical development of the domination concept reveals that it originates from the classical chess-based Five Queens Problem. In this problem, the goal is to place the minimum number of queens on a chessboard such that all squares are under threat. This idea has served as a foundational approach to domination problems in graphs. Over time, the concept has been expanded with the introduction of subtopics such as independent dominating sets, total domination, and connected domination. vii One of the fundamental problems related to domination is determining the size of the smallest dominating set in a graph, referred to as the domination number. This value is a key indicator of the efficiency of coverage in a graph. However, the complexity of this problem varies significantly depending on the type of graph. While the domination number can be computed efficiently in some specific graph classes (e.g., trees, cycles), it is generally NP-hard in arbitrary graphs, requiring high computational effort for exact solutions. Accordingly, the main objective of this thesis is to examine domination-related concepts in graphs from both theoretical and applied perspectives, thereby contributing to the existing literature and offering a framework for potential applications. Within this scope, the second chapter of the thesis introduces the basic concepts and definitions of graph theory. The third chapter presents various types of domination, along with related theorems, definitions, and bounds. The fourth and final chapter focuses on a graph invariant associated with dominating sets, known as soenergy, and includes soenergy computations on various graphs. Additionally, the study evaluates domination problems within the framework of computational complexity theory, emphasizing the challenges encountered in solving these problems and discussing approximation and parameterized algorithms developed as potential solutions. The findings of this research strengthen the theoretical foundations of domination in graph theory and provide a basis for future applications in diverse domains. In this respect, the study offers a meaningful contribution both in terms of mathematical theory and practical implementation in various scientific and engineering problems.
Benzer Tezler
- Çizgeler üzerinde baskınlık oyunları
Domination games on graphs
BETÜL ÇELİKTEN
Yüksek Lisans
Türkçe
2025
MatematikEskişehir Teknik ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. EMRAH AKYAR
- Çizgelerde süper baskınlık sayısının incelenmesi
Examining the number of super domination in graphs
YAĞMUR CEREN GÜVEN
Yüksek Lisans
Türkçe
2025
MatematikManisa Celal Bayar ÜniversitesiMatematik Ana Bilim Dalı
DOÇ. DR. GÖKŞEN BACAK TURAN
- Bazı gölge çizgelerde yarı-toplam baskınlık değerleri
Semi-total domination and semi-totalintersecting domination numbersin some graphs
NİDA NUR KOCATÜRK
- Çizgelerde baskın kümelere dayalı çıkarımsal metin özetleme
Dominating set-based extractive text summarization in graphs
ABDULSAMET AYDIN
Yüksek Lisans
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolVan Yüzüncü Yıl ÜniversitesiYapay Zeka ve Robotik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TANER UÇKAN