Bölünmüş grafik - Split graph

Bir klik ve bağımsız bir kümeye bölünmüş bir bölünmüş grafik.

Olarak grafik teorisi , matematik bir dalı, bir bölme grafik noktaların bir içine bölümlenmiş olabilir ki burada bir grafiktir klik ve bağımsız bir set . Bölünmüş grafikler ilk olarak Földes ve Hammer  ( 1977a , 1977b ) tarafından çalışılmış ve bağımsız olarak Tyshkevich ve Chernyak ( 1979 ) tarafından tanıtılmıştır .

Bölünmüş bir grafik, bir klik ve bağımsız bir kümede birden fazla bölüme sahip olabilir; örneğin, a – b – c yolu , köşeleri üç farklı şekilde bölünebilen bölünmüş bir grafiktir:

1. { a , b } kliği ve { c } bağımsız kümesi
2. { b , c } kliği ve { a } bağımsız kümesi
3. { b } kliği ve { a , c } bağımsız kümesi

Bölünmüş grafikler, yasaklanmış indüklenmiş alt grafikleri açısından karakterize edilebilir : bir grafik, ancak ve ancak hiçbir indüklenmiş alt grafiğin dört veya beş köşede bir çevrim veya bir çift ayrık kenar (4 çevrimin tamamlayıcısı) olmaması durumunda bölünür .

Diğer grafik aileleriyle ilişkisi

Tanımdan, bölünmüş grafikler tamamlama altında açıkça kapalıdır . Bölünmüş grafiklerin başka bir karakterizasyonu tamamlama içerir: bunlar , tamamlayıcıları da kordal olan akorlu grafiklerdir . Kordal grafikler ağaçların alt ağaçlarının kesişim grafikleri olduğu gibi, bölünmüş grafikler de yıldız grafiklerinin farklı alt yıldızlarının kesişim grafikleridir . Hemen hemen tüm kiriş grafikleri bölünmüş grafiklerdir; yani, n sonsuza giderken limitte, bölünmüş olan n -köşe kiriş grafiklerinin kesri bire yaklaşır.

Kordal grafikler mükemmel olduğundan, bölünmüş grafikler de öyle. Çift parçalı grafikleri , mükemmel grafikler beş temel sınıfları olarak belirgin bir şekilde, şekil, her köşe (klik bir antimatching ve bağımsız set indükleme gelecek şekilde eşleşen bir indükleme gelir) iki katına bölme grafikler türetilen grafikler bir aile olan diğerleri Chudnovsky ve diğerleri tarafından ispatta oluşturulabilir . (2006) ait Güçlü Mükemmel Grafik Teoremi .

Bir grafik hem bölünmüş grafik hem de aralık grafiğiyse , tamamlayıcısı hem bölünmüş grafik hem de karşılaştırılabilirlik grafiğidir ve bunun tersi de geçerlidir. Bölünmüş karşılaştırılabilirlik grafikleri ve dolayısıyla bölünmüş aralık grafikleri, bir dizi yasaklanmış indüklenmiş alt grafik olarak karakterize edilebilir. Bölünmüş cograph'lar tam olarak eşik grafikleridir . Bölünmüş permütasyon grafikleri tam olarak aralık grafiği tamamlayıcılarına sahip aralık grafikleridir; bunlar, çarpık birleştirilmiş permütasyonların permütasyon grafikleridir . Bölünmüş grafikler kokromatik sayı 2'ye sahiptir.

algoritmik problemler

G , bir C kliği ve bağımsız bir I kümesine bölünmüş bir bölünmüş grafik olsun . O zaman bölünmüş bir grafikteki her maksimum klik ya C'nin kendisidir ya da I'deki bir köşenin komşuluğudur . Böylece, bir bölünmüş grafikte maksimum kliği ve tamamlayıcı olarak maksimum bağımsız kümeyi belirlemek kolaydır . Herhangi bir bölünmüş grafikte, aşağıdaki üç olasılıktan biri doğru olmalıdır:

1. Bir tepe vardır X de bir şekilde Cı- ∪ { x } tamamlanır. Bu durumda, C ∪ { x } bir maksimum klik ve I bir maksimum bağımsız kümedir.
2. Bir tepe vardır X in C , öyle ki bir ∪ { x } bağımsızdır. Bu durumda, I ∪ { x } bir maksimum bağımsız kümedir ve C bir maksimum kliktir.
3. C bir maksimal klik ve I bir maksimal bağımsız kümedir. Bu durumda, G'nin bir klik ve bağımsız bir küme olarak benzersiz bir bölümü ( C , I ) vardır, C maksimum klik ve I maksimum bağımsız kümedir.

Grafik renklendirme de dahil olmak üzere daha genel grafik ailelerinde NP-tamamlanmış olan diğer bazı optimizasyon sorunları , bölünmüş grafiklerde benzer şekilde basittir. Bir Hamilton döngüsü bulmak , güçlü bir şekilde kordal grafikler olan bölünmüş grafikler için bile NP-tam kalır . Ayrıca, bölünmüş grafikler için Minimum Hakim Küme probleminin NP-tam olarak kaldığı da iyi bilinmektedir .

derece dizileri

Bölünmüş grafiklerin dikkate değer bir özelliği, yalnızca derece dizilerinden tanınabilmeleridir . Bir grafik derecesi dizisi olsun G olmak d ₁ ≥ d ₂ ≥ ... ≥ d _{, n} ve izin m, en büyük değeri i öyle ki d _i ≥ i - 1 O G bölünmüş bir grafiktir, ancak ve ancak

${\displaystyle \sum _{i=1}^{m}d_{i}=m(m-1)+\sum _{i=m+1}^{n}d_{i}.}$

Bu durumda ise, o zaman m, büyük derecelerde köşeler maksimum bir klik oluşturan G ve geri kalan köşe bağımsız bir set oluşturmaktadır.

Bölünmüş grafikleri sayma

(2000) Royle gösterdi N ile -vertex bölünmüş grafikler N olan bire bir karşılık bazı ile Sperner ailesine . Bu gerçeği kullanarak, n köşedeki izomorfik olmayan bölünmüş grafiklerin sayısı için bir formül belirledi . n'nin küçük değerleri için , n = 1'den başlayarak , bu sayılar

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64.956, 501.696, ... (dizi A048194 olarak OEIS ).

Bu enumerative sonuç, daha erken ispat edildi Tyshkevich & Chernyak (1990) .

Notlar

Referanslar

daha fazla okuma

• Bölünmüş grafikler üzerine bir bölüm Martin Charles Golumbic'in "Algorithmic Graph Theory and Perfect Graphs" kitabında yer almaktadır .