Ağaç ayrışması - Tree decomposition

Sekiz köşeli bir grafik ve bunun altı düğümlü bir ağaca ayrıştırılması. Her grafik kenarı, bazı ağaç düğümlerinde birlikte listelenen iki köşeyi birbirine bağlar ve her grafik köşesi, ağacın bitişik bir alt ağacının düğümlerinde listelenir. Her ağaç düğümü en fazla üç köşe listeler, dolayısıyla bu ayrıştırmanın genişliği ikidir.

Olarak grafik teorisi , bir ağaç ayrışma , bir bir eşleme grafik bir içine ağaç tanımlamak için kullanılabilir treewidth grafik ve grafik üzerinde belirli bir işlem sorunlarını çözmek hızlandırır.

Ağaç ayrıştırma olarak da adlandırılan bağlantı ağaçları , klik ağaçları ya da ağaçlar katılması ; olasılıksal çıkarım , kısıt tatmini , sorgu optimizasyonu ve matris ayrıştırması gibi problemlerde önemli bir rol oynarlar .

Ağaç ayrışmaları kavramı ilk olarak Rudolf Halin  ( 1976 ) tarafından ortaya atılmıştır . Daha sonra Neil Robertson ve Paul Seymour  ( 1984 ) tarafından yeniden keşfedildi ve o zamandan beri birçok başka yazar tarafından incelendi.

Tanım

Sezgisel olarak, bir ağaç ayrıştırması, belirli bir G grafiğinin köşelerini bir ağacın alt ağaçları olarak temsil eder, öyle ki verilen grafikteki köşeler yalnızca karşılık gelen alt ağaçlar kesiştiğinde bitişik olur. Bu durumda, G, bir oluşturan alt grafiğini ait kesişme grafik alt ağaçlar. Tam kesişim grafiği bir kiriş grafiğidir .

Her alt ağaç, bir grafik tepe noktasını bir dizi ağaç düğümü ile ilişkilendirir. Bunu resmi olarak tanımlamak için, her bir ağaç düğümünü kendisiyle ilişkili köşeler kümesi olarak temsil ediyoruz. Böylece, bir G = ( V , E ) grafiği verildiğinde , bir ağaç ayrıştırması bir çifttir ( X , T ), burada X = { X ₁ , ..., X _n } aşağıdakilerin bir alt kümeleri ailesidir (bazen torbalar olarak adlandırılır ) V ve T , düğümleri X _i alt kümeleri olan ve aşağıdaki özellikleri karşılayan bir ağaçtır :

1. Tüm X _i kümelerinin birleşimi V'ye eşittir . Yani, her grafik köşesi en az bir ağaç düğümü ile ilişkilendirilir.
2. Her kenar için ( v , w grafikte), bir alt grubu vardır X _ı hem de içerir v ve w . Diğer bir deyişle, köşeler, yalnızca karşılık gelen alt ağaçların ortak bir düğümü olduğunda grafikte bitişiktir.
3. Eğer X, _i ve X, _j bir köşe ihtiva hem v , tüm düğümler x _k arasında (benzersiz) yol ağacının X _i ve X, _j içeren V de. Yani, v köşesi ile ilişkili düğümler , T'nin bağlantılı bir alt kümesini oluşturur . Bu aynı zamanda tutarlılık veya çalışan kesişim özelliği olarak da bilinir . Eşit olarak ifade edilebilir ki if , ve düğümlerdir ve ' den , ' ye giden yoldadır .${\displaystyle X_{i}}$${\displaystyle X_{j}}$${\displaystyle X_{k}}$${\displaystyle X_{k}}$${\displaystyle X_{i}}$${\displaystyle X_{j}}$${\displaystyle X_{i}\cap X_{j}\subseteq X_{k}}$

Bir grafiğin ağaç ayrıştırması benzersiz olmaktan çok uzaktır; örneğin, önemsiz bir ağaç ayrıştırması, grafiğin tüm köşelerini tek kök düğümünde içerir.

Altta yatan ağacı olan bir ağaç ayrıştırma yolu grafik bir yol ayrışma olarak adlandırılır ve ağaç bozunmanın bu özel türlerinden elde edilen genişlik parametre olarak bilinen pathwidth .

Ağaç genişliği k olan bir ağaç ayrıştırması ( X , T = ( I , F ) ) , eğer herkes için ve herkes için düzgündür . ${\displaystyle i\in I:|X_{i}|=k+1}$${\displaystyle (i,j)\in F:|X_{i}\cap X_{j}|=k}$

Bir ağaç ayrışmasındaki minimum ağaç sayısı , G'nin ağaç sayısıdır .

ağaç genişliği

Aynı grafiğin iki farklı ağaç ayrıştırması

Genişliği bir ağaç ayrışma, en büyük resim boyutu , X _i eksi on. Treewidth tw ( G bir grafik) G tüm olası ağaç ayrısımlarla arasından en az genişliği G . Bu tanımda, bir ağacın ağaç genişliğini bire eşit yapmak için en büyük kümenin boyutu bir küçültülür. Ağaç genişliği, kiriş grafikleri , böğürtlenler ve cennetler dahil olmak üzere ağaç ayrıştırmalarından başka yapılardan da tanımlanabilir .

Belirli bir G grafiğinin , belirli bir değişken k en fazla ağaç genişliğine sahip olup olmadığını belirlemek NP-tamamlanmıştır . Ancak zaman, k, herhangi bir sabit sabittir treewidth olan grafikler k kabul edilebilir, ve genişlik k ağaç ayrışma lineer zamanda, kendileri için inşa edilmiştir. Bu algoritmanın k'ye zamana bağımlılığı üsteldir.

Dinamik program

1970'lerin başında, grafikler üzerinde tanımlanan geniş bir kombinasyonel optimizasyon problem sınıfının , grafik , ağaç genişliği ile ilgili bir parametre olan sınırlı bir boyuta sahip olduğu sürece, seri olmayan dinamik programlama ile verimli bir şekilde çözülebileceği gözlemlendi. Daha sonra, birkaç yazar bağımsız olarak, 1980'lerin sonunda, keyfi grafikler için NP-tamamlanmış birçok algoritmik problemin , bu grafiklerin ağaç ayrıştırmaları kullanılarak, sınırlı ağaç genişliğine sahip grafikler için dinamik programlama ile verimli bir şekilde çözülebileceğini gözlemledi.

Örnek olarak, ağaç genişliği k olan bir grafikte maksimum bağımsız kümeyi bulma problemini ele alalım . Bu sorunu çözmek için, önce keyfi olarak kök olarak ağaç ayrıştırma düğümlerinden birini seçin. Ağaç ayrışmasının bir düğümü X _i için, D _i , X _{i '} den azalan X _j kümelerinin birleşimi olsun . Bağımsız bir kümesi için S  ⊂  X _i , izin bir ( S , i ) en büyük bağımsız alt-düzeyini göstermektedir ı arasında D _I bu şekilde bir  ∩  X _i  =  S . Benzer şekilde, düğüm bitişik bir çifti için x _i ve X, _j ile, X _i daha uzakta ağacın kökten X, _j , ve bağımsız bir grubu S  ⊂  X _i  ∩  x _j , izin B ( S , i , j ) göstermektedirler büyük bağımsız alt küme boyutu I ve D _I bu şekilde bir  ∩  X _i  ∩  x _j  =  S . Bu A ve B değerlerini ağacın aşağıdan yukarıya hareketiyle hesaplayabiliriz :

${\displaystyle A(S,i)=|S|+\sum _{j}\left(B(S\cap X_{j},j,i)-|S\cap X_{j}|\sağ) }$

${\displaystyle B(S,i,j)=\max _{S'\subset X_{i} \atop S=S'\cap X_{j}}A(S',i)}$

burada hesaplamadaki toplam , düğümün çocukları üzerindedir . ${\görüntüleme stili A(S,i)}$${\displaystyle X_{i}}$

Her düğüm veya kenarda, bu değerleri hesaplamamız gereken en fazla 2 ^k S kümesi vardır , bu nedenle k sabitse, tüm hesaplama kenar veya düğüm başına sabit zaman alır. Maksimum bağımsız kümenin boyutu, kök düğümde depolanan en büyük değerdir ve maksimum bağımsız kümenin kendisi (dinamik programlama algoritmalarında standart olduğu gibi), bu en büyük değerden başlayarak bu depolanan değerler üzerinden geriye doğru izlenerek bulunabilir. Böylece, sınırlanmış ağaç genişliği grafiklerinde, maksimum bağımsız küme problemi doğrusal zamanda çözülebilir. Benzer algoritmalar diğer birçok grafik problemi için de geçerlidir.

Bu dinamik programlama yaklaşımı, sınırlı ağaç genişliği grafiklerinde inanç yayılımı için bağlantı ağacı algoritması aracılığıyla makine öğreniminde kullanılır . Ayrıca, ağaç genişliğini hesaplamak ve ağaç ayrıştırmalarını oluşturmak için algoritmalarda önemli bir rol oynar: tipik olarak, bu tür algoritmaların ağaç genişliğine yaklaşan bir ilk adımı vardır , bu yaklaşık genişlikle bir ağaç ayrıştırması oluşturur ve ardından dinamik programlamayı gerçekleştiren ikinci bir adım vardır. ağaç genişliğinin tam değerini hesaplamak için yaklaşık ağaç ayrıştırması.

Ayrıca bakınız

• Brambles ve sığınaklar  – Bir grafiğin ağaç genişliğini tanımlamada ağaç ayrıştırmasına alternatif olarak kullanılabilecek iki tür yapı.
• Dal ayrışma  – Genişliği sabit bir ağaç genişliği faktörü içinde olan yakından ilişkili bir yapı.
• Ayrıştırma Metodu  – Kısıt tatmin problemini çözmek için Ayrıştırma Metodu'nda Ağaç Ayrıştırma kullanılır.

Notlar

Referanslar