Bipartit grafiği tamamlayın

Bipartit grafiği tamamlayın
${\ görüntü stili K_ {3,2}}$

Değerlendirme	$K _ {{m, n}}$
köşe sayısı	${\ görüntü stili m + n}$
Kenar sayısı	$milyon$
Derece dağılımı	m derece köşeleri , n , n derecesi tepe noktası m
Çap	2

Olarak grafik teorisi , bir grafiktir olduğu söylenir tam ikili (denen veya hatta biclique bu ise) ikili ve birinci kümedeki her köşe ikinci kümenin her köşe noktalarına bağlanmıştır. Daha doğrusu, orada var olan bölüm iki alt-grup halinde köşe onun setinin ve böyle her köşe o her köşe bağlanır . $sen$ $V$ $sen$ $V$

Birinci küme m temeline ve ikinci küme n ana kümesine aitse, tam iki parçalı grafik gösterilir . $sen$ $V$ $K _ {{m, n}}$

Örnekler

Yıldızlar

Eğer m = 1, tam ikili grafik K 1, n, a, yıldız ve gösterilir . $S_ {n}$

Özellikle yıldızlar ağaçlardır . Ayrıca, ağaç olan tüm tam iki parçalı grafikler yıldızdır .

Diğer örnekler

İşte m = 3 için örnekler.

K 3.1
K 3.2
K 3.3

K 3.3 grafiği , düzlemsel olmayan en küçük kübik grafiktir . Bu vasıflandırılmasında kullanılan düzlemsel grafikler arasında Kazimierz Kuratowski Klaus Wagner | ve [[Klaus Wagner ]]. Üç evin bilmecesinin arkasında oturan odur .

Özellikleri

Grafik ailesi kapanımları

Tam iki parçalı grafik , bir Moore grafiği ve bir -kafesidir . ${\ görüntü stili K_ {n, n}}$ ${\ görüntü stili (n, 4)}$
Tam iki parçalı grafikler ve [[Turán grafiği | Turán grafikleri ]]. ${\ görüntü stili K_ {n, n}}$ ${\ görüntü stili K_ {n, n + 1}}$
Tam ikili grafiktir a, simetrik grafiktir : bu kenar geçişli, tepe-geçişli ve ark geçişlidir . ${\ görüntü stili K_ {n, n}}$
Sayısı kapsayan ağaç tam ikili grafik olup . $K _ {{m, n}}$ ${\ displaystyle m ^ {n-1} n ^ {m-1}}$

değişmezler

Karakteristik polinom tam ikili grafik olup: . Bu karakteristik polinom, ancak ve ancak mn bir tam kare ise tam kökleri kabul eder . Tam iki parçalı grafik bu nedenle yalnızca bu durumda bir integral grafiğidir . $K _ {{m, n}}$ ${\ displaystyle x ^ {m + n-2} (x ^ {2} -mn)}$

kullanır

Kuratowski teoremi düzlemsel grafikler karakterize grafiğini kullanarak . $K_ {3.3}$

varsayım

Biz göstermek geçiş noktalarının sayısının grafiğinin , olası parseller arasında geçişlerin en az sayıda . Kazimierz Zarankiewicz , sorununu çözmek isteyen Pál Turan tuğla fabrikasında , kurulan aşağıdaki işareti makyaj : ${\ displaystyle \ matematik {cr} (G)}$ $G$ $G$

{\ displaystyle {\ textrm {cr}} (K_ {m, n}) \ leq \ left \ lfloor {\ frac {n} {2}} \ sağ \ rfloor \ sol \ lfloor {\ frac {n-1} {2}} \ sağ \ rfloor \ sol \ lfloor {\ frac {m} {2}} \ sağ \ rfloor \ sol \ lfloor {\ frac {m-1} {2}} \ sağ \ rfloor}

Bu eşitsizliğin bir eşitlik olduğu varsayılır.

Algoritmik yönler ve uygulamalar

Bir grafiktir verilen G tam ikili kaynaklı alt grafiğini bulmak ve G (dolayısıyla ile mümkün olduğu kadar çok kenarlı olarak sahip , bir maksimal) olan NP-tam sorun . $K _ {{m, n}}$ $milyon$

Notlar ve referanslar

(içinde) Steven Klee ve Matthew T. Stamps, " Ağaç sayımını kapsayan doğrusal cebirsel teknik " , Amer. Matematik. Aylık , cilt. 127, n o 4,2020, s. 297-307 ( DOI 10.1080 / 00029890.2020.1708171 ).
Daha fazla ayrıntı için makale düzlemsel grafiğine bakın .
Orijinal makale: Kazimierz Kuratowski , “ Topolojide sol eğriler sorunu üzerine ”, Fon. Matematik. , cilt. 15,1930, s. 271-283 ( çevrimiçi okuyun ). Ayrıca bakınız: (tr) Carsten Thomassen , “ Kuratowski teoremi ” , Journal of Graph Theory , cilt. 5 ,, n o 3,bin dokuz yüz Seksen bir, s. 225-241 ( DOI 10.1002 / jgt.3190050304 , Matematik İncelemeleri 625064 ).
(in) K. Zarankiewicz , " P. Turán grafikleri ile ilgili bir sorundur " , Fon. Matematik. , cilt. 41,1954, s. 137–145.
Richard K. Guy , Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) , Academic Press, New York,1969( Matematik İncelemeleri 0253931 ) , s. 63-69.

İlgili makale

Graham-Pollak teoremi