yaprak gücü - Leaf power

Bir ağaç (üstte) ve karşılık gelen 3 yapraklı gücü (altta)

Olarak matematiksel bir alan grafik teorisi , bir k -leaf güç bir ağacın bir grafiktir olan noktalar yaprakları olan kenarları mesafe yaprak çiftleri bağlanmak ve en fazla bir . Kendisine, bir bir kaynaklı alt grafiğinin bölgesinin grafik gücü yaprakları ile indüklenen, . Bu şekilde oluşturulan bir grafik için , ' nin k -yaprak kökü olarak adlandırılır . ${\görüntüleme stili T}$${\görüntüleme stili G}$${\görüntüleme stili T}$${\görüntüleme stili T}$${\görüntüleme stili k}$${\görüntüleme stili G}$ ${\görüntüleme stili T^{k}}$${\görüntüleme stili T}$${\görüntüleme stili G}$${\görüntüleme stili T}$${\görüntüleme stili G}$

Bazıları için yaprak gücü ise bir grafik yaprak gücüdür . Bu grafikler, evrim ağaçlarının yeniden yapılandırılması sorunu olan filogenide uygulamalara sahiptir . ${\görüntüleme stili k}$${\görüntüleme stili k}$

İlgili grafik sınıfları

Kuvvetli kirişli grafiklerin güçleri güçlü kirişli ve ağaçlar güçlü kirişli olduğundan, yaprak güçlerinin güçlü kirişli grafikler olduğu sonucu çıkar. Aslında, yaprak güçleri, güçlü kirişli grafiklerin uygun bir alt sınıfını oluşturur; bir grafik, ancak ve ancak sabit toleranslı bir NeST grafiğiyse ve bu tür grafikler güçlü kordal grafiklerin uygun bir alt sınıfıysa bir yaprak gücüdür.

Gelen Brandstädt ve diğ. (2010) , aralık grafiklerinin ve köklü yönlendirilmiş yol grafiklerinin daha büyük sınıfının yaprak güçleri olduğunu göstermiştir. Kayıtsızlık grafikleri tam olarak kimin altta yatan ağaçlar yaprak güçler tırtıl ağaçlar .

K -leaf sınırlandırılmış değerler için yetkileri k mı sınırlı klik-genişliği , ancak bu sınırsız üstellerle yaprak güçlerin doğru değildir.

Yapı ve tanıma

Bir grafik, ancak ve ancak, eğer, bir 2 yapraklı gücü ayrık birleşimi arasında klikleri (yani, bir küme grafik ).

Bir grafik, ancak ve ancak (boğa, dart, mücevher) içermeyen bir akor grafiği ise 3 yapraklı bir güçtür . Bu ve benzerlerine dayanarak, 3 yapraklı güçler lineer zamanda tanınabilir .

4 yapraklı güçlerin karakterizasyonları Rautenbach (2006) ve Brandstädt, Le & Sritharan (2008) tarafından verilmiştir ve bu da doğrusal zaman tanımayı mümkün kılmaktadır. 5 yapraklı ve 6 yapraklı güç grafiklerinin tanınması da sırasıyla Chang ve Ko (2007) ve Ducoffe (2018) tarafından lineer zamanda çözülmüştür.

İçin de ≥ 7 tanıma problemi -leaf güçler açıktır ve aynı şekilde, bu yaprak güçler tanınan edilip edilemeyeceğini açık bir problemdir polinom zamanda . Bununla birlikte, fark olduğu kanıtlanmıştır -leaf güçleri olan sabit bir parametre uysal parametreli zaman ve dejenerasyon giriş grafik. ${\görüntüleme stili k}$${\görüntüleme stili k}$${\görüntüleme stili k}$${\görüntüleme stili k}$

Notlar

Referanslar