English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGraphes et réseauxIntroduction
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
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
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
Ordre:
Ordre:
Degré:
Degré:
Les graphes constitués d'une seule chaîne de sommets sont appelés