Kuratowski Teoremi: Bir Graf Düzlemde Kesişmeden Çizilebilir mi?

"Üç ev üç tesis" bilmecesi

19. yüzyıl bilmecelerinden klasik: üç evi (A, B, C) ve üç tesisi (su, gaz, elektrik) düşünün. Her evi her tesise borularla bağlamak istiyorsunuz. Boruların hiçbiri kesişmesin. Mümkün mü?

Deneyin. 8 hattı çizdikten sonra 9. hat daima başka birini kesmek zorunda kalır. Mümkün değildir. Ama bunu kanıtlamak sezgisel olarak değil kombinatoryal-topolojik olarak gerekir.

Bu bilmeceye karşılık gelen graf $K_{3,3}$ ("tam iki-parçalı 3-3 graf"): 3 ev + 3 tesis = 6 düğüm, her ev-tesis çifti için bir kenar = 9 kenar.

Benzer bir graf, $K_5$ ("tam 5 düğümlü graf"): 5 düğüm, her ikisi arası birer kenar = 10 kenar. Pentagram çizmeyi denediğinizde bir kenarın bir başkasını kesmesi şart.

Bu iki graf — $K_5$ ve $K_{3,3}$ — düzlemde kesişmeden çizilemez. Kuratowski'nin teoreminin söylediği: bunlar tek "engel" — başka hiçbir engel yok.

Düzlemsel graf nedir?

Bir düzlemsel graf (planar graph), düzleme (kâğıda) düğüm ve kenar olarak çizilebilen ve kenarların yalnızca düğümlerde kesiştiği bir graftır. Eşdeğer ifade: kürenin yüzeyine çizilebilen bir graf.

Düzlemsel grafların sayısı, harita renklendirmesi, devre tasarımı, VLSI çip yerleşimi, sosyal ağ görselleştirmesi için temel öneme sahip. Düzlemsel olmayan grafları kâğıda çizemeyiz; çizmek için çapraz kullanmamız gerekir.

Kuratowski teoremi (1930)

Polonyalı topolog Kazimierz Kuratowski (1896-1980), 1930'da Varşova'da şu teoremi kanıtladı:

Bir sonlu graf $G$ düzlemseldir ancak ve ancak $K_5$ veya $K_{3,3}$'ün bir altbölümünü altgraf olarak içermiyorsa.

İki anahtar terim:

• Altgraf: düğüm/kenar kümesinin bir alt kümesi.
• Altbölüm (subdivision): bir grafın kenarlarına ek düğümler ekleyerek elde edilen graf. Örneğin bir kenarın ortasına bir düğüm koyup iki kenara bölmek.

Yani $G$'de "$K_5$'e benzeyen — kenarlar uzatılmış olabilir — bir alt yapı" varsa, $G$ düzlemsel değildir.

Eşdeğer: Wagner teoremi (1937)

Alman matematikçi Klaus Wagner, 7 yıl sonra eşdeğer bir karakterizasyon verdi: minör terimiyle.

Bir grafın minörü, altgrafından kenar kontraksiyonu (iki uçtaki düğümleri birleştirmek) ile elde edilen graf.

Wagner teoremi: $G$ düzlemseldir ⇔ $K_5$ ve $K_{3,3}$'ü minör olarak içermez.

Minör, altbölümden daha geniş bir kavram olduğundan Wagner'in formu pratikte (büyük graflarda) daha güçlüdür.

Euler formülü ile kanıtın özü

Euler formülü düzlemsel bağlı graf için:

$V - E + F = 2$

Burada $V$ düğüm, $E$ kenar, $F$ yüz sayısı. Bu formülü kullanarak düzlemsel grafın kenar sayısının düğüm sayısıyla sınırlı olduğu gösterilir: $E \leq 3V - 6$.

$K_5$: $V=5$, $E=10$. $3 \cdot 5 - 6 = 9 < 10$. Çelişki — $K_5$ düzlemsel olamaz.

$K_{3,3}$ için iki-parçalı yapı sayesinde her yüz en az 4 kenarla sınırlandığından sıkılaştırılmış formül: $E \leq 2V - 4$. $K_{3,3}$: $V=6$, $E=9$. $2 \cdot 6 - 4 = 8 < 9$. Çelişki — $K_{3,3}$ düzlemsel olamaz.

Bu iki çelişki "yeterlilik" tarafının yarısı; geri kalanı (yasaklı yapı içermeyen her grafın gerçekten çizilebilir olduğu) çok daha karmaşıktır.

Algoritmik düzlemsellik testi

Kuratowski teoremi ifade eder ama nasıl test edileceğini doğrudan söylemez. Test için saf yaklaşım $O(n^6)$ kadar yavaş olabilir.

1974'te Hopcroft ve Tarjan $O(n)$ — lineer zaman — bir algoritma verdi. Bugünkü graf görselleştirme yazılımları (Graphviz, yEd) bu temel üzerinde çalışır.

Genellemeler

1. Yüksek-cins yüzeyler: $K_5$ ve $K_{3,3}$ torus üzerinde çizilebilir. Her cinste yasaklı altgraflar vardır.
2. Robertson-Seymour teoremi (1983-2004): Düzlemsellik gibi her "minör altında kapalı" özellik sonlu sayıda yasaklı minör ile karakterize edilir. Modern graf teorisinin en derin sonuçlarından — 20 makalelik bir seri.
3. Knot teorisi: Düğümlerin düzleme çizilebilirliği analoglar.
4. Renklendirme: Dört Renk Teoremi sadece düzlemsel graflar için geçerlidir; Kuratowski karakterizasyonu olmadan ifade etmek zor olurdu.

Kuratowski hakkında kısa not

Kazimierz Kuratowski Varşova Polonya Okulu'nun (Sierpiński, Tarski, Banach gibi isimlerle) önemli üyesiydi. İkinci Dünya Savaşı sırasında Polonya'daki yer altı üniversitesinde matematik öğretti — Naziler matematiksel eğitimi yasakladığı için. Yetiştirdiği öğrenciler arasında Andrzej Mostowski ve Helena Rasiowa var.

Kuratowski'nin teoremi bugün her algoritma ve graf teorisi dersinde okutulur; Polonya matematik geleneğinin dünyaya en yaygın katkılarından biri.

Sonuç

"Üç ev üç tesis" gibi basit bir bilmecenin altında, sonlu sayıda yasaklı yapı ile karakterize edilebilen derin bir topolojik olgu yatıyor. Kuratowski teoremi, kombinatorik ve topoloji arasındaki bağı en zarif şekilde gösteren teoremlerden biri.

Bilgisayar grafiği, devre tasarımı, sosyal ağ analizi — hepsinin altında bu "iki yasaklı graf" var.