Présentation

Article

1 - GÉNÉRALITÉS

2 - MODES DE REPRÉSENTATION

  • 2.1 - Listes de succession
  • 2.2 - Matrice d’adjacence
  • 2.3 - Matrice d’incidence

3 - NOMBRES ET ENSEMBLES CARACTÉRISTIQUES DES GRAPHES

4 - CHEMINS ET CIRCUITS

5 - ARBRES ET ARBORESCENCES

6 - RÉSEAUX DE TRANSPORT

7 - GRAPHES BIPARTIS ET COUPLAGES

8 - GRAPHES PLANAIRES

9 - IMPLANTATIONS D’UN GRAPHE DANS UN AUTRE

Article de référence | Réf : AF205 v1

Généralités
Théorie des graphes

Auteur(s) : Robert CABANE

Relu et validé le 20 janv. 2023

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

Auteur(s)

  • Robert CABANE : Professeur de mathématiques spéciales au lycée Michel-Montaigne (Bordeaux) - Ancien élève de l’École normale supérieure

Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.

Lire l’article

INTRODUCTION

Chacun a vu une fois au moins un plan de métro, une carte de lignes ferroviaires ou aériennes, un plan électrique ou un circuit électronique ; ainsi, tout le monde sait plus ou moins intuitivement ce qu’est un graphe. Toutefois, entre la vague notion d’un schéma incluant des « points » et des « trajets » unissant ces points et la théorie mathématique des graphes, il y a une longue élaboration des concepts, et en particulier le choix d’une terminologie.

Un graphe n’est pas a priori autre chose qu’un ensemble fini de « points » (ses « sommets ») reliés par des « traits » ou des « flèches » (ses « arêtes »).

Nous trouvons aussi des graphes dans deux activités de l’ingénieur : les diagrammes fonctionnels et les problèmes d’ordonnancement des tâches.

On comprendra mieux l’apparition des graphes dans ce dernier problème par un exemple (figure 1). Supposons que cinq équipes de football nommées AB, OR, LF, DT, PZ jouent dans un tournoi. A un certain moment, les matchs joués ont été les suivants :

AB-OR 1-0AB-DT 0-0

AB-LF 1-2OR-PZ 0-0

LF-DT 1-1PZ-DT 2-0

On peut modéliser l’ensemble de ces matchs de manière graphique, comme on le voit dans la figure 1. L’information sur les résultats des matchs n’a pas été reportée, on pourrait l’attacher aux traits (« arêtes » : ce sont les matchs) qui unissent les « sommets » (qui sont ici les équipes). Grâce à cette représentation, on perçoit d’emblée un certain nombre de faits, par exemple le nombre d’équipes en retard.

On trouve aussi une situation de théorie des graphes avec le réseau Internet, dans lequel les sommets sont les fichiers (ou leurs adresses) et les arcs sont les liens entre ces documents.

Un dernier exemple, très différent, peut être trouvé avec la modélisation financière des systèmes internationaux de droits de douane et taxes diverses.

La théorie des graphes est un sujet d’étude relativement récent en Mathéma-tiques. Le texte le plus ancien semble être dû à Euler, en 1736 (dans le problème des ponts de Königsberg, il s’agissait de parcourir les sept ponts sur la rivière Pregel une et seule fois chacun), et le suivant à Monge, en 1781 (à propos d’un problème de déplacement de terre de déblai et de remblai). On remarque ensuite les contributions de Kirkman et Hamilton en 1856 au sujet des parcours désormais appelés chemins hamiltoniens. Mais c’est vers la fin du XIXe siècle, avec Cayley, que la théorie des graphes commença à prendre son essor et à fixer sa terminologie.

Du fait de cette jeunesse, le développement théorique, la mise au point des algorithmes, le choix d’une terminologie ne sont pas entièrement achevés. On trouvera, dans cet article, un exposé de quelques méthodes et applications importantes de la théorie des graphes. Le lecteur trouvera tout le nécessaire pour compléter son information en compulsant les ouvrages fondamentaux de Claude Berge, bien que ceux-ci soient très orientés vers la Combinatoire. Les besoins plus spécifiques de l’Algorithmique sont développés dans des ouvrages plus récents qui sont également cités en bibliographie.

Terminons en signalant que la théorie des graphes est parfois «classée » comme sous-discipline de l’Informatique théorique (en anglais « computer science ») en raison de l’importance des algorithmes, parfois comme sous-discipline des Mathématiques en raison de sa proximité avec la Combinatoire. En réalité, la théorie des graphes se trouve « à la croisée des chemins », entre Mathématiques, Recherche opérationnelle, Informatique et Gestion des réseaux de distribution ou de transport, s’appliquant aussi bien en économie, biologie ou en psychologie.

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-af205


Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Présentation

1. Généralités

Dans tout ce qui suit, pour un ensemble X on notera │X │ le nombre de ses éléments.

L’ensemble réduit au seul élément x sera noté {x}.

L’ensemble des parties d’un ensemble X sera noté .

La matrice transposée d’une matrice A = (aij  ) (i indice de ligne, j indice de colonne) sera notée tA = (aji  ).

1.1 Concepts orientés

HAUT DE PAGE

1.1.1 Vocabulaire

Définition 1.

On appelle graphe orienté ou digraphe G = (XA) la donnée d’un ensemble X, dont les éléments sont appelés sommets, et d’une partie A de , dont les éléments sont appelés arcs ou arêtes.

En présence d’un arc a = (x, y) qui peut être noté simplement xy, on dit que x est l’origine et y l’extrémité de a, que a est sortant en x et incident en y, et que y est un successeur de x tandis que x est un prédécesseur de y. On dit aussi que x et y sont adjacents.

On dit que le graphe G est sans boucle si A ne contient pas d’arête de la forme (xx ), c’est-à-dire joignant un sommet à lui-même.

Une arête (arc) se notera .

On peut aussi définir les graphes d’une manière un peu différente.

Définition 2. Soit un graphe G = (X, A). Pour tout sommet ...

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Généralités
Sommaire
Sommaire

BIBLIOGRAPHIE

  • (1) - AHO (A.), HOPCROFT (J.), ULLMAN (J.) -   Structures de données et algorithmes.  -  Addison-Wesley/Interéditions 1987.

  • (2) - AHUJA (R.-K.), MAGNANTI (T.-L.), ORLIN (J.-B.) -   Network Flows : Theory, Algorithms and Applications (Flots dans les réseaux : théorie, algorithmes et applications).  -  Prentice Hall (USA), 1993.

  • (3) - AVONDO-BODINO (G.) -   Economic Applications of the Theory of Graphs (Applications de la théorie des graphes en économie).  -  Gordon and Breach (USA), 1962.

  • (4) - BAASE (S.) -   Computer Algorithms. Introduction to Design and Analysis (second edition) (Algorithmes informatiques, intro-duction à la conception et l’analyse).  -  Addison-Wesley. 1978.

  • (5) - BATTERSBY (A.) -   Méthodes modernes d’ordonnancement,  -  volume 11 de Sigma Dunod, 1967.

  • (6) - BERGE (C.), GHOUILA-HOURI -   Programmes,...

1 Sites Internet

Voici quelques adresses électroniques auxquelles une recherche thématique conduit aisément, et à partir desquelles d’autres liens peuvent être suivis. Il convient de rappeler que ces adresses sont tout à fait susceptibles de changer inopinément et ne doivent pas être considérées comme une source aussi fiable que les livres et articles.

C’est cependant par ce canal qu’on trouvera le plus facilement des algorithmes relatifs aux graphes, généralement codés en langage C.

On pourra consulter, par ordre de généralité décroissante :

Un aperçu de la théorie des graphes, par le Laboratoire Leibniz, Institut de mathématiques appliquées de Grenoble. https://ensimag.grenoble-inp.fr/

Les pages de théorie des graphes de Stephen C. Locke, de l’Université de Floride à Boca Raton. http://www.math.fau.edu/locke/graphthe.htm

Un vocabulaire de Théorie des graphes par Chris Caldwell, de l’Université du Tennessee à Martin. http://www.utm.edu/departments/math/graph/glossary.html

Une collection de liens sur le thème du tracé des graphes (Graph Drawing), extraits de Geometry in Action (David Eppstein, Université de Californie à Irvine). http://www. ics.uci.edu./~eppstein/gina/gdraw.html

Des pages sur les problèmes de coloriages des graphes, écrites par Joseph Culberson de l’Université de l’Alberta (Canada). http://www.cs.ualberta.ca/~joe.Coloring/index.html

Un ensemble de pages sur la recherche opérationnelle (Operational Research), créées par J.-E. Beasley de l’Imperial College...

Cet article est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS