Éd. 1971-1976

graphes (théorie des) (suite)

graphe hamiltonien, graphe qui peut être décrit par un cycle élémentaire, c’est-à-dire contenant chaque point du graphe une fois et une seule (fig. j). [C’est sir William Hamilton (1805-1865) qui proposa, pour vingt-cinq guinées environ, à un fabricant de jouets de Dublin un jeu en forme de dodécaèdre dont chaque sommet avait le nom d’une capitale. Le joueur devait aller dans chaque capitale une fois et une seule. Le graphe de la figure j représente les vingt sommets et les douze faces y compris la face extérieure ; les numéros placés sur les sommets indiquent un périple gagnant.]

graphe n – chromatique, graphe qui peut être colorié avec n couleurs et non avec n – 1 couleurs. (Tout graphe plan peut être colorié avec cinq couleurs ; tout graphe peut être colorié avec deux couleurs si et seulement s’il ne contient aucun cycle de longueur impaire.)

graphe (multigraphe) plan, graphe (multigraphe) qui peut être tracé sur un plan ou sur une sphère, sans que deux de ses lignes se coupent.

graphe régulier, graphe dont tous les sommets ont le même degré.

longueur d’un chemin, nombre des lignes qu’il contient.

multigraphe, ensemble de points et de lignes dans lequel deux points distincts peuvent être joints par plus d’une seule ligne.

ordre d’un graphe, nombre de points dont est formé ce graphe.

point de degré 0, point isolé d’un graphe.

(p, q) graphe, graphe contenant p points et q lignes (fig. h).

Applications

La théorie des graphes a de nombreuses applications. Les graphes orientés aident à représenter les relations dans un ensemble, mais également les chaînes de Markov qui interviennent dans des processus aléatoires décrivant l’évolution de systèmes passant un nombre fini ou infini de fois par n états, chaque passage étant affecté d’une certaine probabilité. Les états seront représentés par des points et les passages par des flèches.

La théorie des graphes a également des applications directes en économie, en organisation industrielle, notamment dans des problèmes d’ordonnancement, de circulation et de transport, de cheminement, dans des jeux de stratégie, dans l’étude de réseaux de communication ou de relation à l’intérieur d’un groupe humain, en chimie organique, en psychologie, en sociologie, dans la théorie des langages, en programmation, en composition musicale, etc. C’est une des théories les plus fécondes.

E. S.

➙ Application / Ensemble / Relation / Treillis.

C. Berge, Théorie des graphes et ses applications (Dunod, 1963) ; Graphes et hypergraphes (Dunod, 1971). / F. Harary, R. Z. Norman et D. Cartwright, Structural Models. An Introduction to the Theory of Directed Graphs (New York, 1965).

graphique statistique

Représentation d’observations statistiques par des grandeurs géométriques ou des figures en vue d’obtenir des données numériques une image permettant d’en saisir rapidement l’ensemble des éléments fondamentaux : caractéristiques d’une distribution, liaison entre deux variables, comparaison des variations, relation entre des observations et leurs origines géographiques, etc.

Un graphique est aussi un moyen de contrôle et d’analyse : il rend particulièrement frappantes toutes variations anormales, impliquant une vérification des données, et constitue souvent la base d’une étude analytique. D’autre part, il doit rester simple et clair : à vouloir contenir trop de renseignements divers, il perd en efficacité visuelle ce qu’il gagne en informations.

Les éléments essentiels que l’œil peut apprécier rapidement sont les longueurs, les différences ou rapports de longueurs, les angles et les surfaces. L’utilisation de couleurs, de hachures différentes peut faciliter les comparaisons, soit en accentuant l’image associée à chaque grandeur représentée, soit en faisant correspondre une échelle de teintes, convenablement choisie, à la hiérarchie des valeurs du phénomène observé.

L’interprétation rapide d’un graphique peut, dans certains cas, être trompeuse : le fait que le jugement immédiat résultant d’un graphique provient de sensations visuelles permet à un dessinateur d’accentuer ou lie réduire l’importance de certains caractères du phénomène représenté ; cette propriété est l’un des arguments utilisés dans les présentations graphiques de statistiques publicitaires.

Méthodes de présentation graphique d’une statistique

Les méthodes utilisées, faisant appel à l’imagination du dessinateur, sont évidemment très variées et ne se prêtent guère à une classification systématique : on peut cependant distinguer les divers types ci-après.

• Graphiques utilisant un système de coordonnées :
— graphiques cartésiens : échelles arithmétiques, échelles logarithmiques ou autres échelles fonctionnelles ;
— graphiques polaires.

• Graphiques utilisant des surfaces : rectangles, secteurs, images.

• Cartes statistiques.

• Représentations planes de stéréogrammes (cas où trois variables sont envisagées simultanément).

Les graphiques à coordonnées cartésiennes rectangulaires jouent un rôle fondamental dans la représentation des distributions de fréquences (relations entre la valeur d’une variable ou une classe de ses valeurs et l’effectif ou la fréquence des observations correspondantes). Dans le cas d’une variable discrète, on utilise généralement le diagramme en bâtons, dans lequel on fait correspondre à chaque valeur de la variable une ordonnée de longueur proportionnelle à l’effectif correspondant ou à la fréquence. À ce graphique, on peut faire correspondre un graphique cumulatif en escalier, chaque ordonnée représentant l’effectif ou la fréquence cumulés des observations inférieures ou égales à une valeur donnée de la variable.