Kesinlikle kordal grafiği - Strongly chordal graph

Olarak matematiksel alan grafik teorisi , bir yönsüz grafiktir G ise kuvvetli kiriş eğer bu bir kiriş grafiktir ve her çevrim içerisinde eşit uzunlukta (≥ 6) arasında G bir sahiptir tek bir akor yani, bir kenar bu tek olan bağlandığı iki köşe çevrimde birbirinden uzaklık (>1).

Karakterizasyonlar

Güçlü kiriş grafikler bir olması yasak subgraph karakterizasyonu üçten daha uzunlukta daha büyük bir neden döngüsü veya içermeyen grafik olarak N -Sun ( n  bir, ≥ 3) neden olduğu alt grafiği . Bir n -sun, 2 n köşesi olan, U  = { u 1 ,  u 2 ,...} ve W  = { w 1 ,  w 2 ,...} olmak üzere iki alt kümeye bölünmüş , her köşe w olacak şekilde bir kiriş grafiğidir. i in W'nin tam olarak iki komşusu vardır, u i ve u ( i  + 1) mod  n . Bir n -sun güçlü bir kordal olamaz, çünkü u 1 w 1 u 2 w 2 ... döngüsünde tek bir akor yoktur.

Güçlü kordal grafikler, aynı zamanda, güçlü bir mükemmel eleme sıralamasına sahip grafikler olarak da karakterize edilebilir, böylece herhangi bir köşenin komşuları, sıralamada daha sonra gelen herhangi bir köşenin komşuları bir klik oluşturur ve öyle ki, her i  <  j  <  k  < için  l ise, i sipariş th köşe bitişik olan k th ve l köşe inci ve j inci ve k inci köşe bitişiktir, daha sonra j inci ve l köşe inci bitişik olmalıdır.

Bir grafik, ancak ve ancak indüklenmiş alt grafiklerinin her birinin basit bir tepe noktasına, komşuları dahil edilerek doğrusal olarak sıralanmış komşulara sahip bir tepe noktasına sahipse güçlü bir kordaldır. Ayrıca, bir grafik ancak ve ancak kirişliyse ve uzunluğu beş veya daha fazla olan her döngüde 2 kirişli bir üçgen, iki kirişten oluşan bir üçgen ve döngünün bir kenarı varsa güçlü bir kiriştir.

Bir grafik, ancak ve ancak indüklenmiş alt grafiklerinin her birinin ikili kiriş grafiği olması durumunda güçlü bir şekilde kordaldır .

Güçlü kordal grafikler, her bir kenarın katıldığı tam alt grafiklerin sayısı açısından da karakterize edilebilir . Yine başka bir karakterizasyon verilmiştir.

Tanıma

Bir grafiğin polinom zamanında güçlü bir kordal olup olmadığını , basit bir tepe noktasını tekrar tekrar arayarak ve kaldırarak belirlemek mümkündür . Bu işlem, grafikteki tüm köşeleri ortadan kaldırırsa, grafik güçlü kordal olmalıdır; aksi takdirde, bu işlem daha basit köşeleri olmayan bir alt graf bulursa, orijinal graf güçlü bir şekilde kordal olamaz. Güçlü bir kiriş grafiği için, bu işlemle köşelerin kaldırıldığı sıra, güçlü bir mükemmel eleme sıralamasıdır.

Alternatif algoritmalar hemen bir grafiktir güçlü kiriş olup olmadığını belirlemek ve eğer öyleyse, zaman içinde, daha etkili bir şekilde güçlü mükemmel eleme sipariş kurulabileceğini bilinmektedir ((en az O , n 2 , ( n- + m ) log n )) bir grafik şurada n köşeler ve m kenarlar.

alt sınıflar

Önemli bir alt sınıf ( filojeniye dayalı ) k - yaprak güçleri sınıfıdır, bir ağacın yapraklarından, ağaçtaki mesafeleri en fazla k olduğunda iki yaprağı bir kenarla birbirine bağlayarak oluşturulan grafiklerdir . Bir yaprak gücü, bazı k için bir k- yaprak gücü olan bir grafiktir . Kuvvetli kirişli grafiklerin güçleri kuvvetli kirişli ve ağaçlar kuvvetli kirişli olduğundan, yaprak kuvvetlerinin kuvvetli kirişli olduğu sonucu çıkar. Güçlü kiriş grafiklerinin uygun bir alt sınıfını oluştururlar ve bu da küme grafiklerini 2 yapraklı güçler olarak içerir. Güçlü kiriş grafiklerinin bir diğer önemli alt sınıfı da aralık grafikleridir . Aralık grafiklerinin ve köklü yönlendirilmiş yol grafiklerinin daha büyük sınıfının yaprak güçleri olduğu gösterilmiştir.

algoritmik problemler

Kuvvetle Kordal grafikleri hem olduklarından Kordal grafikleri ve dually Korda grafikleri , böyle Bağımsız Set, clique, Boyama, Klik Kapak, hâkim Set ve Steiner Ağacı gibi çeşitli NP-tam problemler şiddetle Kordal grafikler için verimli bir şekilde çözülebilir. Grafik izomorfizmi, güçlü kordal grafikler için izomorfizm-tamamlanmıştır. Hamiltonian Circuit, güçlü kordal bölünmüş grafikler için NP-tamamlanmış olarak kalır .

Notlar

Referanslar

  • Brandstädt, Andreas ; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dual Chordal Graphs", SIAM Journal on Discrete Mathematics , 11 (3): 437–455, doi : 10.1137/s0895480193253415.
  • Brandstädt, Andreas ; Hundt, Hristiyan; Mancini, Federico; Wagner, Peter (2010), "Köklü yönlendirilmiş yol grafikleri yaprak güçlerdir", Discrete Mathematics , 310 (4): 897–910, doi : 10.1016/j.disc.2009.100.06.
  • Brandstädt, Andreas ; Le, Van Bang (2006), "3 yapraklı güçlerin yapısı ve doğrusal zaman tanıma", Bilgi İşlem Mektupları , 98 (4): 133–138, doi : 10.1016/j.ipl.2006.01.004.
  • Brandstädt, Andreas ; Le, Van Bang; Sritharan, R. (2008), "4 yapraklı yetkilerin yapısı ve doğrusal zaman tanıma", ACM İşlemleri Algoritmalar , 5 : Madde 11, doi : 10.1145/1435375.1435386.
  • Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
  • Chang, GJ (1982), K - Hakimiyeti ve Grafik Kaplama Problemleri , Ph.D. tez, Cornell Üniversitesi.
  • Dahlhaus, E.; Manuel, PD; Miller, M. (1998), "Güçlü kordal grafiklerin karakterizasyonu", Discrete Mathematics , 187 (1–3): 269–271 , doi : 10.1016/S0012-365X(97)00268-9.
  • De Caria, P.; McKee, TA (2014), "Güçlü kordal grafiklerin Maxclique ve birim disk karakterizasyonları", Tartışmalar Mathematicae Graph Theory , 34 (3): 593–602, doi : 10.7151/dmgt.1757.
  • Farber, M. (1983), "Kuvvetli kiriş grafiklerinin karakterizasyonu", Discrete Mathematics , 43 (2–3): 173–189, doi : 10.1016/0012-365X(83)90154-1.
  • Lubiw, A. (1987), "Matrislerin çift sözcük sıralaması", SIAM Journal on Computing , 16 (5): 854–879, doi : 10.1137/0216057.
  • McKee, TA (1999), "Güçlü kordal grafiklerin yeni karakterizasyonu", Discrete Mathematics , 205 (1–3): 245–247, doi : 10.1016/S0012-365X(99)00107-7.
  • Müller, H. (1996), "Chordal Bipartite Graphs in Hamilton Circuits", Discrete Mathematics , 156 (1–3): 291–298, doi : 10.1016/0012-365x(95)00057-4.
  • Nishimura, N.; Ragde, P.; Thilikos, DM (2002), "Yaprak etiketli ağaçlar için grafik güçleri", Journal of Algorithms , 42 : 69–108, doi : 10.1006/jagm.2001.1195.
  • Paige, R.; Tarjan, RE (1987), "Üç bölüm iyileştirme algoritması", SIAM Journal on Computing , 16 (6): 973–989, doi : 10.1137/0216062.
  • Rautenbach, D. (2006), "Yaprak kökleri hakkında bazı açıklamalar", Discrete Mathematics , 306 (13): 1456–1461, doi : 10.1016/j.disc.2006.03.030.
  • Spinrad, J. (1993), "Yoğun 0–1 matrislerinin çifte sözcüksel sıralaması", Information Processing Letters , 45 (2): 229–235, doi : 10.1016/0020-0190(93)90209-R.
  • Uehara, R.; Toda, S.; Nagoya, T. (2005), "Akor iki parçalı ve güçlü kirişli grafikler için grafik izomorfizmi bütünlüğü", Discrete Applied Mathematics , 145 (3): 479–482, doi : 10.1016/j.dam.2004.06.008.