Théorie des graphes
La théorie des graphes étudie les graphes – des structures composées de sommets reliés par des arêtes – en tant que modèles mathématiques de relations binaires et de réseaux.
Definition
L'étude mathématique des graphes, qui sont des ensembles de sommets associés à un ensemble d'arêtes reliant chacune une paire de sommets, et des propriétés invariantes sous la structure de ces connexions.
Scope
Ce domaine couvre la structure, les propriétés et les paramètres des graphes : connectivité, chemins et cycles, arbres, planarité, colorations, couplages et flots, ainsi que les questions extrémales et probabilistes concernant la manière dont les propriétés des graphes se contraignent mutuellement. Elle est centrale en mathématiques discrètes et fournit le langage des réseaux dans l'informatique, la recherche opérationnelle et les sciences naturelles et sociales.
Sub-topics
Core questions
- Quelles propriétés structurelles découlent de la connectivité, de la suite des degrés ou de la structure cyclique d'un graphe ?
- Quand un graphe peut-il être dessiné dans le plan sans croisements ou coloré avec peu de couleurs ?
- Quelle peut être la taille ou la densité maximale d'un graphe tout en évitant une sous-structure donnée ?
- Comment les chemins, les couplages et les flots permettent-ils d'optimiser un réseau ?
Key concepts
- Sommets, arêtes et degré
- Connectivité et composantes
- Chemins, cycles et arbres
- Planarité
- Coloration de graphes
- Couplages et flots
Clinical relevance
Les graphes modélisent les réseaux de communication et de transport, les réseaux d'interaction sociaux et biologiques, les structures de circuits et de dépendances, ainsi que les problèmes d'ordonnancement, faisant de la théorie des graphes un outil fondamental en informatique et en recherche opérationnelle.
History
La théorie des graphes trouve ses origines dans la solution d'Euler en 1736 au problème des ponts de Königsberg et s'est développée au XXe siècle grâce aux travaux sur la coloration, la connectivité et les méthodes probabilistes et structurelles d'Erdos, Tutte et d'autres.
Key figures
- Leonhard Euler
- William Tutte
- Bela Bollobas
Related topics
Seminal works
- diestel2017
- bollobas1998
Frequently asked questions
- Quelle est la différence entre un graphe et un réseau ?
- Un graphe est l'objet mathématique abstrait composé de sommets et d'arêtes ; un réseau fait généralement référence à un graphe doté de données supplémentaires telles que des poids, des capacités ou des directions modélisant un système réel.
- Pourquoi le problème des ponts de Königsberg était-il important ?
- La preuve d'Euler qu'aucune promenade ne pouvait traverser chacun des sept ponts exactement une fois a abstrait le problème en termes de sommets et d'arêtes, fondant ainsi la théorie des graphes et la topologie.