Bramble (grafik teorisi) - Bramble (graph theory)
Grafik Teorik olarak, dikenli bir için yönsüz grafik G ailesidir bağlı Alt Graflar arasında G ayrık Alt Graflar her çifti için, bir kenar bulunmalıdır: tüm dokunma birbirine o G , her alt grafiği bir bitiş noktası vardır. Sipariş bir bramble bir en küçük boyutudur vurma grubu , köşe bir dizi G Alt Graflar her biri ile boş olmayan bir kesişme vardır. Brambles , G'nin ağaç genişliğini karakterize etmek için kullanılabilir .
Ağaç genişliği ve sığınaklar
Bir G grafiğinde k dereceli bir sığınak , her iki alt kümenin β ( X ) ve β ( Y ) birbirine değeceği şekilde, k noktasından daha az olan her bir X kümesini G - X'in bağlantılı bir bileşenine eşleyen bir β işlevidir. herbiri. Böylece, β'nın görüntü kümesi G'de k sıralı bir böğürtlen oluşturur . Tersine, her böğürtlen, bir sığınak belirlemek için kullanılabilir: böğürtlen türünden daha küçük boyutlu her bir X kümesi için , böğürtlen içindeki X'ten ayrık olan tüm alt grafikleri içeren benzersiz bir bağlı bileşen β ( X ) vardır. .
Seymour ve Thomas (bir sığınak bölgesinin eşit ya da), bir bramble sırasını gösterdiği gibi karakterize treewidth : bir grafiktir sırası bir dikenli sahip k , ancak ve ancak en az treewidth sahip olması durumunda , k 1 - .
böğürtlenlerin boyutu
Sınırlı dereceli genişletici grafikler , köşe sayılarıyla orantılı ağaç genişliğine sahiptir ve bu nedenle ayrıca doğrusal düzende böğürtlenlere sahiptir. Bununla birlikte, Martin Grohe ve Dániel Marx'ın gösterdiği gibi, bu grafikler için, böylesine yüksek bir mertebeden bir böğürtlen, katlanarak çok sayıda küme içermelidir. Daha güçlü olarak, bu grafikler için, sırası ağaç genişliğinin karekökünden biraz daha büyük olan böğürtlenlerin bile üstel boyutu olmalıdır. Bununla birlikte, Grohe ve Marx ayrıca, ağaç genişliği k olan her grafiğin bir polinom boyutu ve düzenine sahip olduğunu gösterdi .
hesaplama karmaşıklığı
Brambles üstel boyuta sahip olabileceğinden , sınırsız ağaç genişliği grafikleri için onları polinom zamanında oluşturmak her zaman mümkün değildir . Bununla birlikte, ağaç genişliği sınırlandırıldığında, bir polinom zaman yapısı mümkündür: O( n k + 2 ) zamanında, mevcut olduğunda, k mertebesinde bir böğürtlen bulmak mümkündür, burada n , verilen grafikteki köşe sayısıdır. . Birkaç minimum ayırıcıya sahip grafikler için daha da hızlı algoritmalar mümkündür.
Bodlaender, Grigoriev ve Koster, yüksek mertebeden böğürtlenleri bulmak için buluşsal yöntemler üzerinde çalıştılar. Yöntemleri her zaman girdi grafiğinin ağaç genişliğine yakın sıralı böğürtlenler oluşturmaz, ancak düzlemsel grafikler için sabit bir yaklaşıklık oranı verirler . Kreutzer ve Tazari , ağaç genişliği k grafiklerinde, polinom boyutundaki böğürtlenleri ve polinom zaman içindeki sıralı böğürtlenleri bulan , Grohe ve Marx (2009) tarafından polinom boyutlu böğürtlenler için varolmak üzere gösterilen sıranın logaritmik faktörüne giren rastgele algoritmalar sağlar .
Yönlendirilmiş böğürtlenler
Bramble kavramı, yönlendirilmiş grafikler için de tanımlanmıştır. Bir de ilgilidir grafiktir D , bir dikenli bir koleksiyon kuvvetli bağlanmış bir Alt Graflar D ayrık elemanlar her çifti için: birbirine tüm dokunma bu X , Y, bramble bölgesinin bir yay bulunmalıdır D den X için Y bir diğerine ve bir Y için X . Sipariş bir bramble bir en küçük boyutudur vurma grubu , köşe bir dizi D bramble elemanlarının her biri ile bir boş olmayan bir arakesite. Dikenli sayısı arasında D bir bramble maksimum sırasıdır D . Yönlendirilmiş bir grafiğin böğürtlen sayısı, yönlendirilmiş ağaç genişliğinin sabit bir faktörü içindedir.