Glossaire

Sélectionnez l'un des mots clés à gauche…

Graphes et réseauxIntroduction

Temps de lecture: ~10 min

Chaque jour, nous sommes entourés d'innombrables connexions et réseaux: routes et voies ferrées, lignes téléphoniques, Internet, circuits électroniques et même liaisons moléculaires. Il existe également des réseaux sociaux entre amis et familles. Tous ces systèmes consistent en certains points dénommés , dont certains sont reliés par . En mathématiques, on appelle cela un graphe.

La théorie des graphes est l'étude des graphes et de leurs propriétés. C’est l’un des domaines les plus passionnants et les plus visuels des mathématiques, et il a de nombreuses applications importantes:

Réseaux routiers et ferroviaires

Circuits intégrés

Des chaînes d'approvisionnement

Amitiés

Connexions neuronales

L'Internet

Nous pouvons esquisser la disposition de graphes simples en utilisant des cercles et des lignes. La position des cercles et la longueur des lignes sont sans importance - nous nous soucions uniquement de la manière dont elles sont connectées. Les lignes peuvent même se croiser et ne doivent pas nécessairement être droites.

Dans certains graphiques, les arêtes ne vont que dans un sens. Ces graphes sont appelés graphes orientés.

Certains graphes sont constitués de plusieurs parties distinctes qui ne sont pas reliées par des arêtes. Ces graphes sont non connexes.

D'autres graphiques peuvent contenir plusieurs arêtes entre les mêmes paires de sommets ou des sommets reliés entre eux (boucles).

Pour des raisons de simplicité, nous ne penserons qu'aux graphes non orientés et connectés sans arêtes et boucles multiples dans ce cours.

Nous pouvons créer de nouveaux graphiques à partir d'un graphique existant en supprimant certains des sommets et des arêtes. Le résultat s'appelle un sous-graphique. Voici quelques exemples de graphiques et de sous-graphiques:

L'ordre d'un graphe est son nombre de sommets. Le degré d'un sommet dans un graphe est le nombre d'arêtes qui se rejoignent à ce sommet.

Ordre:

Ordre:

Degré:

Degré:

Les graphes constitués d'une seule chaîne de sommets sont appelés cycles. Tous les cycles ont .

Archie