Rappel : ce petit cours, réalisé en HTML5/JS/SVG,
n'est visible que sur des navigateurs internet récents
(Firefox vivement recommandé pour un rendu optimal).

Les graphes

Ce petit cours de maths reprend quelques notions sur les graphes, et utilise notamment la multiplication matricielle que je n'ai pas abordé ici.

À noter que Chromium et Chrome ne supportent toujours pas le standard de notation web MathML, utilisé dans cette page, ce qui est absolument honteux. Une fois encore, Firefox peut se targuer d'un support correct des normes face à ses concurrents...

Exemple 1 : graphe simple (non orienté, non pondéré)

Graphe simple
  • Matrice M associée :
  • M = [ 0 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 ]
  • Le degré de chaque sommet s'obtient en aditionnant les 1 de la ligne (ou de la colonne) de notre matrice M, soit :
    • degré de A=3 (3 arêtes partent de A),
    • degré de B=2 (2 arêtes partent de B),
    • degré de C=1 (1 arête part de C),
    • degré de D=2 (2 arêtes partent de D)
  • Tableau de base associé (non trié) :
  • Sommet A B C D
    Degré du sommet 3 2 1 2
  • Comme toujours, on obtient ici le nombre d'arêtes du graphe en additionnant les degrés de tous les sommets et en divisant ce total par 2, soit 8/2=4 arêtes. La raison est assez évidente : on a compté 2x fois chaque arête - il faut donc diviser le total par 2...
  • Ce graphe est connexe, puisqu'on partir de n'importe quel point pour en joindre un autre via une chaîne quelconque.
  • Ce graphe n'est pas complet, puisque chaque sommet ne communique pas directement avec tous les autres. En revanche, le sous-graphe BCD est quant à lui complet.
  • On remarquera également que ce graphe contient 2 sommets impairs, ce qui signifie qu'il contient une chaîne eulérienne, passant une fois et une seule par toutes les arêtes : C - A -B - D par exemple.
  • Ce graphe ne contient pas de cycle eulérien, car il faudrait que tous les degrés du graphe soient pairs. En conséquence de quoi nous ne pouvons pas partir d'un point, parcourir toutes les arêtes et revenir à notre point de départ...
  • Ces constations d'usage étant faites, calculons la matrice M2 :
  • M 2 = [ 0 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 ] × [ 0 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 ] = [ 3 1 0 1 1 2 1 1 0 1 1 1 1 1 1 2 ]
  • Cette matrice nous renseigne sur tous les chemins du graphe passant par 2 arêtes.
  • Prenons la première ligne de M. Elle signifie que A communique avec B, C et D. Prenons la première colonne de M. Elle signifie que B, C et D communiquent avec A. En conséquence de quoi, si sommes allés de A à B avec la première ligne de M, nous pouvons repasser de B à A avec la première colonne, donc le chemin A - B - A est authorisé. Idem pour les points C et D, d'où les chemins suivants :
    • A - B - A
    • A - C - A
    • A - D - A
  • et le chiffre 3 observé.
  • Multiplions maintenant la première ligne de M avec sa seconde colonne de M. D'après la première ligne de M, nous pouvons aller de A à B, C ou D. D'après la seconde colonne de M, nous pouvons aller de A à B ou de D à A. La première possibilité (aller de A à B) ne nous intéresse pas ici, parce que nous sommes partis de A pour aller sur B, C ou D - il est donc impossible de repartir de A... En revanche, la seconde colonne de M nous dit que nous pouvons retourner de D à A. Donc le chemin A - D - A est ici le seul autorisé, et le chiffre 1, dans la première ligne et seconde colonne de M2, de matérialiser ce fait.
  • On peut ainsi continuer le raisonnement : on s’apercevra que M2 matérialise finalement le nombre total de chemins de longueur 2, permettant d'aller d'un point à un autre ou de boucler sur le même point.
  • Pour la matrice M3, le raisonnement est le même :
  • M 3 = [ 3 1 0 1 1 2 1 1 0 1 1 1 1 1 1 2 ] × [ 0 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 ] = [ 2 4 3 4 4 2 1 3 3 1 0 1 4 3 1 2 ]
  • Première ligne de M3 avec première colonne de M, on obtient 2 chemins de 3 arêtes :
    • A - B - D - A
    • A - D - B - A
  • Première ligne de M3 avec seconde colonne de M, on obtient 4 chemins de 3 arêtes :
    • A - B - A - B
    • A - C - A - B
    • A - D - A - B
    • A - B - D - B
  • Première ligne de M3 avec troisième colonne de M, on obtient 3 chemins de 3 arêtes :
    • A - B - A - C
    • A - D - A - C
    • A - C - A - C
  • Première ligne de M3 avec quatrième colonne de M, on obtient 4 chemins de 3 arêtes :
    • A - B - A - D
    • A - C - A - D
    • A - D - A - D
    • A - D - B - D

Conclusion

  • Dans ce petit exemple rapide, on s'aperçoit qu'un simple graphe peut déjà donner bon nombre d'informations, à condition évidemment de connaître les quelques notions de cours associées.
  • Le calcul matriciel a beaucoup d'autres usages, en mathématiques comme en physiques. On remarquera ici le fait d'avoir une diagonale non nulle pour M2, qui signifie que l'on reboucle sur des points déjà visités...
  • Un grand merci enfin à VisualMathEditor pour le rendu des matrices, et à MathFonts pour permettre la correction du bug de rendu des matrices en MathML sous Firefox (lignes trop hautes avec la fonte par défaut).