Blok grafiği - Block graph
Olarak grafik teorisi , birleştirici bir matematik dalı, bir blok grafik veya klik ağaç türüdür yönsüz grafik her hangi biconnected bileşen (blok) a, klik .
Blok grafikler bazen yanlışlıkla Husimi ağaçları olarak adlandırılır ( Kôdi Husimi'den sonra ), ancak bu ad daha doğru bir şekilde kaktüs grafiklerine , yani her önemsiz çift bağlantılı bileşenin bir döngü olduğu grafiklere atıfta bulunur .
Blok grafikler , rastgele yönlendirilmemiş grafik bloklarının kesişim grafikleri olarak karakterize edilebilir .
karakterizasyon
Blok grafikler tam olarak, her dört u , v , x ve y köşesi için , üç uzaklığın en büyük ikisinin d ( u , v ) + d ( x , y ), d ( u , x ) + olduğu grafiklerdir. d ( v , y ) ve d ( u , y ) + d ( v , x ) her zaman eşittir.
Ayrıca, indüklenmiş bir alt grafik olarak elmas grafiği veya dört veya daha fazla köşe döngüsü olmayan grafikler olarak yasak bir grafik karakterizasyonuna sahiptirler ; yani, elmassız akor grafikleridir. Bunlar aynı zamanda, birbirinden iki mesafedeki her iki düğümün benzersiz bir en kısa yolla bağlandığı Ptolemaik grafiklerdir ( kordal mesafe-kalıtsal grafikler ) ve her iki maksimum kliğin ortak en fazla bir tepe noktasına sahip olduğu kiriş grafikleridir.
Bir grafik G her iki kesişme ancak ve ancak bir blok grafiktir bağlı köşe alt kümeleri G boş ya da bağlantılıdır. Bu nedenle, bağlantılı bir blok grafiğindeki bağlantılı köşe alt kümeleri, blok grafik olmayan herhangi bir grafik için doğru olmayan bir özellik olan dışbükey bir geometri oluşturur . Bu özellik nedeniyle, bağlantılı bir blok grafiğinde, her köşe kümesinin benzersiz bir minimal bağlantılı üst kümesi vardır, dışbükey geometride kapanması. Bağlı blok grafikler, her bir köşe çiftini birbirine bağlayan benzersiz bir indüklenmiş yolun olduğu grafiklerdir .
İlgili grafik sınıfları
Blok grafikler kordal , uzaklık kalıtsal ve jeodeziktir . Uzaklık-kalıtsal grafikler, aynı iki köşe arasındaki her iki indüklenmiş yolun aynı uzunluğa sahip olduğu grafiklerdir; bu, her iki köşe arasında en fazla bir indüklenmiş yola sahip blok grafiklerin karakterizasyonunun zayıflamasıdır. Hem kordal grafikler hem de uzaklık-kalıtsal grafikler mükemmel grafiklerin alt sınıfları olduğundan , blok grafikler mükemmeldir.
Her ağaç , küme grafiği veya yel değirmeni grafiği bir blok grafiğidir.
Her blok grafiğin en fazla iki kutuluğu vardır .
Blok grafikler, sözde medyan grafiklerin örnekleridir : her üç köşe için, ya üç köşe arasındaki en kısa yollara ait benzersiz bir köşe vardır ya da kenarları bu en kısa üç yolda uzanan benzersiz bir üçgen vardır.
Çizgi grafikleridir ağaçlar tam olarak her kesim tepe en fazla iki blok ya da eşdeğer yapılan olay olan blok grafiklerdir pençe içermeyen blok grafikler. Ağaçların çizgi grafikleri, bir ağaç olan en büyük indüklenmiş alt grafiğin mümkün olduğu kadar küçük olduğu belirli sayıda kenar ve köşeye sahip grafikleri bulmak için kullanılmıştır.
Her bloğun en fazla üç boyutlu olduğu blok grafikler, özel bir kaktüs grafiği türüdür, üçgen kaktüs. Herhangi bir grafikteki en büyük üçgen kaktüs , matroid parite problemi için bir algoritma kullanılarak polinom zamanında bulunabilir . Üçgen kaktüs grafikleri düzlemsel grafikler olduğundan , en büyük üçgen kaktüs, düzlemselleştirmede önemli bir alt problem olan en büyük düzlemsel alt grafiğe bir yaklaşım olarak kullanılabilir . Bir yaklaşım algoritması olarak , bu yöntem, maksimum düzlemsel alt çizge problemi için en iyi bilinen yaklaşıklık oranı 4/9'a sahiptir .
Yönsüz grafiklerin blok grafikleri
Eğer G bir yönsüz grafik, blok grafiğidir G ile gösterilen B ( G ), bir kesişme grafik bloklarının G : B ( G ) a her biconnected bileşeni için köşe sahip G ve iki köşe B ( G ) karşılık gelen iki blok bir eklemlenme köşesinde buluşuyorsa bitişiktir. Eğer K 1 bir tepe grafiği temsil eder, daha sonra oda ( K 1 ) olarak tanımlanır boş grafiktir . B ( G ) zorunlu olarak bir blok grafiktir: G'nin her eklemlenme tepe noktası için bir çift bağlantılı bileşene sahiptir ve bu şekilde oluşturulan her iki bağlantılı bileşen bir klik olmalıdır. Bunun aksine, her bir blok grafik grafiktir B ( G bir grafik için) G . Eğer G bir ağaç, daha sonra, oda ( G ) ile çakışmaktadır çizgi grafiği arasında G .
B ( B ( G )) grafiği , G'nin her eklemlenme tepe noktası için bir tepe noktasına sahiptir ; İki köşe bitişik olan B ( B ( G de aynı bloğa ait ise)) G .