Un graphe est un ensemble de points appelés sommets et de liens entre ces points, appelés arêtes. Tout ensemble muni d'une relation binaire peut être modélisé par un graphe. On peut évoquer par exemple les réseaux (informatique, sociaux, de télécommunications, etc.), les cartes routières, ou encore des diagrammes de compatibilité entre des tâches.
La théorie des graphes s'intéresse aux propriétés des structures ainsi obtenues. En particulier, on cherche par exemple combien de couleurs suffisent à colorer chaque sommet sans que deux voisins partagent une même couleur (coloration de cartes); combien il faut placer de représentants pour que chaque sommet ait au moins un représentant dans son voisinage (domination), etc.
Réduire