Bölünmüş (grafik teorisi) - Split (graph theory)
Olarak grafik teorisi , bir bölme , bir ait yönsüz grafik a, kesik olan kesme grubu formları tam ikili grafik . Bölünmesi olmayan bir grafik asaldır . Bir grafiğin bölmeleri, doğrusal zamanda oluşturulabilen bölünmüş ayrıştırma veya birleştirme ayrıştırma adı verilen ağaç benzeri bir yapıda toplanabilir . Bu ayrıştırma, daire grafiklerinin ve uzaklık-kalıtsal grafiklerin hızlı tanınması için ve ayrıca grafik algoritmalarındaki diğer problemler için kullanılmıştır.
Bölünmeler ve bölünmüş ayrıştırmalar ilk olarak, aynı kavramların yönlendirilmiş grafikler için varyantlarını da inceleyen Cunningham (1982) tarafından tanıtıldı .
Tanımlar
Bir kesik bir yönsüz grafik, iki boş olmayan alt-, kesme kenarları içine köşelerin bir bölümdür. Her iki tarafında bir bitiş noktası olan kenarların alt kümesine kesme kümesi denir. Bir kesim kümesi tam bir iki parçalı grafik oluşturduğunda , kesimine bölme denir. Bu durumda, bir ayrık İki alt-küme içine Grafiğin köşeler bir bölüm olarak tarif edilebilir , X ve Y , her bir komşu olacak şekilde, X in Y her komşu bitişik olan Y de X .
Kesim veya bölme, iki kenarından birinin içinde yalnızca bir tepe noktası olduğunda önemsizdir; her önemsiz kesim bir bölünmedir. Önemsiz bölünmelere sahip olmayan bir grafiğin (bölmelere göre) asal olduğu söylenir.
Bir bölmenin her iki tarafının diğer bölmenin her iki tarafıyla boş olmayan bir kesişimi varsa, iki bölmenin kesiştiği söylenir. Bir bölünme, başka bir bölünme tarafından geçilmediğinde güçlü olarak adlandırılır. Özel bir durum olarak, her önemsiz bölünme güçlüdür. Bir grafiğin güçlü bölmeleri, grafiğin bölünmüş ayrıştırması veya birleştirme ayrıştırması olarak adlandırılan bir yapıya yol açar. Bu ayrışma , verilen grafikle yaprakları bire bir ve kenarları grafiğin güçlü bölmeleriyle birebir eşleşen bir ağaçla temsil edilebilir , öyle ki yaprakların herhangi bir kenarının çıkarılmasıyla oluşan yaprakların bölünmesi. ağaç, ilişkili güçlü bölme tarafından verilen köşe bölümleriyle aynıdır.
Her bir iç düğüm ı bir grafik bölünmüş ayrışma ağacının G bir grafik ile ilişkilidir G i düğüm için bölüm grafiği denir, i . Bölüm grafiği , ağaçtan i'nin silinmesi , elde edilen alt ağaçların her birinde yapraklara karşılık gelen G'de köşe alt kümelerinin oluşturulması ve bu köşe kümelerinin her birinin tek bir köşeye daraltılmasıyla oluşturulabilir. Her bölüm grafiğinin üç biçiminden biri vardır: bir asal grafik, tam bir grafik veya bir yıldız olabilir .
Bir grafik üstel olarak birçok farklı bölmeye sahip olabilir, ancak bunların tümü bölünmüş ayrıştırma ağacında ya ağacın bir kenarı (güçlü bir bölme için) ya da tam veya yıldız bölüm grafiğinin keyfi bir bölümü olarak (bir bölme için) temsil edilir. güçlü değil).
Örnekler
Tam bir grafikte veya tam iki parçalı bir grafikte , her kesim bir bölünmedir.
Dört uzunluktaki bir döngü grafiğinde , döngünün 2-renklendirilmesiyle verilen köşelerin bölümü önemsiz bir bölmedir, ancak daha uzun uzunluktaki çevrimler için önemsiz bölmeler yoktur.
Bir köprü olmayan bir grafiğin 2-kenar-bağlı köprünün bir tarafında köşe oluşturduğu bölünmüş her bir tarafı, bir bölünme karşılık gelir. Bölünmenin kesme seti, tam bir iki parçalı alt grafiğin özel bir durumu olan sadece tek köprü kenarıdır. Benzer şekilde, v , 2-köşe bağlantılı olmayan bir grafiğin eklemlenme noktasıysa , grafik, v ve silinmesiyle oluşturulan bileşenlerin tamamı olmasa da bazılarının bir tarafta olduğu ve geri kalan bileşenlerin olduğu birden fazla bölmeye sahiptir. diğer taraftalar. Bu örneklerde, bölmenin kesme kümesi bir yıldız oluşturur .
algoritmalar
Cunningham (1982) , bölünmüş ayrışmayı polinom zamanında bulmanın mümkün olduğunu zaten göstermişti . Algoritmadaki sonraki iyileştirmelerden sonra, Dahlhaus (2000) ve Charbit, de Montgolfier & Raffinot (2012) tarafından doğrusal zaman algoritmaları keşfedildi .
Uygulamalar
Birkaç önemli grafik sınıfının tanınmasında bölünmüş ayrıştırma uygulanmıştır:
- Bir mesafe kalıtsal grafik olan bölünmüş ayrışma yok ana quotients içeren bir grafiktir. Bu karakterizasyona dayanarak, doğrusal zamanda mesafe-kalıtsal grafikleri tanımak için bölünmüş ayrıştırmayı kullanmak mümkündür.
- Parite grafikleri , her bir bölünmüş bölümün tam veya iki parçalı olduğu grafikler olarak doğrusal zamanda tanınabilir .
- Bir daire grafiği , bir dairenin akorları ailesinin kesişim grafiğidir. Belirli bir grafik, ancak ve ancak bölünmüş ayrışmasının bölümlerinin her biri bir daire grafiğiyse, bir daire grafiğidir, bu nedenle bir grafiğin daire grafiği olup olmadığının test edilmesi, grafiğin asal bölüm grafiklerinde aynı probleme indirgenebilir. Dahası, bir daire grafiği asal olduğunda, onu temsil eden akorlar kümesinin kombinatoryal yapısı benzersiz bir şekilde belirlenir, bu da bu yapıyı tanıma görevini basitleştirir. Bu fikirlere dayanarak, polinom zamanında daire grafiklerini tanımak mümkündür.
Rastgele grafiklerde NP-zor olan bazı problemlerin çözümünü basitleştirmek için bölünmüş ayrıştırma da kullanılmıştır:
- Olarak Cunningham (1982) daha önce gözlenen herhangi bir grafik maksimum bağımsız seti ile bulunabilir dinamik programlama kopmaz ayrışma ağacının aşağıdan yukarı bir geçişi algoritmanın. Her düğümde, alt düğümlerde halihazırda hesaplanmış bağımsız kümelerin boyutlarına göre ağırlıklandırılan bölüm grafiğinde maksimum ağırlık bağımsız kümesini seçiyoruz.
- Cunningham (1982) tarafından verilen başka bir algoritma kusurlu olsa da, benzer bir aşağıdan yukarıya geçiş , bölüm grafiklerinde ağırlıklı maksimum kliklerin hesaplamalarını birleştirerek bir grafiğin maksimum kliğini hesaplamak için kullanılabilir .
- Rao (2008) ayrıca bağlantılı baskın kümeler , tam baskın kümeler ve grafik renklendirme için algoritmalar sunar .
Bu yöntemler, her bölüm grafiğinin alt probleminin verimli bir şekilde hesaplanmasına izin veren basit bir yapıya sahip olduğu grafikler için polinom zaman algoritmalarına yol açabilir. Örneğin, bu, her bölüm grafiğinin sabit büyüklüğe sahip olduğu grafikler için geçerlidir.