3
ÉlÉ ments de
la thÉo rie des
graphes
3.1 ÉlÉ ments de la thÉo rie des graphes
3.1.1 Qu’est- ce qu’un graphe ?
Un des plus anciens pro blèmes combi na toires, est la déter mi na tion d’un iti né raire
à tra vers la ville de Königsberg (aujourd’hui Kaliningrad) en n’uti li sant qu’une
fois et une seule cha cun des sept ponts qui enjam baient les bras de la rivière ou
condui saient à deux îles, dont Euler mon tra en 1735 l’impos si bi lité en uti li sant un
argu ment simple, de parité, semble consti tuer le pre mier témoi gnage de l’emploi
des graphes :
B
A
C
D
Figure 3.1
La preuve de l’impossiblité est donnée dans l’exercice 3.2.
Plus tard, J. Petersen, avec ses graphes régu liers (1891), André Sainte- Laguë,
ancien pro fes seur du CNAM, avec la pre mière thèse sur les réseaux (ou graphes),
en 1926, et sur tout Dénes König, publiant sa Theo rie der endlichen und unendlichen Graphen (1936), déve lop pèrent ce concept. C’est en 1958 que Claude Berge
fit paraître sa Théo rie des graphes et appli ca tions, consi dé ra ble ment ampli fiée dans
ÉlÉ ments de
la thÉo rie des
graphes
3.1 ÉlÉ ments de la thÉo rie des graphes
3.1.1 Qu’est- ce qu’un graphe ?
Un des plus anciens pro blèmes combi na toires, est la déter mi na tion d’un iti né raire
à tra vers la ville de Königsberg (aujourd’hui Kaliningrad) en n’uti li sant qu’une
fois et une seule cha cun des sept ponts qui enjam baient les bras de la rivière ou
condui saient à deux îles, dont Euler mon tra en 1735 l’impos si bi lité en uti li sant un
argu ment simple, de parité, semble consti tuer le pre mier témoi gnage de l’emploi
des graphes :
B
A
C
D
Figure 3.1
La preuve de l’impossiblité est donnée dans l’exercice 3.2.
Plus tard, J. Petersen, avec ses graphes régu liers (1891), André Sainte- Laguë,
ancien pro fes seur du CNAM, avec la pre mière thèse sur les réseaux (ou graphes),
en 1926, et sur tout Dénes König, publiant sa Theo rie der endlichen und unendlichen Graphen (1936), déve lop pèrent ce concept. C’est en 1958 que Claude Berge
fit paraître sa Théo rie des graphes et appli ca tions, consi dé ra ble ment ampli fiée dans