Graphes et réseauxGraphes plans

Voici un autre casse-tête lié à la théorie des graphes.

Dans un petit village, il existe trois centrales produisant de l’eau, de l’électricité et du gaz. Il y a aussi trois maisons qui doivent être desservies. Malheureusement, en raison de la configuration de la ville, les tuyaux ou les câbles de chaque produit ne sont pas autorisés à se croiser.

Essayez de connecter chacune des plantes ci-dessous à chacune des maisons, sans qu’une de vos lignes ne se croise:

Tout comme les ponts de Königsberg, vous découvrez rapidement que ce problème est également impossible. Il semble que certains graphiques puissent être dessinés sans bords se chevauchant - il s’agit de graphes plans - mais d’autres ne le peuvent pas.

K3 est planaire.

K4 .

K5 .

Le graphe complet K5 est le plus petit graphe non planaire. Tout autre graphe contenant K5 comme sous-graphe n’est pas non plus planaire. Ceci inclut K6, K7 et tous les graphiques complets plus grands.

Le graphique du puzzle des trois utilitaires est le graphique bipartite K3,3. Il s'avère que tout graphe non planaire doit contenir une sous-division K5 ou K3,3 ou sous forme de sous-graphe.

Planarité

C'est un graphe planaire, mais les ${n} sommets ont été brouillés. Réorganisez les sommets de manière à ce qu'aucun des bords ne se chevauche.

Formule d'Euler

Tous les graphes plans divisent le plan sur lequel ils sont dessinés en un certain nombre de zones, appelées faces.

sommets faces arêtes 11 sommets + faces

sommets faces arêtes 15 sommets + faces

sommets faces arêtes 25 sommets + faces

En comparant ces nombres, vous remarquerez que le nombre d'arêtes correspond toujours à de moins que le nombre de faces plus le nombre de sommets. En d'autres termes, F + V = E + 1. Ce résultat s'appelle l'équation d'Euler et est nommé d'après le même mathématicien qui a résolu le problème des ponts de Königsberg.

Malheureusement, il existe une infinité de graphiques et nous ne pouvons pas vérifier chacun d’eux pour voir si l’équation d’Euler fonctionne. Au lieu de cela, nous pouvons essayer de trouver une preuve simple qui fonctionne pour tous les graphes…

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.

Tout graphe (fini) peut être construit en commençant par un sommet et en ajoutant plusieurs sommets un à un. Nous avons montré que, quelle que soit la manière dont nous ajoutons de nouveaux sommets, l’équation d’Euler est valide. Par conséquent, il est valable pour tous les graphiques.

Le processus que nous avons utilisé s'appelle l'induction mathématique. C'est une technique très utile pour prouver des résultats dans une infinité de cas, en commençant par le cas le plus simple et en montrant que le résultat est valable à chaque étape lors de la construction de cas plus complexes.

De nombreux graphes plans ressemblent beaucoup aux réseaux de polyèdres, des formes tridimensionnelles à faces polygonales. Si nous pensons que les polyèdres sont constitués d’élastiques, nous pouvons les étendre jusqu’à ce qu’ils deviennent des graphiques plats et plats:

Cela signifie que nous pouvons utiliser la formule d'Euler non seulement pour les graphes plans, mais aussi pour tous les polyèdres - à une petite différence près. Lors de la transformation des polyèdres en graphiques, une des faces disparaît: la face la plus haute du polyèdre devient le "dehors"; des graphiques.

En d'autres termes, si vous comptez le nombre de arêtes, faces et sommets de toutes polyèdre, vous constaterez que F + V = E + .

Icosahedron 20 Faces 12 Sommets 30 Bords

Rhombicosidodecahedron 62 Faces 60 Vertices 120 Bords

Icosaèdre tronqué 32 faces (12 noires, 20 blanches) 60 sommets 90 bords

Changer de langue

Connectez-vous à Mathigon

Partager

Réinitialiser la progression

Glossaire

Graphes et réseauxGraphes plans

Planarité

Formule d'Euler