Gràfics i xarxesGràfics plans

Aquesta pàgina ha estat traduïda automàticament i pot contenir errors. Poseu-vos en contacte si voleu ajudar-nos a revisar les traduccions.

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.

K3 és pla.

K4 .

K5 .

El gràfic complet K5 és el gràfic més petit que no és pla. Qualsevol altre gràfic que contingui K5 com a subgraf d’alguna manera tampoc és planer. Això inclou K6 , K7 i tots els gràfics complets més grans.

El gràfic del trencaclosques de les tres utilitats és el gràfic del bipartit K3,3 . Resulta que qualsevol gràfic no pla ha de contenir una K5 o a K3,3 (o una subdivisió d'aquests dos gràfics) com a subgraf. D’això s’anomena teorema de Kuratowski .

Planaritat

Aquest és un gràfic pla, però el ${n} els vèrtexs s’han revoltat. Reordeneu els vèrtexs de manera que cap de les vores se superposi.

Fórmula d'Euler

Tots els gràfics plans divideixen el pla en què es dibuixen en diverses zones, anomenades cares .

vèrtexs
cares
Vores
11 vèrtexs + cares

vèrtexs
cares
Vores
15 vèrtexs + cares

vèrtexs
cares
Vores
25 vèrtexs + cares

Quan compareu aquests nombres, notareu que el nombre d'arcs és sempre al nombre de cares més el nombre de vèrtexs. En altres paraules, F + V = E + 1. Aquest resultat s’anomena equació d’Euler i rep el nom del mateix matemàtic que va resoldre el problema de Ponts de Königsberg.

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 prova senzilla que funcioni per a qualsevol gràfic ...

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.

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 políedres , formes tridimensionals amb cares poligonals . Si pensem en els poliedres constituïts per bandes elàstiques, podem imaginar estirar-los fins a convertir-los en gràfics plans i plans:

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

Inicieu la sessió a Mathigon

Compartir

Envieu-nos comentaris

Gràcies pels teus suggeriments!

Configuració

Preferències de visualització

Restableix el progrés

Glossari

Gràfics i xarxesGràfics plans

Planaritat

Fórmula d'Euler

Canviar d'idioma