Çizgelerde baskın kümeyi bulmak için Malatya merkezilik değerlerini kullanan yeni bir yöntem önerisi
A new method proposed using Malatya centrality values to find the dominating set in graphs
- Tez No: 844534
- Danışmanlar: DR. ÖĞR. ÜYESİ FATİH OKUMUŞ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: Türkçe
- Üniversite: İnönü Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 44
Özet
Baskın küme problemi (dominating set problem), çizge teorisinde üzerinde oldukça çalışılan bir problem olup karmaşıklık olarak NP-Tam problemler grubuna girmektedir. Bundan dolayı günümüze kadar bu problemin çözümü için yapılan çalışmalar üç grupta toplanabilir. Sezgisel yöntemler, tam yöntemler ve yaklaşık yöntemler şeklinde gruplandırılabilirler. Sezgisel yöntemler sağlam olmayan her zaman aynı çizge için aynı sonucu veremeyen yöntemlerdir ve bu yöntemler olasılık tabanlı olup karmaşıklık analizleri çoğunlukla yapılmaz. İkinci grupta yer alan tam yöntemlerde ise, çözüm olabilecek bütün durumlar denenir ve ondan sonra çözüm ortaya konulur. Bu yöntemler çalışabildikleri çizgeler için minimum çözümü garanti ederler fakat zaman veya uzay karmaşıklıkları üstel olan yöntemlerdir. Son grupta yer alan yöntemler ise, minimum çözüm iddiaları olmayan yaklaşık çözüm noktasında da kesin iddiaları olmayan yöntemlerdir. Bu tez çalışmasında Malatya Merkezilik kavramının ikincisinin çizge teorisi problemlerinden olan Baskın Küme probleminin çözümü için kullanılabileceği iddiası ortaya konuldu. Malatya Merkezilik yönteminin kullanılması önerilecek yöntemin zaman ve uzay karmaşıklıklarının polinomsal olmasını sağlayacaktır. Aynı zamanda önerilen yöntemin bazı çizge grupları için minimum çözümü elde ettiği ortaya konuldu ve geriye kalan çizgelerde ise, minimum çözüme çok yakın sonuçlar elde edebildiği ortaya konulmuştur (minimum çözümden bir fazla düğümlü çözüm bulması gibi). Tez çalışmasında İkinci Malatya Merkezilik kavramı kullanıldı ve bu yöntemin ilk kullanıldığı tez çalışması oldu. İkinci Malatya Merkezilik kavramının baskın küme probleminin çözümü için kullanılabileceği yorumlarla gösterildikten sonra önerilen yöntemin kodlamaları gerçekleştirildi ve sonuçlar kodlaması gerçekleştirilen yöntemden elde edilmiştir.
Özet (Çeviri)
The dominating set problem is a widely studied problem in graph theory and falls into the group of NP-Complete problems in terms of complexity. Therefore, the studies carried out to date to solve this problem can be grouped into three groups. They can be grouped as heuristic methods, exact methods, and approximate methods. The heuristic methods are methods that are not robust and cannot always give the same result for the same graph, and these methods are probability*based and complexity analyses are often not performed. In the exact methdos, all feasible solutions are tried and then the solution is presented. These methods guarantee a minimum solution for the graphs they work with, but their time or space complexity is exponential. The methods in the last group are methods that do not have minimum solution claims, nor do they make definitive claims about the approximate solution. The concept of Second Malatya Centrality was used in the this thesis study, and it was the first thesis study in which this method was used. After showing with comments that the Second Malatya Centrality concept can be used to solve the dominating set problem, the implementation of the proposed method was carried out and the results were obtained from the implementation. In this thesis, is is claimed that the Second Malatya Centrality concept can be used to solve the Dominating Set Problem, which is one of the graph theory problems. It will ensure that the proposed method which is based on the Second Malatya Centrality conept, the time and space complexities of the propoed method are polynomial. It was revealed that the proposed method obtained the minimum solution for some graph groups, and in the remaining graphs, it was revealed that it could obtain results very close to the minimum solution (such as finding a solution with one more node than the minimum solution).
Benzer Tezler
- Çizgelerin diferansiyelinin hesaplanması
Computing the differential in graphs
AKIN KANLI
Yüksek Lisans
Türkçe
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül ÜniversitesiBilgisayar Bilimleri Ana Bilim Dalı
DOÇ. DR. ZEYNEP NİHAN BERBERLER
- Ç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
- Çizgelerde jeodezik baskın bütünlük değerinin incelenmesi
Investigation of geodetic dominant integrity in graphs
ŞEYMA ONUR
Yüksek Lisans
Türkçe
2024
MatematikManisa Celal Bayar ÜniversitesiMatematik Ana Bilim Dalı
DOÇ. DR. GÖKŞEN BACAK TURAN
- Spektral renormalizasyon grubu ile ölçek envaryant çizgeler üzerinde kritik üstellerin hesaplanması
Critical exponents on scale invariant networks by using spectral renormalization group
ASLI TUNCER ÖZDEMİR
Doktora
Türkçe
2016
Fizik ve Fizik Mühendisliğiİstanbul Teknik ÜniversitesiFizik Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE SİLİER