Grafikoni i mrežeRavni grafikoni

Evo još jedne zagonetke koja je povezana s teorijom grafova. U malom selu postoje tri kuće i tri komunalna postrojenja koja proizvode vodu, struju i plin. Moramo povezati svaki tečaj sa svakim komunalnim postrojenjem, ali zbog rasporeda sela različite cijevi i kablovi nisu dopušteni.

Pokušajte spojiti svaku kuću dolje u bilo kojem od komunalnih poduzeća, a da se ni jedan od vaših linija ne presijeca:

Baš kao prije Königsbergovih mostova, brzo otkrijete da je i ovaj problem nemoguć. Čini se da se neki grafikoni mogu nacrtati bez rubova koji se preklapaju - oni se nazivaju ravninskim grafovima - ali drugi ne mogu.

K3 je ravan.

K4 .

K5 .

kompletan grafikon K5 najmanji je graf koji nije ravan. Bilo koji drugi graf koji sadrži K5 kao podgraf na neki način također nije ravan. To uključuje K6, K7 i sve veće cjelovite grafikone. Graf u slagalici s tri komunalije je dvostrani graf K3,3. Ispada da svaki neplanarni graf mora sadržavati K5 ili K3,3 (ili potpodjelu ova dva grafikona) kao podgraf. To se zove Kuratovski teorem.

Planarnost

Ovo je ravan graf, ali su ${n} vrhovi uništeni. Rasporedite vrhove tako da se nijedan od rubova ne preklapa.

Eulerova formula

Svi ravni planeri dijele ravninu na koju su nacrtani, na brojna područja koja se nazivaju lica.

Vrhovi Lica Rubovi 11 vrhova + lica

vrhovi Lica Rubovi 15 vrhova + lica

vrhovi Lica Rubovi 25 vrhova i lica

Kada uspoređujete ove brojeve, primijetit ćete da je broj rubova uvijek od broja lica plus broj vrhova. Drugim riječima, F + V = E + 1. Taj se rezultat zove Eulerova jednadžba i ime je dobio po istom matematičaru koji je riješio problem Königsbergovih mostova. Nažalost, postoji beskonačno puno grafova i ne možemo provjeriti svaki da vidimo djeluje li Eulerova jednadžba. Umjesto toga, možemo pokušati pronaći jednostavan dokaz koji djeluje za bilo koji graf ...

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.

Bilo koji (konačni) graf može se konstruirati počevši s jednim vrhom i dodavanjem više vrhova jedan po jedan. Pokazali smo da, na koji god način dodali nove vrhove, vrijedi Eulerova jednadžba. Stoga vrijedi za sve grafikone. Proces koji smo koristili naziva se matematička indukcija. Vrlo je korisna tehnika dokazivanja rezultata u beskonačno mnogim slučajevima, jednostavno počevši od najjednostavnijeg slučaja i pokazujući da se rezultat drži na svakom koraku prilikom konstrukcije složenijih slučajeva. .svg-block: include svg/dominoes.svg

Mnogi ravni planeti izgledaju vrlo slično mrežama poliedra, trodimenzionalnim oblicima s poligonalnim licima. Ako mislimo na poliedre kao na elastične vrpce, možemo zamisliti da ih rastežemo dok oni ne postanu ravni, ravninski grafikoni:

To znači da mogu koristiti Eulerovu formulu ne samo za ravnine grafova već i za sve poliedre - s jednom malom razlikom. Prilikom pretvaranja poliedra u grafikone jedno lice nestaje: gornje lice poliedra postaje „izvan“; grafova. Drugim riječima, ako računate broj rubova, lica i vrhova od bilo poliedrom, otkrit ćete da je F + V = E + .

Ikozaedar 20 Lica 12 Vrhovi 30 Rubovi

Rhombicosidodekahedron 62 Lica 60 Vrhovi 120 Rubovi

Urezan ikosahedron 32 Lica (12 crnih, 20 bijelih) 60 Vrhovi 90 Rubovi

Promjena jezika

Prijavite se u Mathigon

Podijeli

Poništavanje napretka

Riječnik

Grafikoni i mrežeRavni grafikoni

Planarnost

Eulerova formula