Aralık grafiği - Interval graph

Olarak grafik teorisi , bir aralık grafik bir olan yönsüz grafik kümesinden oluşan aralıklar ile gerçek hattı Her bir aralık için, bir tepe noktası ve aralıkları kesişen uçları arasında bir kenar ile. Bu bir kesişme grafik aralıklarının.

Aralık grafikleri, kordal grafikler ve mükemmel grafiklerdir . Doğrusal zamanda tanınabilirler ve bu grafiklerde optimal bir grafik renklendirmesi veya maksimum klik doğrusal zamanda bulunabilir. Aralık grafikleri, tüm uygun aralık grafiklerini , bir dizi birim aralıktan aynı şekilde tanımlanan grafikleri içerir .

Bu grafikler, besin ağlarını modellemek ve örtüşmeyen zamanlarda gerçekleştirilecek görevlerin bir alt kümesini seçmesi gereken zamanlama problemlerini incelemek için kullanılmıştır. Diğer uygulamalar, DNA haritalamasında bitişik alt dizilerin birleştirilmesini ve zamansal akıl yürütmeyi içerir.

Tanım

Aralık grafiği, bir aralık ailesinden oluşturulan yönsüz bir grafiktir . ${\görüntüleme stili G}$

her aralık için bir tepe noktası oluşturarak ve karşılık gelen iki kümenin boş olmayan bir kesişimi olduğunda iki köşeyi ve bir kenarı birbirine bağlayarak . Yani, kenar seti IS ${\displaystyle v_{i}}$${\displaystyle S_{i}}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\görüntüleme stili G}$ Bu bir kesişme grafik aralıklarının.

Karakterizasyonlar

Üç köşe , her ikisi için, bu ikisini içeren ancak üçüncünün komşusu olmayan bir yol varsa, bir grafikte bir asteroit üçlüsü (AT) oluşturur . Asteroit üçlüsü olmayan bir grafik AT içermez. Aralık grafiklerinin en erken karakterizasyonu aşağıdaki gibi görünmektedir:

• Bir grafik, ancak ve ancak kordal ve AT'siz ise bir aralık grafiğidir .

Diğer karakterizasyonlar:

• Bir grafik, ancak ve ancak maksimal klikleri , bu kliklerden ikisine ait olan her bir köşe, sıralamada aralarındaki tüm kliklere ait olacak şekilde sıralanabiliyorsa , bir aralık grafiğidir . Yani, her with , aynı zamanda her zaman da böyledir .${\displaystyle M_{1},M_{2},\dots ,M_{k}}$${\displaystyle v\in M_{i}\cap M_{k}}$${\görüntüleme stili <k}$${\displaystyle v\in M_{j}}$${\görüntüleme stili i<j<k}$
• Bir grafik, ancak ve ancak döngü grafiğini indüklenmiş bir alt grafik olarak içermiyorsa ve bir karşılaştırılabilirlik grafiğinin tamamlayıcısıysa , bir aralık grafiğidir .${\görüntüleme stili C_{4}}$

Aralık grafiklerinin ve varyantlarının çeşitli diğer karakterizasyonları tarif edilmiştir.

Verimli tanıma algoritması

Belirli bir grafiğin bir aralık grafiği olup olmadığını belirlemek , tepe noktası içermesine göre ardışık olan maksimum kliklerinin sıralaması aranarak zaman içinde yapılabilir . Bu problem için bilinen algoritmaların çoğu bu şekilde çalışır, ancak aralık grafiklerini lineer zamanda onların kliklerini kullanmadan tanımak da mümkündür. ${\görüntüleme stili G=(V,E)}$${\displaystyle O(|V|+|E|)}$${\görüntüleme stili G}$

Booth & Lueker'in (1976) orijinal doğrusal zaman tanıma algoritması, karmaşık PQ ağacı veri yapısına dayanmaktadır , ancak Habib ve ark. (2000) , bir grafiğin ancak ve ancak kordal olması ve tamamlayıcısının bir karşılaştırılabilirlik grafiği olması durumunda bir aralık grafiği olduğu gerçeğine dayanarak, sözlükbilimsel genişlik öncelikli aramayı kullanarak sorunun nasıl daha basit bir şekilde çözüleceğini gösterdi . 6 taramalı LexBFS algoritmasını kullanan benzer bir yaklaşım Corneil, Olariu & Stewart (2009)' da anlatılmıştır .

İlgili grafik aileleri

Aralık grafiklerinin AT'den bağımsız kiriş grafikleri olarak karakterize edilmesiyle, aralık grafikleri güçlü kiriş grafikleridir ve dolayısıyla mükemmel grafiklerdir . Onların tamamlar sınıfına aittir kıyaslanabilirlik grafikler ve karşılaştırılabilirlik ilişkileri kesin olan aralık siparişleri .

Bir grafiğin bir aralık grafiği olması gerçeğinden, ancak ve ancak akor ve tamamlayıcısı bir karşılaştırılabilirlik grafiği ise , bu grafiği ve onun tamamlayıcısının, ancak ve ancak grafiğin hem bölünmüş bir grafik hem de bir permütasyon olması durumunda aralık grafikleri olduğunu izler. grafik .

Her iki aralığın ayrık veya iç içe olduğu bir aralık temsiline sahip aralık grafikleri, önemsiz derecede mükemmel grafiklerdir .

Bir grafiğin, ancak ve ancak bir aralık grafiği olması durumunda en fazla bir kutuluğu vardır ; keyfi bir grafiğin kutululuğu, aralık grafiklerinin kenar kümelerinin kesişimi olacak şekilde aynı köşe kümesindeki minimum aralık grafiği sayısıdır . ${\görüntüleme stili G}$${\görüntüleme stili G}$

Kesişim grafikleri yay a daire şekli dairesel yay grafikler , aralık grafikler yer almaktadır grafikler bir sınıfı. Yamuk grafikleri , paralel kenarları aynı iki paralel hat üzerindeki tüm yalan yamuk kesişmeleri de aralık grafikler bir genelleme bulunmaktadır.

Bağlı üçgensiz aralık grafikleri tam olarak tırtıl ağaçlarıdır .

Uygun aralık grafikleri

Uygun aralık grafikleri , hiçbir aralığın başka bir aralığı düzgün bir şekilde içermediği bir aralık temsiline sahip aralık grafikleridir ; birim aralık grafikleri , her bir aralığın birim uzunluğuna sahip olduğu bir aralık temsiline sahip aralık grafikleridir. Tekrarlanan aralıkları olmayan bir birim aralık gösterimi, zorunlu olarak uygun bir aralık gösterimidir. Her uygun aralık gösterimi bir birim aralık gösterimi değildir, ancak her uygun aralık grafiği bir birim aralık grafiğidir ve bunun tersi de geçerlidir. Her uygun aralık grafiği, pençesiz bir grafiktir ; tersine, uygun aralık grafikleri tam olarak pençesiz aralık grafikleridir. Ancak, aralık grafikleri olmayan pençesiz grafikler de vardır.

Herhangi bir aralığın diğerlerinden daha fazla içermediği bir gösterim varsa , bir aralık grafiği - uygun olarak adlandırılır . Bu kavram, 0-uygun aralık grafiği uygun bir aralık grafiği olacak şekilde uygun aralık grafikleri fikrini genişletir. Hiçbir aralığın diğerlerinden daha fazlasını içermediği bir gösterim varsa , bir aralık grafiği -improper olarak adlandırılır . Bu kavram, 0-yanlış aralık grafiği uygun bir aralık grafiği olacak şekilde uygun aralık grafikleri fikrini genişletir. Bir aralık grafiği, iç içe geçmiş bir aralık uzunluğu zinciri yoksa, iç içedir . 1-iç içe aralık grafikleri tam olarak uygun aralık grafikleri olduğundan, bu uygun aralık grafiklerinin bir genellemesidir. ${\görüntüleme stili q}$${\görüntüleme stili q}$${\görüntüleme stili p}$${\görüntüleme stili p}$${\görüntüleme stili k}$${\ Displaystyle k+1}$

Uygulamalar

Aralık grafiklerinin matematiksel teorisi, liderlerin yanı sıra Peter C. Fishburn gibi genç araştırmacıları ve Alan C. Tucker ve Joel E. Cohen gibi öğrencileri içeren RAND Corporation'ın matematik bölümündeki araştırmacıların uygulamalarına yönelik bir bakış açısıyla geliştirildi. —Delbert Fulkerson ve (yinelenen ziyaretçi) Victor Klee gibi . Cohen aralığı grafikler uygulanan matematiksel modeller arasında nüfus biyoloji , özellikle gıda ağları .

Aralık grafikleri, yöneylem araştırması ve çizelgeleme teorisindeki kaynak tahsis problemlerini temsil etmek için kullanılır . Bu uygulamalarda, her aralık belirli bir süre için bir kaynağa (dağıtılmış bir bilgi işlem sisteminin işlem birimi veya bir sınıf için bir oda gibi) yönelik bir talebi temsil eder. Grafik için maksimum ağırlıktan bağımsız küme sorunu , çakışma olmadan karşılanabilecek en iyi istek alt kümesini bulma sorununu temsil eder. Daha fazla bilgi için aralık planlamasına bakın .

Aralık grafiğinin optimal grafik rengi , mümkün olduğunca az kaynakla tüm istekleri kapsayan bir kaynak atamasını temsil eder; bunun bulunabilir polinom zamanda bir tarafından açgözlü boyama algoritması sol uç noktaları ile sıralanmış sırayla renkler aralıkları söyledi.

Diğer uygulamalar arasında genetik, biyoinformatik ve bilgisayar bilimi bulunur. Bir aralık grafiğini temsil eden bir dizi aralık bulmak, DNA haritalamasında bitişik alt dizileri birleştirmenin bir yolu olarak da kullanılabilir . Aralık grafikleri de zamansal akıl yürütmede önemli bir rol oynar.

Aralık tamamlamaları ve yol genişliği

Eğer isteğe bağlı bir grafiktir, bir bir aralık tamamlanması arasında içeren aynı tepe sette bir aralık grafiktir bir alt grafiği olarak. Aralık tamamlamanın parametreli versiyonu ( k ek kenarlı bir aralık süpergrafı bulun ) sabit parametre izlenebilirdir ve dahası, parametreleştirilmiş alt-üssel zamanda çözülebilir. ${\görüntüleme stili G}$${\görüntüleme stili G}$${\görüntüleme stili G}$

Pathwidth bir aralık grafik (daha az olan renk sayısına eşit veya eşdeğer bir) daha az maksimum klik boyutundan biridir ve herhangi bir grafiğin pathwidth içeren bir aralık grafiğin küçük pathwidth aynıdır bir alt grafiği olarak . ${\görüntüleme stili G}$${\görüntüleme stili G}$

Notlar

Referanslar

Dış bağlantılar

• "aralık grafiği" , Grafik Sınıfları ve İnklüzyonları Hakkında Bilgi Sistemi
• Weisstein, Eric W. , "Aralık grafiği" , MathWorld