Ayırıcı (grafik teorisi)
Olarak grafik teorisi ve teorik bilgisayar biliminin , bir ayırıcı bağlı bir grafik çıkarılması grafik yapar grafik köşe bir alt kümesidir bağlı-olmayan . Bu nesne, bir grafiği daha küçük ve daha basit grafiklere ayırmak için özellikle kullanışlıdır.
Bazen ayırıcıya, çıkarılması grafiği bağlantısız hale getiren, yani bir kesim yapan bir kenar kümesi diyoruz .
Menger teoremi bağlayan bağlantı ve ayırıcılar minimum.
Resmi tanımlama
Bir grafik için , bir ayırıcı bir alt kümesi içinde bu şekilde alt grafiğinin neden olduğu daha fazlasına sahiptir bağlı bileşenlerin daha , yani iki köşe orada mevcut olacağı şekilde bir yol ile bağlıdır ancak artık içindedir alt -graph ile indüklenen . Bu durumda biz demek ayıran dan .
G=(V,E){\ displaystyle G = (V, E)}S{\ displaystyle S}V{\ displaystyle V}V∖S{\ displaystyle V \ setminus S}G{\ displaystyle G}sen,v∈V∖S{\ displaystyle u, v \ in V \ setminus S}G{\ displaystyle G}V∖S{\ displaystyle V \ setminus S}S{\ displaystyle S}sen{\ displaystyle u}v{\ displaystyle v}
Minimum ayırıcı
Izin vermek ve bir grafiğin aynı bağlantılı bileşenine ait iki köşe olsun . Biz diyoruz -Minimal separatörlerde ayıran herhangi bir köşe seti gelen ve içerme ile çok az. Köşe kümesi bir olan asgari ayırıcı arasında bir ise bazı köşeler için asgari -separator, ve .
sen{\ displaystyle u}v{\ displaystyle v}G{\ displaystyle G}(sen,v){\ displaystyle (u, v)}sen{\ displaystyle u}v{\ displaystyle v}G{\ displaystyle G}G{\ displaystyle G}(sen,v){\ displaystyle (u, v)}sen{\ displaystyle u}v{\ displaystyle v}
Misal:
Bir ağacın her bir iç köşesi, minimal bir ayırıcı oluşturur.
Kordal grafiklerini karakterize etmek için minimal ayırıcılar kullanılabilir.
Grubu arasında -separators bir sağlanabilir ön siparişe tanımlanan aşağıdaki gibidir: herkes için -separators ve bir , elimizdeki eğer ayrı şekilde herhangi köşe ait . Escalante, minimal ayırıcılarla sınırlandırıldığında , bu ilişkinin tam bir kafesi tanımladığını göstermiştir .
(sen,v){\ displaystyle (u, v)}G{\ displaystyle G} ⊑sen,v{\ displaystyle \ sqsubseteq _ {u, v}}(sen,v){\ displaystyle (u, v)}S{\ displaystyle S}T{\ displaystyle T}G{\ displaystyle G}S⊑sen,vT{\ displaystyle S \ sqsubseteq _ {u, v} T}T{\ displaystyle T}S∖T{\ displaystyle S \ setminus T}v{\ displaystyle v}(sen,v){\ displaystyle (u, v)}
Bir grafiğin minimum ayırıcıları algoritmik problem çözmede kullanılabilir. Bu nedenle, ağaç genişliğinin hesaplanması gibi NP-zor bazı problemler , polinom zamandaki minimum ayırıcıları nasıl sıralayacağımızı bildiğimiz grafik sınıflarında, permütasyon grafikleri, kesişim grafikleri gibi polinom zamanda çözülebilir . dizeler d 'bir daire veya dairesel aralıklı grafikler.
Referanslar
-
Olivier Fouquet , Theory of graphs: kısa bir giriş: varsayılan bir cebirsel önyargı ile ( çevrimiçi okuyun )
-
(inç) Reinhard Diestel , Grafik Teorisi [ perakende sürümler ] , s. 11.
-
Örneğin Jacques Labelle , Théorie des graphes , modulo éditeur ,bin dokuz yüz Seksen bir( çevrimiçi okuyun ) sayfa 26
-
F. Escalante , " Graphen içinde Schnittverbände " Universität Hamburg der Abhandlungen aus dem mathematichen Semineri , uçuş. 38,
1972, s. 199–220 ( DOI 10.1007 / BF02996932 )
-
T. Kloks , H. Bodlaender , H. Müller ve D. Kratsch , “ Proc. 1. Avrupa Algoritmalar Sempozyumu (ESA'93) ”, Bilgisayar Bilimi Ders Notları , Springer-Verlag, cilt. 726,
1993, s. 260–271 ( DOI 10.1007 / 3-540-57273-2_61 )
İlgili makale
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">