Sözlük

Soldaki anahtar kelimelerden birini seçin…

Grafikler ve AğlarDüzlemsel Grafikler

Okuma zamanı: ~25 min
Bu sayfa otomatik olarak çevrilmiştir ve hatalar içerebilir. Çevirileri incelememize yardımcı olmak istiyorsanız lütfen iletişime geçin!

İşte grafik teorisi ile ilgili başka bir bulmaca.

Küçük bir köyde su, elektrik ve gaz üreten üç ev ve üç tesis vardır. Kursların her birini yardımcı tesislerin her birine bağlamamız gerekiyor, ancak köyün düzeni nedeniyle, farklı boru ve kabloların geçmesine izin verilmiyor.

Evlerin her birini, herhangi bir hattınız kesişmeden aşağıdaki yardımcı şirketlere bağlamaya çalışın:

Tıpkı Königsberg köprülerinde olduğu gibi, bu sorunun da imkansız olduğunu çabucak keşfediyorsunuz. Bazı grafikler üst üste binen kenarlar olmadan çizilebilir - buna düzlemsel grafikler denir - ancak diğerleri çizilemez.

K3 düzlemseldir.

K4 .

K5 .

Grafiğin tamamı K5 düzlemsel olmayan en küçük grafiktir. İçeren tüm diğer grafikler K5 bir şekilde bir alt-tabaka da düzlemsel değildir. Bu içerir K6 , K7 ve daha büyük tam grafikler.

Üç yardımcı program bulmacasındaki grafik iki taraflı grafiktir K3,3 . Herhangi bir düzlemsel olmayan grafiğin bir K5 veya bir K3,3 (veya bu iki grafiğin bir alt bölümü ) bir alt grafik olarak. Buna Kuratowski teoremi denir.

Düzlemsellik

Bu düzlemsel bir grafik, ancak ${n} köşeler karıştırıldı. Köşeleri, kenarların hiçbiri çakışmayacak şekilde yeniden düzenleyin.

Euler Formülü

Tüm düzlemsel grafikler, çizildikleri düzlemi yüz adı verilen bir dizi alana bölerler.

Köşebent
Yüz
Kenar
11 Noktalar + Yüzler

Tepe Noktaları
Yüz
Kenar
15 Tepe Noktası + Yüzler

Tepe Noktası
Yüzler
Kenar
25 Tepe Noktası + Yüzler

Bu sayıları karşılaştırırken, kenar sayısının her zaman olduğunu göreceksiniz. yüz sayısı artı köşe sayısı ile . Diğer bir deyişle, F + V = E + 1. Bu sonuca Euler denklemi denir ve adını Königsberg Bridges problemini çözen aynı matematikçiden alır .

Ne yazık ki, sonsuz sayıda grafik var ve Euler denkleminin işe yarayıp yaramadığını görmek için her birini kontrol edemiyoruz. Bunun yerine, herhangi bir grafik için işe yarayan basit bir kanıt bulmaya çalışabiliriz…

FVE
010

0 + 1  =  0 + 1

The simplest graph consists of a single vertex. We can easily check that Euler’s equation works.
Let us add a new vertex to our graph. We also have to add an edge, and Euler’s equation still works.
If we want to add a third vertex to the graph we have two possibilities. We could create a small triangle: this adds one vertex, one face and two edges, so Euler’s equation still works.
Instead we could simply extend the line by one: this adds one vertex and one edge, and Euler’s equation works.
Let’s keep going: if we now create a quadrilateral we add one vertex, two edges and one face. Euler’s equation still works.

Herhangi bir (sonlu) grafik, bir tepe noktasıyla başlayıp tek tek daha fazla köşe ekleyerek oluşturulabilir. Yeni köşeler eklesek de Euler denkleminin geçerli olduğunu gösterdik. Bu nedenle tüm grafikler için geçerlidir.

Kullandığımız sürece matematiksel tümevarım denir. Sadece en basit durumdan başlayarak ve daha karmaşık vakalar oluştururken sonucun her adımda geçerli olduğunu göstererek, sonsuz sayıda vakada sonuçları kanıtlamak için çok yararlı bir tekniktir.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Bir çok düzlemsel grafikleri polyhedra ağları, poligon yüzeye üç boyutlu şekiller, çok benzer. Çokyüzlüyü elastik bantlardan yapılmış olarak düşünürsek, düz, düzlemsel grafikler olana kadar onları uzatarak hayal edebiliriz:

Bu, Euler formülünü sadece düzlemsel grafikler için değil, aynı zamanda tüm polihedra için de kullanabileceğimiz anlamına gelir - küçük bir fark. Polihedra grafiklere dönüştürülürken, yüzlerden biri kaybolur: polihedranın en üst yüzü “dış” olur; grafikleri.

Başka bir deyişle, kenarlar , yüzler ve Herhangi bir polihedronun köşeleri , F + V = E + .

ikosahedron
20 Yüz
12 Tepe Noktası
30 Kenar

Rhombicosidodecahedron
62 Yüzler
60 Tepe Noktası
120 Kenar

Kesik İkosahedron
32 Yüz (12 siyah, 20 beyaz)
60 Tepe Noktası
90 Kenar

Archie