Les graphes 117
1930
Kuratowski prouve
le théorème des graphes
planaires.
1935
George Pólya développe
des techniques algébriques
d’énumération des graphes.
1999
Eric Rains et Neil Sloane
développent l’énumération
des structures arborescentes.
pouvoir quitter la berge sur laquelle on se trouve par un pont qui n’a pas encore été
traversé. En traduisant cette pensée en image abstraite, cela signifie que les arêtes
adjacentes en un sommet doivent arriver par deux. À part les deux sommets qui
représentent le début et la fin de la promenade, tous les ponts peuvent être traversés
si et seulement si de chaque sommet part un nombre pair d’arêtes.
Le nombre d’arêtes adjacentes en un point s’appelle le « degré » du point.
degré = 5
Le théorème d’Euler stipule que
Les ponts d’une ville peuvent être traversés une fois et une seule si et seulement si tous les
sommets du graphe sont de degré pair sauf éventuellement deux d’entre eux.
En regardant le graphe représentant Königsberg, on constate
que chaque sommet est de degré impair. Cela signifie qu’un
itinéraire qui permet de traverser chaque pont une fois et
une seule est impossible à Königsberg. Si l’on modifiait
la configuration du réseau de ponts, alors peut-être. Si
l’on construisait un autre pont entre les îles I et C, les
degrés de I et C seraient tous deux pairs. Cela signifie
que l’on pourrait partir de A et terminer en B, après
avoir traversé chaque pont une fois et une seule. Si l’on
construisait un autre pont encore, cette fois entre A et B
(voir le schéma de droite), on pourrait partir de n’importe
quel endroit et y revenir parce que, dans ce cas, chaque
sommet serait de degré pair.
Le théorème de la poignée de mains Si on nous demandait de dessiner
un graphe contenant trois sommets de degré impair, nous aurions un problème.
Essayez. On ne peut pas le faire parce que
Le nombre de sommets de degré impair d’un graphe quelconque doit être pair.
C’est le théorème de la poignée de main, premier théorème de la théorie des
graphes. Dans un graphe quel qu’il soit, chaque arête a un début et une fin, ou en
d’autres termes, il faut être au moins deux pour se serrer la main. Soit x (resp. y) le
nombre de sommets de degré impair (resp. pair). Appelons N (resp. Nx ; Ny) la
somme des degrés (resp. degrés impairs ; degrés pairs) des sommets du graphe.
C
B
A
I
1930
Kuratowski prouve
le théorème des graphes
planaires.
1935
George Pólya développe
des techniques algébriques
d’énumération des graphes.
1999
Eric Rains et Neil Sloane
développent l’énumération
des structures arborescentes.
pouvoir quitter la berge sur laquelle on se trouve par un pont qui n’a pas encore été
traversé. En traduisant cette pensée en image abstraite, cela signifie que les arêtes
adjacentes en un sommet doivent arriver par deux. À part les deux sommets qui
représentent le début et la fin de la promenade, tous les ponts peuvent être traversés
si et seulement si de chaque sommet part un nombre pair d’arêtes.
Le nombre d’arêtes adjacentes en un point s’appelle le « degré » du point.
degré = 5
Le théorème d’Euler stipule que
Les ponts d’une ville peuvent être traversés une fois et une seule si et seulement si tous les
sommets du graphe sont de degré pair sauf éventuellement deux d’entre eux.
En regardant le graphe représentant Königsberg, on constate
que chaque sommet est de degré impair. Cela signifie qu’un
itinéraire qui permet de traverser chaque pont une fois et
une seule est impossible à Königsberg. Si l’on modifiait
la configuration du réseau de ponts, alors peut-être. Si
l’on construisait un autre pont entre les îles I et C, les
degrés de I et C seraient tous deux pairs. Cela signifie
que l’on pourrait partir de A et terminer en B, après
avoir traversé chaque pont une fois et une seule. Si l’on
construisait un autre pont encore, cette fois entre A et B
(voir le schéma de droite), on pourrait partir de n’importe
quel endroit et y revenir parce que, dans ce cas, chaque
sommet serait de degré pair.
Le théorème de la poignée de mains Si on nous demandait de dessiner
un graphe contenant trois sommets de degré impair, nous aurions un problème.
Essayez. On ne peut pas le faire parce que
Le nombre de sommets de degré impair d’un graphe quelconque doit être pair.
C’est le théorème de la poignée de main, premier théorème de la théorie des
graphes. Dans un graphe quel qu’il soit, chaque arête a un début et une fin, ou en
d’autres termes, il faut être au moins deux pour se serrer la main. Soit x (resp. y) le
nombre de sommets de degré impair (resp. pair). Appelons N (resp. Nx ; Ny) la
somme des degrés (resp. degrés impairs ; degrés pairs) des sommets du graphe.
C
B
A
I