Fondamentaux des graphes et connectivité

Les fondamentaux de la théorie des graphes introduisent les graphes, leurs paramètres de base, ainsi que les notions de connectivité et de parcours qui décrivent la cohésion d'un graphe.

Definition

Un graphe est constitué d'un ensemble de sommets et d'un ensemble d'arêtes reliant des paires de sommets ; la connectivité mesure la capacité du graphe à rester d'un seul tenant lorsque des sommets ou des arêtes sont supprimés.

Scope

Ce sujet couvre les définitions des graphes et des digraphes, le degré et le lemme des poignées de main, les sous-graphes et l'isomorphisme, les parcours, les chemins et les cycles, la connectivité et les composantes, ainsi que les caractérisations classiques des graphes eulériens et hamiltoniens. Il établit le vocabulaire et les résultats structurels fondamentaux utilisés dans toute la théorie des graphes.

Core questions

• Quels sont les paramètres de base – ordre, taille et degré – d'un graphe ?
• Quand un graphe est-il connexe, et quelle est la robustesse de sa connectivité face à la suppression ?
• Quand un graphe admet-il un parcours fermé utilisant chaque arête exactement une fois ?
• Comment les chemins et les cycles encodent-ils l'accessibilité et la structure ?

Key concepts

• Sommets, arêtes et degré
• Parcours, chemins et cycles
• Composantes connexes
• Connectivité par sommets et par arêtes
• Circuits eulériens
• Cycles hamiltoniens

Key theories

Lemme des poignées de main

Dans tout graphe, la somme des degrés de tous les sommets est égale à deux fois le nombre d'arêtes, ce qui implique immédiatement que le nombre de sommets de degré impair est pair.

Théorème d'Euler sur les circuits eulériens

Un graphe connexe possède un parcours fermé traversant chaque arête exactement une fois si et seulement si chaque sommet a un degré pair, ce résultat étant à la base de la solution d'Euler au problème des ponts de Königsberg.

Clinical relevance

L'analyse de la connectivité est essentielle pour la fiabilité des réseaux, le routage et la conception de systèmes de communication et de transport tolérants aux pannes, tandis que les structures eulériennes et hamiltoniennes apparaissent dans les problèmes de routage et d'ordonnancement.

History

L'article d'Euler de 1736 sur Königsberg a introduit le parcours de graphes ; le théorème de Menger de 1927 a établi la dualité fondamentale entre la connectivité et les chemins disjoints qui sous-tend la théorie moderne.

Key figures

• Leonhard Euler
• Karl Menger

Seminal works

• diestel2017

Frequently asked questions

Quelle est la différence entre un cycle eulérien et un cycle hamiltonien ?

Un circuit eulérien utilise chaque arête exactement une fois, tandis qu'un cycle hamiltonien visite chaque sommet exactement une fois ; le premier possède une caractérisation simple par le degré, mais la décision du second est computationnellement difficile.

Que signifie pour un graphe d'être k-connexe ?

Un graphe est k-connexe s'il reste connexe chaque fois que moins de k sommets sont supprimés, quantifiant ainsi sa résilience aux défaillances de sommets.