tırtıl ağacı - Caterpillar tree
Olarak grafik teorisi , bir tırtıl veya tırtıl ağaç a, ağaç bütün çıkıntılar merkezi bir yolun mesafe 1 içinde olduğu.
Tırtıllar ilk olarak Harary ve Schwenk tarafından bir dizi makalede incelenmiştir. İsim A. Hobbs tarafından önerildi . Şöyle Harary ve Schwenk (1973) renkli yazma, "Bir tırtılın yoluna başkalaşımlar uç noktaları olan koza kaldırılır bir ağaçtır."
eşdeğer karakterizasyonlar
Aşağıdaki karakterizasyonların tümü tırtıl ağaçlarını tanımlar:
- Yaprakları ve gelen kenarları kaldırarak bir yol grafiği oluşturan ağaçlardır .
- İki veya daha fazla derecenin her köşesini içeren bir yolun bulunduğu ağaçlardır.
- En az üç derecenin her köşesinin en fazla iki yaprak olmayan komşuya sahip olduğu ağaçlardır.
- K 1,3 yıldız grafiğindeki her kenarın iki uzunluğunda bir yol ile değiştirilmesiyle oluşturulan grafiği alt graf olarak içermeyen ağaçlardır .
- Köşeleri iki paralel çizgi üzerinde çizilebilen , kenarları her çizgide bir bitiş noktası olan kesişmeyen çizgi parçaları olarak temsil edilen bağlantılı grafiklerdir .
- Onlar, ağaçlar kare a, Hamilton grafiktir . Yani, bir tırtılda, dizideki her bitişik köşe çiftinin birbirinden bir veya iki uzaklıkta olduğu tüm köşelerin döngüsel bir dizisi vardır ve tırtıl olmayan ağaçlarda böyle bir dizi yoktur. Bu tür bir döngü, tırtılı iki paralel çizgi üzerine çizerek ve bir satırdaki köşelerin sırasını, diğer satırdaki dizinin tersi ile birleştirerek elde edilebilir.
- Bunlar, çizgi grafikleri bir Hamilton yolu içeren ağaçlardır ; böyle bir yol, ağacın iki çizgili bir çiziminde kenarların sıralanmasıyla elde edilebilir. Daha genel olarak, bir Hamilton yolunu içermesi için rastgele bir ağacın çizgi grafiğine eklenmesi gereken kenarların sayısı ( Hamiltonian tamamlamasının boyutu ), ağacın kenarlarının alabileceği minimum kenar ayrık tırtıl sayısına eşittir. olarak ayrıştırılabilir.
- Bunlar, yol genişliğinin bağlantılı grafikleridir .
- Bunlar bağlı üçgensiz aralık grafikleridir .
- Komşuluk matrisleri, üst üçgen kısmın sağ üst köşesinden başlayıp aşağı veya sola giden n-1 uzunluğunda bir yol oluşturacak şekilde yazılabilen n-köşe grafikleridir.
genellemeler
Bir k ağacı , her biri k + 1 köşe içeren tam olarak n - k maksimum klik içeren bir kiriş grafiğidir ; a k -Tree bir değil kendisi ( k -clique + 1) , her bir maksimum klik iki ya da daha çok bileşen halinde grafik ayıran ya da tek bir yaprak tepe, sadece tek bir maksimum klik ait bir köşe ihtiva eder. Bir k -Path isimli bir k -ağacı en fazla iki yaprak ve bir k -caterpillar isimli bir k -ağacı bir içine bölümlenmiş olabilir k -Path ve bazı K -leaves, a, her bir bitişik ayırıcı k arasında -clique k -yol. Bu terminolojide, 1-tırtıl, tırtıl ağacıyla aynı şeydir ve k -tırtıllar, yol genişliği k olan kenar-maksimal grafiklerdir .
Bir ıstakoz grafiği, tüm köşelerin merkezi bir yolun 2 mesafesi içinde olduğu bir ağaçtır .
numaralandırma
Tırtıllar, kesin bir formülün verilebileceği ender grafik numaralandırma problemlerinden birini sağlar : n ≥ 3 olduğunda , n etiketlenmemiş tırtıl sayısıdır.
For n = 1, 2, 3, ... sayısı n -vertex tırtıllar vardır
hesaplama karmaşıklığı
Bir grafikte yayılan bir tırtıl bulmak NP-tamamlanmıştır . İlgili bir optimizasyon problemi Minimum Yayılan Tırtıl Problemidir (MSCP), burada bir grafiğin kenarları üzerinde çift maliyet vardır ve amaç, giriş grafiğini kapsayan ve en küçük toplam maliyete sahip bir tırtıl ağacı bulmaktır. Burada tırtılın maliyeti, kenarlarının maliyetlerinin toplamı olarak tanımlanır; burada her kenar, yaprak kenarı veya iç kenar rolüne bağlı olarak iki maliyetten birini alır. P = NP olmadıkça MSCP için f(n)- yaklaşım algoritması yoktur . Burada f(n), bir grafiğin köşe sayısı olan n'nin herhangi bir polinom zamanlı hesaplanabilir fonksiyonudur.
Sınırlı ağaç genişliği grafiklerinde MSCP için optimal bir çözüm bulan parametreli bir algoritma vardır . Dolayısıyla, bir grafik bir dış düzlem, bir seri-paralel veya bir Halin grafiği ise , hem Yayılan Tırtıl Problemi hem de MSCP'nin doğrusal zaman algoritmaları vardır .
Uygulamalar
Benzenoid hidrokarbon moleküllerinin yapısını temsil etmek için kimyasal grafik teorisinde tırtıl ağaçları kullanılmıştır . Bu temsilde, her bir kenarın moleküler yapıda 6 karbonlu bir halkaya karşılık geldiği ve karşılık gelen halkalar uçtan uca bağlı bir halka dizisine ait olduğunda iki kenarın bir tepe noktasında geldiği bir tırtıl oluşturulur. yapı. El-Basil (1987) şöyle yazıyor: "Şu anda "kimyasal çizge kuramı" olarak adlandırılan şeyde önemli bir rol oynayan hemen hemen tüm çizgelerin tırtıl ağaçlarıyla ilişkili olabilmesi şaşırtıcıdır." Bu bağlamda tırtıl ağaçları, Ivan Gutman'ın bu alandaki çalışmalarından sonra benzenoid ağaçlar ve Gutman ağaçları olarak da bilinir .