Médaille
N°1 pour apprendre & réviser du collège au lycée.
Marianne

Conforme au programme
officiel 2018 - 2019

Graphes

Déjà plus de

1 million

d'inscrits !

Graphes non-orientés

  • Un graphe est composé de sommets et d’arêtes reliant certains de ces sommets.

  • L’ordre d’un graphe est le nombre de ses sommets.

  • Une boucle est une arête reliant un sommet à lui-même.

  • Deux sommets reliés par une arête sont dits adjacents.

  • Le degré d’un sommet est le nombre d’arêtes dont ce sommet est une extrémité.

  • Un graphe est complet lorsque tous ses sommets sont adjacents.

  • La somme des degrés des sommets d’un graphe non orienté est égale au double du nombre total d’arêtes.

  • La matrice d’adjacence associée à un graphe non orienté d’ordre nn dont les sommets sont numérotés de 11 à nn est la matrice carrée d’ordre nn, où le terme situé en ligne ii et colonne jj est égal au nombre d’arêtes reliant ii et jj. La matrice d’adjacence d’un graphe non orienté sera toujours symétrique par rapport à sa première diagonale.

  • Une chaîne est une liste ordonnée de sommets reliés deux à deux par une arête.

  • La longueur d’une chaîne est le nombre d’arêtes qui la composent.

  • Une chaîne est fermée lorsque l’origine et l’extrémité sont confondues.

  • Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes.

  • Propriété : trouver dans un graphe un nombre de chaînes de longueur donnée

Soit pp un entier naturel et MM la matrice d’adjacence associée à un graphe non orienté dont les sommets sont numérotés. Le terme aija_{ij}ij (ligne ii colonne jj) de la matrice MpM^p donne le nombre de chaînes de longueur pp reliant ii et jj.

  • Un graphe est connexe s’il existe toujours une chaîne entre deux sommets distincts, c’est-à-dire si le graphe est « d’un seul tenant ».
  • Une chaîne est eulérienne lorsqu’elle contient chaque arête du graphe une et une seule fois. Si cette chaîne est un cycle, on dit qu’il s’agit d’un cycle eulérien.

Le théorème d’Euler permet de savoir rapidement si un graphe connexe comporte une chaîne eulérienne ou un cycle eulérien.

  • Théorème d’Euler :

Un graphe connexe admet une chaîne eulérienne si, et seulement si, le nombre de sommets de degré impair vaut 00 ou 22. Un graphe connexe admet un cycle eulérien si, et seulement si, tous ses sommets sont de degré pair.

Graphes orientés

  • Un graphe orienté est un graphe dont les arêtes sont orientées. Chaque arête ne peut être parcourue que dans le sens de la flèche. Une boucle est une arête orientée dont l’origine et l’extrémité sont les mêmes.
  • La matrice d’adjacence associée à un graphe orienté d’ordre nn, dont les sommets sont numérotés de 11 à nn, est une matrice carrée d’ordre nn où le terme figurant en ligne ii et colonne jj est égal à 11 s’il existe une arête menant de ii à jj, et à 00 sinon. Contrairement à la matrice d’adjacence d’un graphe non orienté, celle d’un graphe orienté n’est pas forcément symétrique par rapport à sa première diagonale.
  • Propriété : trouver dans un graphe un nombre de chaîne d’une longueur donnée
  • Soit pp un entier naturel et MM est la matrice d’adjacence associée à un graphe orienté dont les sommets sont numérotés. Le terme aija_{ij}ij (ligne ii colonne jj) de la matrice MpM^p donne le nombre de chaînes de longueur pp reliant ii et jj.
  • Cette propriété est exactement la même que pour les graphes non orientés.
  • Graphe étiqueté :
  • Un graphe étiqueté est un graphe orienté où chacune des arêtes est affectée d’une lettre ou d’un mot ou de tout autre symbole. Ces symboles sont appelés des étiquettes.

    • Graphe pondéré :

    Un graphe pondéré est un graphe étiqueté dont toutes les étiquettes sont des nombres positifs.

    • Poids d’une chaîne :

    Le poids d’une chaîne est la somme du poids des arêtes qui la composent.

    • Plus courte chaîne :

    Une plus courte chaîne entre deux sommets est, parmi les chaînes qui relient ces deux sommets, une chaîne de poids minimal.

    Algorithme de Dijkstra-Moore

    L’algorithme de Dijkstra-Moore permet de trouver la plus courte chaîne reliant un sommet à un autre dans un graphe.

    • Placer tous les sommets du graphe dans la 1re ligne d’un tableau.
      Sur la 2e ligne du tableau, écrire le coefficient 00 sous le sommet de départ et le coefficient \infty sous les autres sommets.
    • Sur la dernière ligne écrite, repérer le sommet XX de coefficient minimal.
      Commencer une nouvelle ligne et rayer toutes les cases vides sous XX.
    • Pour chaque sommet YY adjacent à XX, calculer la somme PP du coefficient de XX et du poids de l’arête reliant YY à XX. Si PP est strictement inférieur au coefficient de YY, inscrire PXP_XX dans la case correspondante de la colonne YY.
      Sinon, inscrire le coefficient de YY et compléter la ligne par des coefficients de la ligne précédente.
    • S’il reste des sommets non sélectionnés, recommencer à l’étape 22.
      Sinon, passer à l’étape 55.
    • La longueur minimale est le nombre lu sur la dernière ligne du tableau.