50 clés pour comprendre les maths
118
D’après ce qui précède, N est pair et il est clair que Ny est pair également. De plus,
on a Nx + Ny = N et, et donc Nx = N – Ny. Il s’ensuit que Nx est pair. Cela implique
que x est pair, car, sinon Nx serait impair puisque la somme d’un nombre impair de
degré impair donne un nombre impair.
Graphes non planaires Le casse-tête des trois maisons est un classique.
Imaginez trois maisons et trois bornes pour les alimenter en gaz, électricité, et eau. Il
faut relier chacune des maisons à chacune des bornes, mais un problème se pose : aucun croisement ne doit se produire.
En réalité, c’est impossible, mais vous pouvez
faire l’essai avec des amis qui ignorent tout du
problème. Le graphe obtenu en reliant trois
points à trois autres points de toutes les manières
possibles (en utilisant neuf arcs seulement) ne
peut pas être dessiné dans le plan sans que des
croisements ne se produisent. Un tel graphe est
dit non-planaire. Ce graphe des trois maisons et
le graphe constitué de tous les arcs qui relient
cinq points occupent tous deux une place particulière dans la théorie des graphes. En 1930, le
mathématicien polonais Kazimierz Kuratowski
a prouvé ce théorème surprenant selon lequel un
graphe est planaire si et seulement si il ne contient
aucun des deux graphes précédents.
Les arbres Un « arbre » est une sorte particulière de graphe, très différente du
graphe des trois maisons ou de celui des ponts de Königsberg. Dans le problème des
ponts de Königsberg, il était possible de commencer en un point et d’y retourner
par un chemin différent. Un tel trajet qui part d’un point pour y revenir s’appelle
un cycle. Un arbre est un graphe qui n’a pas de cycle.
Un exemple connu de ce type de graphe se trouve dans la structure des répertoires
des ordinateurs. Ils sont arrangés selon une hiérarchie constituée d’un répertoire
G
1
É
E
2
3
Racine
118
D’après ce qui précède, N est pair et il est clair que Ny est pair également. De plus,
on a Nx + Ny = N et, et donc Nx = N – Ny. Il s’ensuit que Nx est pair. Cela implique
que x est pair, car, sinon Nx serait impair puisque la somme d’un nombre impair de
degré impair donne un nombre impair.
Graphes non planaires Le casse-tête des trois maisons est un classique.
Imaginez trois maisons et trois bornes pour les alimenter en gaz, électricité, et eau. Il
faut relier chacune des maisons à chacune des bornes, mais un problème se pose : aucun croisement ne doit se produire.
En réalité, c’est impossible, mais vous pouvez
faire l’essai avec des amis qui ignorent tout du
problème. Le graphe obtenu en reliant trois
points à trois autres points de toutes les manières
possibles (en utilisant neuf arcs seulement) ne
peut pas être dessiné dans le plan sans que des
croisements ne se produisent. Un tel graphe est
dit non-planaire. Ce graphe des trois maisons et
le graphe constitué de tous les arcs qui relient
cinq points occupent tous deux une place particulière dans la théorie des graphes. En 1930, le
mathématicien polonais Kazimierz Kuratowski
a prouvé ce théorème surprenant selon lequel un
graphe est planaire si et seulement si il ne contient
aucun des deux graphes précédents.
Les arbres Un « arbre » est une sorte particulière de graphe, très différente du
graphe des trois maisons ou de celui des ponts de Königsberg. Dans le problème des
ponts de Königsberg, il était possible de commencer en un point et d’y retourner
par un chemin différent. Un tel trajet qui part d’un point pour y revenir s’appelle
un cycle. Un arbre est un graphe qui n’a pas de cycle.
Un exemple connu de ce type de graphe se trouve dans la structure des répertoires
des ordinateurs. Ils sont arrangés selon une hiérarchie constituée d’un répertoire
G
1
É
E
2
3
Racine