Planarity testing algorithms in graph theory
Çizge kuramında düzlemselliği test etme algoritmaları
- Tez No: 631265
- Danışmanlar: PROF. DR. HANDAN AKYAR
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: Anadolu Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Uygulamalı Matematik Bilim Dalı
- Sayfa Sayısı: 62
Özet
Bir çizgenin düzlemsel olup olmadığını belirlemek ve düzlemsel bir çizgeyi gömmek, çizge kuramı ve çizge çizimleri alanlarının en ilgi çekici ve büyüleyici algoritmik sorunlarından biridir. Bu tezde, basit ancak verimli algoritmalar yardımıyla bu tür problemler çözmenin basit yöntemleri ele alınmaktadır. Tezin 4. bölümünde, literatürde yer alan ve dümleselliği test etmek için kullanılan algoritmaların neredeyse tamamı listelenerek konuyla ilgili kısa ancak kapsamlı bir tarihsel süreçte sunulmakadır. Bu yüksek lisans tezinde iki doğrusal-zaman algoritması ve bir kuadratik-zaman algoritması tartışılmıştır. Sunulan algoritmalar bir çizgenin düzlemselliğini manuel olarak test ederken hangi algoritmanın daha kullanışlı olduğunu görmek için her algoritma iki örnek üzerinde de uygulanmıştır. Elde edilen bulgulara göre, Boyer-Myrvold algoritması, az sayıda köşeye sahip belirli bir çizgenin düzlemselliğini manuel olarak test etmek için en hızlı algoritmadır. Bununla birlikte, LEDA'da (Verimli Veri Tipleri ve Algoritmalar Kütüphanesi) çok sayıda köşe noktası olan çizgelerde yapılan testlere dayanarak, Sol-Sağ düzlemsellik algoritmasi en hızlı algoritmadır.
Özet (Çeviri)
Determining the planarity or displanarity of a graph and possibly embedding that graph is one of the most intriguing and fascinating algorithmic problems of the fields of graph theory and graph drawings. This thesis studies the simplest ways to do exactly that by using simple nevertheless efficient algorithms. Section 4 gives a short but comprehensive historical background on the subject by introducing a list of almost all planarity algorithms of all time. In this master thesis two linear-time algorithms and one quadratic-time algorithm are discussed. The presented algorithms are applied on two examples each to see which algorithm comes in handy when testing the planarity of a graph manually. According to the findings, the Boyer-Myrvold algorithm is the fastest algorithm to test the planarity of a certain graph, with few vertices, manually. However, based on tests done in LEDA (A Library of Efficient Data Types and Algorithms) on graphs with many vertices, the Left-Right planarity algorithm is the fastest algorithm to test planarity.
Benzer Tezler
- Tepe-Transitif graflar
Başlık çevirisi yok
FATMA YILDIRIM
Yüksek Lisans
Türkçe
1994
MatematikBalıkesir ÜniversitesiFen Bilimleri Ana Bilim Dalı
DOÇ. DR. MEHMET ARISOY
- Nano-scale chemically modified thin film characterization for chemical mechanical planarization applications
Nano-boyutta kimyasal modifiye edilmiş ince filmlerin kimyasal-mekanik düzleştirme uygulamaları için karakterizasyonu
AYŞE KARAGÖZ
Doktora
İngilizce
2015
Mühendislik BilimleriÖzyeğin ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÜL BAHAR BAŞIM DOĞAN
- Kapak onarım cerrahisi açısından insan kadaverik mitral kapak kompleks anatomisinin kritik analizi
Başlık çevirisi yok
ALİ FUAT KARAÇUHA
Tıpta Uzmanlık
Türkçe
2023
Göğüs Kalp ve Damar CerrahisiAnkara ÜniversitesiKalp ve Damar Cerrahisi Ana Bilim Dalı
PROF. DR. AHMET RÜÇHAN AKAR
- Pultrüzyon yöntemi ile üretimi yapılan kompozit profillerin darbe davranışlarının incelenmesi
Investigation of the impact behavior of composite profiles manufactured by pultrusion method
DUYGU GÜNKAYA
Yüksek Lisans
Türkçe
2023
Makine MühendisliğiUşak ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. OSMAN ASİ
- Design of a slotted waveguide array antenna and its feed system
Yarıklı dalga kılavuzu dizi anteni ve besleme sisteminin tasarımı
CAN BARIŞ TOP
Yüksek Lisans
İngilizce
2006
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ALTUNKAN HIZAL