GRAPHES THÉORIE DES
Problèmes d'Euler et de Hamilton
« Des problèmes où l'on se fait tout petit pour se promener le long des arêtes d'un graphe. »
Le problème d'Euler
Ponts de Kœnigsberg
Encyclopædia Universalis France
Ponts de Kœnigsberg
Le graphe associé au problème des ponts de Kœnigsberg.
Encyclopædia Universalis France
Ce problème classique de cheminement le long des ponts de Königsberg, ville de l'ancienne Prusse-Orientale, souleva l'intérêt du célèbre mathématicien suisse Leonhard Euler. On parlait alors beaucoup du problème des ponts. Le plan de la ville (aujourd'hui Kaliningrad, en Russie) peut être schématisé comme sur la figure et le problème posé par les oisifs prussiens était le suivant : peut-on se promener dans Königsberg en passant une fois et une seule par chaque pont et en revenant au point de départ ?
Ce problème devient un problème de graphes dans la représentation de la figure. Il faut alors trouver un cheminement qui passe par toutes les arêtes du graphe une fois et une seule et qui revienne à son point de départ. Un tel cheminement est appelé de nos jours un cycle eulérien, notion qui se formalise aisément.
Euler démontra simplement que ce problème était insoluble et, plus généralement, que pour qu'il existe dans un graphe G un cycle eulérien, il faut et il suffit que le nombre des arêtes de G en chacun de ses sommets soit pair.
Le problème de WILLIAM ROWAN (1805-1865)"Hamilton
Tournoi
Encyclopædia Universalis France
Tournoi
Exemple de tournoi.
Encyclopædia Universalis France
Théorème de L. Redei. Dans un tournoi, il existe un chemin hamiltonien. Imaginons qu'un arc d'origine x et d'extrémité y signifie qu' « au cours d'un tournoi x l'a emporté sur y ». On voit qu'à l'issue du tournoi, on pourra toujours ranger les joueurs selon un ordre total. Alors que le théorème de Redei peut se démontrer avec des moyens très simples et un fort support intuitif, il faut une formalisation raffinée pour démontrer le résultat suivant.
Théorème de A. Gouihla-Houri. Si G est un graphe orienté sans boucles à n sommets tel que pour tout sommet x de G le nombre des arcs ayant x pour origine ou pour extrémité est strictement supérieur à n, alors G contient un circuit hamiltonien.
La suite de cet article est accessible aux abonnés
- Des contenus variés, complets et fiables
- Accessible sur tous les écrans
- Pas de publicité
Déjà abonné ? Se connecter
Écrit par
- Hervé RAYNAUD : professeur émérite de l'université Joseph Fourier
Classification
Pour citer cet article
Hervé RAYNAUD, « GRAPHES THÉORIE DES », Encyclopædia Universalis [en ligne], consulté le . URL :
Médias
Graphes orientés
Encyclopædia Universalis France
Graphes orientés
Exemples de graphes orientés
Encyclopædia Universalis France
Graphes non orientés
Encyclopædia Universalis France
Graphes non orientés
Exemples de graphes non orientés
Encyclopædia Universalis France
Problème des trois maisons
Encyclopædia Universalis France
Problème des trois maisons
Le problème des trois maisons
Encyclopædia Universalis France
Autres références
-
ALGORITHMIQUE
- Écrit par Philippe COLLARD, Philippe FLAJOLET
- 6 652 mots
- 3 médias
...B : soit m la cardinalité de V ; il s'agit de déterminer s'il existe une permutation vσ(1), vσ(2), ..., vσ(m) de V telle que :– Le problème du coloriage de graphes. Étant donné un graphe G et un entier m, déterminer si G est m-coloriable, c'est-à-dire s'il existe une fonction...
-
BERGE CLAUDE (1926-2002)
- Écrit par Universalis
- 207 mots
Mathématicien français. Fondateur de la théorie des graphes, écrivain cofondateur de l'Oulipo (« Ouvroir de littérature potentielle », en 1960), Claude Berge laisse aussi une œuvre de sculpteur et une collection d'objets d'art des Asmat de Nouvelle-Guinée. Docteur ès sciences mathématiques,...
-
COMBINATOIRE ANALYSE
- Écrit par Dominique FOATA
- 5 426 mots
- 2 médias
...élémentaires s'appliquent plus difficilement lorsqu'on veut dénombrer d'autres structures finies plus élaborées comme celles des arbres ou certains types de graphes. Le plus souvent on est conduit à chercher une correspondance biunivoque entre ces structures et les ensembles finis considérés dans la première... -
CONVEXITÉ - Ensembles convexes
- Écrit par Victor KLEE
- 4 666 mots
- 7 médias
L'étude des propriétés des intersections d'ensembles convexes est facilitée par la notion de graphe d'intersection, qui est utilisée dans des domaines aussi variés que la génétique moléculaire, la psychologie et l'écologie. Pour toute famille d'ensembles, on appelle graphe d'intersection... - Afficher les 9 références
Voir aussi
