Graphs of edge-intersecting non-splitting paths

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye

Tezin Onay Tarihi: 2015

Tezin Dili: İngilizce

Öğrenci: ARMAN BOYACI

Danışman: TINAZ EKİM

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Bu çalışmada yeni bir çizge sınıfı olan kenar-kesişen ve ayrılmayan yollar (ENP) çizge sınıfını sunuyor ve çalışıyoruz. İlk önce, özel ama nispeten doğal bir durum olan evsahibi çizgenin bir ağaç olduğu, bir ağaçta kenar-kesişen ayrılmayan yollar (ENPT) durumunu ele aldık. Temel ve önemli yapılar olan kirişsiz halkaların ENPT gösterimini çalıştık. Özel bir varsayım altında tekil enküçük gösterimi dönen bir algoritma verdik. Ancak gösterdik ki bu problem genel haliyle NP-zordur. Daha sonra problemi evsahibi çizgenin herhangi bir çizge olabildiği durum ile genelleştirdik. Herhangi bir evsahibi çizgede yer alan kenar-kesişimli yollar tüm çizgeleri içerse de, gösterdik ki bu durum ENP için doğru değildir. EPG çizge sınıfı için yapılan çalışmalara paralel olarak yolların ızgaradaki bükülme sayısını kısıtlamanın etkilerini çalıştık. Somut olarak, bükülme sayısının kısıtlanması ile birbirini tam olarak içeren sonsuz çizge sınıfları dizesi vardır. Tek bükümlü ENPG çizge sınıfının çift bükümlü çizge sınıfının tam olarak içerildiğini gösterdik. Ayrıca gösterdik ki ağaçlar ve halkalar tek bükümlü ENPG'dir. Yarık (split) ve bütün-ikikümeli (co-bipartite) çizgelerin tek bükümlü ENPG gösterimlerini karakterize ettik. Tek bükümlü ENPG tanıma probleminin yarık çizge sınıfıyla sınırlandırıldığı durumda bile zor olduğunu kanıtladık. Son olarak tek bükümlü ENPG bütün-ikikümeli çizgeler için doğrusal zamanlı bir tanıma algoritması verdik.