Graphes : introduction

Avant de commencer

pff, j’me souviens plus trop bien des opérations de booléens, un petit coup d’œil vers le chapitre logique…

hého c’est quoi ces hiéroglyphes ? un petit rappel pour se souvenir que la notation ensembliste ne se récite pas à la lueur des bougies au dessus d’un chaudron fumant.

Bheu, c’est quoi une matrice ?, un petit détour vers les explications relatives aux matrices s’impose.

Quelques notations et termes

Un graphe est une représentation, une modélisation de nombreux problèmes.

Un graphe est avant tout un ensemble de points, que nous appellerons nœuds ou sommets (cela ne définit pas encore notre graphe, mais c’est un bon point de départ).

Nous pouvons relier certains de ces nœuds entre eux, et d’autres peuvent également se trouver isolés.

Ce qui nous intéresse est la relation qui existe entre les sommets, mais pas leurs positions exactes. Nous pouvons donc représenter de nombreuses manières différentes un même graphe. Deux graphes sont considérés comme isomorphes (identiques) s'ils comportent les mêmes ensembles de paires¹ ou de couples² sur le même ensemble X (ensemble des sommets).

Comme nous relions des nœuds, nous utiliserons des paires ou des couples pour désigner cette relation. Par exemple, le lien entre les sommets 1 et 2 s’écrira (1,2).

Selon que le sens dans lequel nous relions ces nœuds ou sommets soit important ou pas, nous nous trouverons en face de graphes orientés ou non orientés³. Cette classification dichotomique⁴ des graphes nous poussera à nommer de manière différente certains éléments :

Dans le cas d’un arc², nous devons spécifier par une flèche le sens de la relation entre les deux sommets. L’ordre dans lequel les sommets sont représentés au sein du couple est ici important, alors que pour un graphe non orienté la représentation est commutative¹³.

Quelques conventions qui seront utilisées au cours des pages suivantes :

• Notation G(X,A)
  • G = Graphe
  • X = Ensemble des sommets X={x₁, x₂, ... ,x_n}
  • A = Ensemble des arêtes si G est non-orienté (paires), ensemble des arcs si G est orienté (couples)
    A={a₁, a₂, ... , a_n}, ∀ a∈A ⇒ a={x, y}, x∈X ∧ y∈X
• G(X,A) = |{X}| = n : Cardinalité de l’ensemble des sommets. Parfois aussi représenté par #{X} = n.
  Nous devrions dire qu’il s’agit d’un graphe d’ordre n, mais par abus de langage nous disons souvent que le graphe est de taille n, ce qui n’est pas tout à fait correct, car la taille du graphe est m, défini ci-dessous.
• G(X,A) = |{A}| = m : Cardinalité de l’ensemble des arêtes ou des arcs. Il s'agit de la taille du graphe.

Table des matières Haut

Relations entre n et m

Nous pouvons observer qu’il existe une étroite relation entre la cardinalité de l’ensemble des sommets(n) et la cardinalité de l’ensemble des arêtes¹ ou des arcs² (m)

Quand n devient très important, nous pouvons résumer le tableau en deux cas, car ajouter ou supprimer 1 à un très grand nombre est insignifiant :

• Graphe orienté m ≤ n²
• Graphe non-orienté m ≤ n²/2

Nous verrons aussi d'autres relations entre m et n lors des composantes simplement connexes.

Table des matières Haut

Graphe simple et multigraphe

Dans le cas d'un graphe simple non-orienté, nous trouvons au maximum une arête, et maximum deux arcs (un pour chaque sens) pour un graphe simple orienté.

Dans le cas d'un multigraphe (ou p-graphe), nous pouvons avoir plus d'une arête, ou plus de deux arcs entre deux sommets.

Table des matières Haut

Graphe valué

Un graphe valué est un graphe pour lequel nous associons une valeur à chaque arête¹⁶.

Nous pouvons aussi parfois utiliser le terme « graphes pondérés », ce qui signifie exactement la même chose (ce terme dérive de la pondération des arêtes).

La pondération d'une arête² est une valeur associée à cette arête, qui correspond au coût (ou poids) que représente le passage par cette arête.

Précédent et suivant

Pour un arc (x,y)², le sommet x est le précédent de y, et le sommet y est le suivant de x.

Par convention, nous tenterons de limiter l'usage des termes « précédents » et « suivants » aux sommets qui sont reliés par une chaîne de longueur 1¹⁷ avec le sommet courant. Pour l'ensemble des sommets qui précèdent ou suivent dans la hiérarchie, nous emploierons les termes de « prédécesseurs » et « successeurs ».

Chaîne

Une chaîne est une suite finie de sommets reliés entre eux à chaque fois par une arête. Nous pouvons passer plusieurs fois par un même sommet dans une chaîne.

La longueur d'une chaîne est le nombre des arêtes qui la compose.

La valeur d'une chaîne pour un graphe valué est la somme des valeurs des arcs qui la compose.

Une chaîne simple est une chaîne pour laquelle nous n'utilisons qu'une seule fois chaque arête de la chaîne.

Une chaîne eulérienne est une chaîne simple pour laquelle nous utilisons toutes les arêtes du graphe.

Une chaîne hamiltonienne est une chaîne pour laquelle nous utilisons tous les sommets du graphe, en passant une et une seule fois par chaque sommet.

Nous pouvons aussi appliquer les qualificatifs eulérien et hamiltonnien aux cycles, et aux graphes en entier, qui remplissent ces conditions.

Table des matières Haut

Distance

La distance entre deux sommets est la longueur de la plus petite chaîne qui relie ces deux sommets.

Arbre

Un arbre est un graphe connexe, sans cycle, simple, et sans boucle.
Vous pouvez aussi consulter la page d'exemples et d'exercices sur les arbres et les graphes.

Incidence

Une arête¹⁶ (a) est incidente à un sommet (s) si le sommet est une des extrémités de a. La réciprocité est vraie, car ∀a incident à s ⇒ s incident à a.

Nous pouvons avoir des arcs² incidents à un sommet vers l'intérieur, ou des arcs incidents à un sommet vers l'extérieur.

• Soit a=(x,y)
  • a est incident à x vers l'extérieur (a part de x vers l'extérieur)
  • a est incident à y vers l'intérieur (a arrive dans y)

Table des matières Haut

Adjacences

Pour une paire ou un couple (x,y), les sommets x et y sont adjacents.

Des arêtes¹⁶ a(x,y) et b(y,z) sont aussi dits adjacents car ils possèdent en commun le sommet y.

Table des matières Haut

Matrice associée à un graphe

La matrice est un des moyens de représenter un graphe, très pratique en mathématique, mais assez coûteux en informatique (nécessite beaucoup de place en mémoire).

Nous utiliserons une matrice booléenne (remplie uniquement de 0 et de 1) M de dimension n*n telle que M[i,j] =1 si et seulement si (i,j) ∈ A.

Table des matières Haut

Graphe complet

Un graphe complet est un graphe dont la matrice associée vérifie M[i,j]+M[i,j]≥1 si i≠j.

Pour être plus clair, un graphe est complet si chaque sommet est relié à chacun des autres sommets par une arête.

Un graphe complet est donc toujours simplement connexe.

Nous pouvons trouver un chemin hamiltonien dans tout graphe complet¹⁸.

Table des matières Haut

Application multivoque

L'application multivoque du graphe G(X,A) (notée par le signe gamma : Γ) est la relation dans X entre un sommet x et l'ensemble de ses suivants (en orienté) ou de ses adjacents (en non-orienté).
Γ(x) = {y|((x,y)∈ A}

Application réciproque

L'application réciproque du graphe G(X,A) (notée Γ^-1) est la relation dans X entre un sommet x et l'ensemble de ses précédents (en orienté) ou de ses adjacents (en non-orienté).
Γ^-1(x) = {y|((y,x)∈ A}

Nous pouvons constater que Γ=Γ^-1 dans le cas d'un graphe non-orienté.

Degré

Soit G = (X,A) un graphe simple, et x un sommet de G. Le degré de x, noté d(x) (ou d_G(x) pour signaler que c'est le degré de x qui appartient au graphe G), est le nombre d'arêtes¹⁶ incidentes à x.

Lorsque d(x)=0, nous pouvons dire que x est un « sommet isolé » (en anglais, “isolated vertex”), et si d(x)=1 nous pouvons dire que x est un « sommet pendant » (en anglais, “leaf vertex”).

Attention : un arc a(x,x) (une boucle) est noté deux fois, mais compté une seule fois dans le degré.

Dans le cas d'un graphe orienté, nous pouvons classer les degrés d'un sommet en deux catégories :

• « Degré intérieur »²¹ : les arcs qui ont pour destination ce sommet (extrémité initiale). Noté d(x)_int ou d^-(x)²²
  Nous retrouvons parfois le terme degré entrant.
• « Degré extérieur »²³ : les arcs qui ont pour origine ce sommet (extrémité finale). Noté d(x)_ext ou d⁺(x)
  Nous retrouvons parfois le terme degré sortant.

• Un sommet de degré intérieur 0 et de degré extérieur > à 0 est un « sommet source » (en anglais, “source vertex”).
• Un sommet de degré extérieur 0 et de degré intérieur > à 0 est un « sommet puit » (en anglais, “sink vertex”).

Calcul du degré des sommets dans un graphe

Dans l'exemple ci-dessus, nous avons un graphe simple orienté, avec 7 sommets, et 7 arcs. Comme nous avons une représentation graphique, nous pouvons aisément calculer les degrés des différents sommets.

d(1) : (1, 2) + (1, 3) + (3, 1) = a+b+c = 3 où a et b sont des degrés extérieurs(d_ext) et c est un degré intérieur(d_int).

Nous pouvons facilement déduire la formule d(x) = d(x)_ext + d(x)_ext
Cette formule s'applique bien au sommet 2 (d(2) = 0+1 = 1), mais qu'en est-il pour le sommet 3?

d(3)_ext = c + d + e = 3
d(3)_int = b + d = 2

⇒d(3) = 3 + 2 = 5, mais nous ne trouvons que 4 arcs pour le sommet 3.
Comme nous avons une boucle (l'arc d) pour le sommet 3, nous comptons à la fois la boucle en tant que degré intérieur car d a bien pour destination le sommet 3 et en tant que degré extérieur car d a bien pour origine le sommet 3.

Afin d'éviter de compter deux fois une boucle, nous devons modifier notre formule en utilisant une fonction indicatrice I qui nous retourne 1 si nous sommes en présence d'une boucle (origine et destination identique), sinon zéro.

d(x) = d(x)_ext + d(x)_ext - I(x)

Ce qui nous donne :

• d(1) = 2 + 1 - 0 = 3
• d(2) = 0 + 1 - 0 = 1
• d(3) = 3 + 2 - 1 = 4
• d(4) = 1 + 1 - 0 = 2
• d(5) = 0 + 1 - 0 = 1
• d(6) = 1 + 0 - 0 = 1
• d(7) = 0 + 1 - 0 = 1

Table des matières Haut

Lemme des poignées de mains

Soit G = (X,A) un graphe simple, nous avons Ce qui signifie que la somme des degrés des sommets d'un graphe est égale à deux fois le nombre d'arêtes,car chaque arête a(x, y) est comptée deux fois, une fois lors du calcul du degré de x et une fois lors du calcul du degré de y.

Nous pouvons aussi représenter cette formule de la manière suivante : car |A| et m correspondent à la cardinalité de l'ensemble des arêtes, n correspond à la cardinalité de X (l'ensemble des sommets).

Lors des calculs de degrés nous comptions chaque boucle une seule fois dans le degré, mais ici une boucle doit être comptée deux fois (ce qui correspond à la formule initiale) pour le lemme des poignées de mains. Dès lors, le lemme des poignées de mains reste valable pour les multigraphes avec boucles.

Démonstration du lemme des poignées de mains

Table des matières Haut

Graphe régulier

Nous pouvons dire d'un graphe simple qu'il est régulier de degré r si tous les sommets du graphe sont de degré r.

Densité d'un graphe

La densité du graphe est la proportion entre le nombre d’arêtes ou d’arcs (m) et le nombre total de liens possibles (mmax).

Composantes simplement connexes

Nous pouvons définir la connexité simple de la manière suivante : ∀x, ∀y : ∃ chaîne entre x et y.

La notion « simplement connexe » (en anglais, “weakly connected”) peut s'appliquer à l'ensemble du graphe (si pour tout couple de sommet x et y il existe une chaîne entre x et y), ou à une partie du graphe (nous parlons alors de composante simplement connexe). Cette notion de connexité simple est assez évidente lorsque nous avons peu de sommets et que nous représentons graphiquement le graphe, comme dans l'exemple ci dessous. Nous pouvons dès lors constater qu'au sein d'une composante simplement connexe (csc) chaque sommet est accessible au départ de n'importe quel sommet de la composante.

Si m ≥ n-1, toutes les arêtes¹⁶sont reliées. Dans ce cas, nous avons une seule composante simplement connexe.

Si m < n-1, nous nous trouvons en présence de plus d'une composante simplement connexe.

L'exemple ci-contre montre que notre graphe comporte deux composantes simplement connexes.
Les sommets {1, 2, 3, 4, 5} forment une composante simplement connexe, et les sommets {6,7} forment la deuxième.

Cet exemple montre un graphe simple non-orienté. Qu'en est-il pour les graphes orientés ?

Dans notre premier exemple, si nous appliquons cete définition le ne comportait qu'une seule csc composée des sommets {1,3}, et cinq csc composées chacune d'un seul sommet ({2}, {4}, {5}, {6}, et {7}). Or ce n'est pas le cas.
Dans le cas de graphes orientés nous devons considérer les arcs comme des arêtes, et nous pouvons ensuite appliquer la définition de la csc qui dit que chaque sommet de la composante simplement connexe doit être accessible depuis n'importe quel sommet de la même composante.

Si notre graphe comportait un huitième sommet qui n'était relié à aucun autre sommet, ou s'il était relié à lui même par une boucle, il serait considéré comme une composante simplement connexe, car tout sommet isolé respecte la définition de la csc. Nous aurions alors trois composantes simplement connexes.

Un graphe complet est donc toujours simplement connexe, mais tout graphe simplement connexe n'est pas forcément complet, car la connexité relie x et y par des chaînes (peu importe la longueur), mais un graphe complet a la contrainte que x et y soient reliés par seulement des chaînes (ou chemins) de longueur 1.

Table des matières Haut

Composantes fortement connexes

Nous pouvons définir la connexité forte de la manière suivante : ∀x, ∀y : ∃ chemin entre x et y et ∃ chemin entre y et x.

Nous pourrions considérer chaque composante simplement connexe d'un graphe non-orienté comme une composante « fortement connexe » (en anglais, “strongly connected”) de ce graphe, en considérant chaque arête comme deux arcs de sens opposés, mais nous réserverons uniquement la connexité forte aux graphes orientés.

Comme dans le cas de la connexité simple, la connexité forte peut s'appliquer à un graphe en entier (graphe fortement connexe), ou le graphe peut être décomposé en composantes fortement connexes.

Un graphe complet est donc toujours un graphe fortement connexe (car nous pouvons remplacer les arêtes par deux arcs aux directions opposées), mais l'inverse n'est pas toujours vrai (pour être complet, les chemins doivent avoir une longueur 1).

De par sa définition, un graphe fortement connexe contient forcément des circuits.

Pour chercher les composantes fortement connexes d'un graphe, nous pouvons utiliser les algorithmes de Foulkes ou de Malgrange.

Table des matières Haut

Graphes et composantes connexes

Le fait de décomposer un graphe en composantes nous permet d'en simplifier la représentation et le traitement²⁸.

Indice chromatique d'un graphe

L'indice chromatique d'un graphe est le nombre minimal de couleurs que nous devrons utiliser pour colorer les arêtes du graphe de telle sorte que deux arêtes adjacentes n'aient pas la même couleur.

Nombre chromatique d'un graphe

Le nombre chromatique d'un graphe est le nombre minimal de couleurs que nous devrons utiliser pour colorer les sommets du graphe de telle sorte que deux sommets adjacents n'aient pas la même couleur.

You are on the French version of the site, but your system indicates that you prefer to use the English language.
The entire site is not translated yet, but the menus and buttons on the interface are largely translated.

Would you like to reach the page in English?
Click here to continue in English: Consult the English version of this page

U bevindt zich op de Franse versie van de site, maar uw systeem geeft aan dat u liever de Nederlandse taal gebruikt.
De hele site is nog niet vertaald, maar de menu's en knoppen op de interface zijn grotendeels vertaald.

Wilt u de pagina in het Nederlands bereiken?
Klik hier om door te gaan in het Nederlands: Raadpleeg de Nederlandse versie van deze pagina

Sie befinden sich in der französischen Version der Website, Ihr System gibt jedoch an, dass Sie die deutsche Sprache bevorzugen.
Die gesamte Site ist noch nicht übersetzt, aber die Menüs und Schaltflächen auf der Benutzeroberfläche sind weitgehend übersetzt.

Möchten Sie die Seite auf Deutsch erreichen?
Klicken Sie hier, um fortzufahren: Konsultieren Sie die deutsche Version dieser Seite