Gràfics i xarxesGràfics plans
Heus aquí un altre trencaclosques relacionat amb la teoria de gràfics.
En un petit poble hi ha tres cases i tres plantes d’utilitat que produeixen aigua, llum i gas. Hem de connectar cadascun dels cursos a cadascuna de les plantes d’utilitat, però, a causa del traçat del poble, no es poden creuar les diferents canonades i cables.
Proveu de connectar cadascuna de les cases amb cadascuna de les empreses de serveis a sota, sense que cap de les vostres línies s’hi creui
Igual que els ponts de Königsberg abans, descobriu ràpidament que aquest problema també és impossible. Sembla que alguns gràfics es poden dibuixar sense sobreposar-se a les arestes (es diuen gràfics plans ), però d'altres no.
El
El gràfic del trencaclosques de les tres utilitats és el
Planaritat
Aquest és un gràfic pla, però el
Fórmula d'Euler
Tots els gràfics plans divideixen el pla en què es dibuixen en diverses zones, anomenades cares .
11 vèrtexs + cares
15 vèrtexs + cares
25 vèrtexs + cares
Quan compareu aquests nombres, notareu que el nombre d'arcs és sempre
Malauradament, hi ha infinites gràfiques i no podem comprovar cadascú per veure si funciona l’equació d’Euler. En lloc d'això, podem intentar trobar una
F | V | E |
0 | 1 | 0 |
0 + 1 = 0 + 1
Qualsevol gràfic (finit) es pot construir començant per un vèrtex i afegint més vèrtexs un per un. Hem demostrat que, segons la manera d’afegir nous vèrtexs, l’equació d’Euler és vàlida. Per tant, és vàlid per a tots els gràfics.
El procés que hem utilitzat s’anomena inducció matemàtica . És una tècnica molt útil per demostrar resultats en infinitat de casos, simplement començant pel cas més senzill i mostrant que el resultat es manté a cada pas quan es construeixen casos més complexos.
Molts gràfics plans semblen molt similars a les xarxes de


Això significa que podem utilitzar la fórmula d’Euler no només per a gràfics plans, sinó també per a tots els poliedres, amb una petita diferència. En transformar els políedres en gràfics, una de les cares desapareix: la cara superior del políedre es converteix en la “exterior”; dels gràfics.
En altres paraules, si compta el nombre de vores , cares i vèrtexs de qualsevol poliedre, ho trobareu F + V = E +
Icosaedre
20 cares
12 vèrtexs
30 Vores
Ròmbicosidodecaedre
62 cares
60 vèrtexs
120 Vores
Icosaedre troncocònic
32 cares (12 negres, 20 blancs)
60 vèrtexs
90 Vores