Grafice și rețeleGraficele planare

Iată un alt puzzle care are legătură cu teoria graficului.

Într-un sat mic există trei case și trei uzine care produc apă, energie electrică și gaz. Trebuie să conectăm fiecare dintre cursuri la fiecare dintre instalațiile de utilitate, dar, datorită amenajării satului, nu se permite traversarea țevilor și cablurilor.

Încercați să conectați fiecare dintre case la fiecare dintre companiile de servicii de mai jos, fără ca oricare dintre liniile dvs. să se intersecteze:

La fel ca podurile din Königsberg înainte, descoperiți rapid că această problemă este imposibilă. Se pare că unele grafice pot fi desenate fără margini suprapuse - acestea se numesc grafice plane - dar altele nu pot.

K3 este planar.

K4 .

K5 .

Graficul complet K5 este cel mai mic grafic care nu este plan. Orice alt grafic care conține K5 întrucât, într-un fel, o subgrafă nu este plană. Aceasta include K6 . K7 , și toate graficele complete mai mari.

Graficul din puzzle-ul celor trei utilități este graficul bipartit K3,3 . Se pare că orice grafic non-planar trebuie să conțină fie o K5 sau a K3,3 (sau o subdiviziune a acestor două grafice) ca subgrafă. Aceasta se numește teorema lui Kuratowski .

Planarity

Acesta este un grafic plan, dar ${n} vârfurile au fost zguduite. Rearanjați vârfurile astfel încât niciunul dintre margini să nu se suprapună.

Formula lui Euler

Toate graficele plane împart planul pe care sunt desenate într-un număr de zone, numite fețe .

Vârfuri fețe muchii 11 Vârfuri + fețe

Vârfuri fețe muchii 15 Vârfuri + fețe

Vârfuri fețe muchii 25 Vârfuri + fețe

Când compari aceste numere, vei observa că numărul de muchii este întotdeauna decât numărul de fețe plus numărul de vârfuri. Cu alte cuvinte, F + V = E + 1. Acest rezultat se numește ecuația lui Euler și poartă numele aceluiași matematician care a rezolvat problema Königsberg Bridges.

Din păcate, există foarte multe grafice și nu putem verifica fiecare pentru a vedea dacă ecuația lui Euler funcționează. În schimb, putem încerca să găsim o simplă dovadă care funcționează pentru orice grafic ...

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.

Orice grafic (finit) poate fi construit începând cu un vertex și adăugând mai multe vertexuri unul câte unul. Am arătat că, indiferent de modul în care adăugăm noi noduri, ecuația lui Euler este valabilă. Prin urmare, este valabil pentru toate graficele.

Procesul pe care l-am folosit se numește inducție matematică . Este o tehnică foarte utilă pentru dovedirea rezultatelor în infinit de multe cazuri, pur și simplu începând cu cel mai simplu caz și arătând că rezultatul se menține la fiecare pas atunci când se construiește cazuri mai complexe.

Multe grafice plane arată foarte asemănătoare cu plasele de poliedre , cu forme tridimensionale cu fețe poligonale . Dacă ne gândim la poliedre ca fiind formate din benzi elastice, ne putem imagina întinzându-le până devin grafice plane, plane:

Aceasta înseamnă că putem folosi formula lui Euler nu numai pentru graficele plane, ci și pentru toate poliedrele - cu o mică diferență. La transformarea poliedrelor în grafice, una dintre fețe dispare: fața superioară a poliedrului devine „afară”; a graficelor.

Cu alte cuvinte, dacă numeri numărul de marginile , chipuri și vârfuri ale oricărui poliedru, veți găsi asta F + V = E + .

icosahedron 20 de fețe 12 Vârfuri 30 muchii

Rhombicosidodecahedron 62 fețe 60 Vârfuri 120 muchii

Icozaedru trunchiat 32 fețe (12 negre, 20 alb) 60 Vârfuri 90 muchii

Schimbă limba

Conectați-vă la Mathigon

Acțiune

Resetați Progresul

Glosar

Grafice și rețeleGraficele planare

Planarity

Formula lui Euler