On equimatchable graphs and well-indumatched graphs
Eşiteşlenebilir çizgeler ve iyi-indüklenmiş çizgeler üzerine
- Tez No: 767355
- Danışmanlar: PROF. DR. SİBEL ÖZKAN, PROF. DR. DİDEM GÖZÜPEK KOCAMAN
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Endüklenmiş modüller, Eşleşme, Grafikler, Rastgele ormanlar, Induced modules, Coupling, Graphics, Random forests
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Gebze Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bu tez, çizge teorisindeki sorunları, çoğunlukla bir grafiğin eşleşmesini araştırır. Grafikteki her maksimum eşleşme bir maksimum eşleşme ise, bir grafiğe {eşiteşleştirilebilir} denir. Birçok araştırmacı eşiteşleştirilebilir çizgeler üzerinde bazı yapısal ve algoritmik sonuçlar sağladılar. Özellikle, üçgensiz eşiteşleştirilebilir çizgelerde bazı kısmi sonuçlar elde ettiler. Bu tezde, ilk önce üçgensiz eşiteşleştirilebilir çizgelerdeki sonuçları, bu tür çizge ailelerinin yapısını tanımlayarak, eşiteşleştirilebilir üçgensiz çizgelerin tam karakterizasyonunu sağlayacak şekilde genişletiyoruz. Bu karakterizasyon, verilen iki parçalı olmayan bir çizgenin eşiteşleştirilebilir ve üçgensiz olup olmadığını tanıyan doğrusal bir zaman algoritması verir. Ayrıca, literatürde eşiteşleştirilebilir iki parçalı çizgeler için yapısal olarak çok fazla bilgi sağlamayan ya da sadece bazı kısmi spnuçlar sağlayan karakterizasyonlar vardır. Kenarlarından birinin çıkarılmasıyla elde edilen her çizgenin eşiteşleştirilemez olması durumunda, eşiteşleştirilebilir bir çizge {kenar-kritik} olarak adlandırılır. Bu tezde, öncelikle, genel eşiteşleştirilebilir iki parçalı çizgeler yerine, kenar-kritik eşeşleştirilebilir iki parçalı çizgelerin yapısına odaklanmanın yeterli olduğunu gösteriyoruz. Daha sonra, kenar-kritik eşiteşleştirilebilir iki parçalı çizgeler için yapısal bir karakterizasyon sağlıyoruz. Çizgedeki her maksimum indüklenmiş eşleşme bir maksimum indüklenmiş eşleşme ise, bu çizgeye iyi-indüklenmiş denir. Literatürde iyi-indüklenmiş asiklik çizgelerin bir karakterizasyonunu ve iyi-indüklenmiş tek döngülü çizgeler üzerinde de bazı kısmi sonuçlar vardır. Sözde orman, her bağlı bileşenin en fazla bir döngü içerdiği, yani her bağlı bileşenin tek döngülü bir çizge veya bir ağaç olduğu bir çizgedir. Bu tezde, son olarak tek döngülü iyi-indüklenmiş çizgelerle ilgili sonuçları, çizge ailelerinin yapısının belirleyerek, iyi-indüklenmiş sahte ormanların tam bir karakterizasyonunu sağlayarak genişletiyoruz.
Özet (Çeviri)
This thesis investigates problems in graph theory, mostly matchings of a graph. A graph is called {equimatchable} if every maximal matching in the graph is a maximum matching. Many researchers provided some structural and algorithmic results on equimatchable graphs; particularly, some authors provided some partial results on equimatchable graphs with no triangle, in other words, equimatchable triangle-free graphs. In this thesis, we first extend these particular results by providing a full characterization of equimatchable triangle‐free graphs by identifying the structure of such graph families. This characterization yields a linear time algorithm that recognizes whether a given non-bipartite graph is equimatchable and triangle-free. Furthermore, some authors characterized equimatchable bipartite graphs, which does not provide a structural insight, whereas some authors provided only a partial characterization for equimatchable bipartite graphs. An equimatchable graph is called {edge-critical} if every graph obtained by the removal of one of its edges is not equimatchable. We first point out that it is sufficient to focus on the structure of edge-critical equimatchable bipartite graphs instead of the general equimatchable bipartite graphs. Hence, in this thesis, we provide a structural characterization for edge-critical equimatchable bipartite graphs. A graph is called {well-indumatched} if every maximal induced matching in the graph is a maximum induced matching. In the literature, some authors provided a characterization of well-indumatched acyclic graphs and some partial results on well-indumatched unicyclic graphs. A {pseudoforest} is a graph in which every connected component contains at most one cycle, that is, each connected component is a unicyclic graph or a tree. In this thesis, we finally extend the result in the literature about well-indumatched unicyclic graphs by providing a complete characterization of well-indumatched pseudoforests by identifying the structure of such graph families.
Benzer Tezler
- Ön işlemenin ve askorbik asitin dondurularak depolanan yılan balıklarının (Anguilla anguilla) kalitesine etkileri
Başlık çevirisi yok
H.VOLKAN GÖKSEL
Yüksek Lisans
Türkçe
1985
Gıda MühendisliğiEge ÜniversitesiSu Ürünleri Ana Bilim Dalı
DOÇ. DR. AYDIN URAL
- On the one-loop renormalizability of the non-linear sigma model with wess zumino structure
Başlık çevirisi yok
ERHAN ONUR İLTAN
Yüksek Lisans
İngilizce
1988
Fizik ve Fizik MühendisliğiOrta Doğu Teknik ÜniversitesiDOÇ. DR. NAMIK K. PAK
- The Control of heat exchangers using on-line identification, modern control theory and internal model control
Başlık çevirisi yok
MOSES NUNA BOGERE
- On dördüncü yüzyıla ait bir Kısas-ı Enbiya nüshası üzerinde sentaks incelenmesi
Başlık çevirisi yok
İSMET CEMİLOĞLU
Doktora
Türkçe
1988
Türk Dili ve EdebiyatıGazi ÜniversitesiTürk Dili ve Edebiyatı Ana Bilim Dalı
PROF. DR. AHMET BİCAN ERCİLASUN