Geri Dön

Graphs of edge-intersecting non-splitting paths

Kenar kesişen ve ayrılmayan yolların çizgeleri

PDF İndir

  1. Tez No: 409231
  2. Yazar: ARMAN BOYACI
  3. Danışmanlar: DOÇ. DR. TINAZ EKİM AŞICI
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2015
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 137

Ö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.

Özet (Çeviri)

In this work, we introduce and study a new graph class: namely the graphs of Edge-Intersecting Non-Splitting Paths (ENP). First, we consider a special case where the host graph is a tree: the graphs of Edge-Intersecting Non-Splitting Paths in a Tree (ENPT). We study the characterization of the ENPT representations of chordless cycles (holes) which are one of the important basic graph structures. Under some assumption, we give an algorithm that returns the unique minimal representation if it exists. However, we show that the problem is NP-complete in general that is when this assumption does not necessarily hold. Then, we consider a more general case for which the host graph can be an arbitrary graph. As opposed to the Edge Intersection Graphs of Paths in an arbitrary graph which includes all graphs, we show that this is not true for ENP that is there exist some graphs which are not ENP. We also show that the class ENP coincides with the family of graphs of Edge-Intersecting and Non-Splitting Paths in a Grid (ENPG). Following similar studies for EPG graph class, we study the implications of restricting the number of bends of the individual paths in the grid. We show that restricting the number of bends also restricts the graph class. More concretely, by restricting the number of bends one gets an infinite sequence of classes such that every class is properly included in the next one. In particular, we show that one bend ENPG graphs are properly included in two bend ENPG graphs. In addition, we show that trees and cycles are one bend ENPG graphs, and characterize split graphs and co-bipartite graphs that are one bend ENPG. We prove that the recognition problem of one bend ENPG graphs is NP-complete even in a very restricted subclass of split graphs. Last, we provide a linear time recognition algorithm for one bend ENPG co-bipartite graphs.

Benzer Tezler

  1. Tez No

    457440

    Intersection graphs of finite groups

    Sonlu grupların kesişim çizgeleri

    SELÇUK KAYACAN

    Doktora

    İngilizce

    İngilizce

    2016

    Matematikİstanbul Teknik Üniversitesi

    Matematik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ERGÜN YARANERİ

  2. Tez No

    827347

    Düzlemsel graflar üzerine

    On planar graphs

    EDA ATALAY

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    MatematikEskişehir Osmangazi Üniversitesi

    Matematik Bilgisayar Ana Bilim Dalı

    PROF. DR. İBRAHİM İLKER AKÇA

  3. Tez No

    430979

    Cebirsel yapıların kesişim çizgeleriyle gösterilişi üzerine

    On algebraic structures denoted by intersection graph

    SEMA KOŞAR SÜRÜL

    Yüksek Lisans

    Türkçe

    Türkçe

    2016

    MatematikKarabük Üniversitesi

    Matematik Ana Bilim Dalı

    DOÇ. DR. NİL ORHAN ERTAŞ

  4. Tez No

    335756

    Domination number of a finite group

    Sonlu bir grubun baskınlık sayısı

    NURDAN ÇABUKOĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    2013

    Matematikİstanbul Teknik Üniversitesi

    Matematik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ERGÜN YARANERİ

  5. Tez No

    607063

    Energy aware endurance framework for mission critical aerial networks

    Güdümlü havasal ağlar için enerji farkında endürans modeli

    YUSUF ÖZÇEVİK

    Doktora

    İngilizce

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. BERK CANBERK

Geri Dön