Riječnik

Odaberite jednu od ključnih riječi s lijeve strane ...

Grafikoni i mrežeRavni grafikoni

Vrijeme čitanja: ~25 min
Ova je stranica automatski prevedena i može sadržavati pogreške. Javite nam se ako nam želite pomoći u pregledu prijevoda!

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 ...

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.

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