Produit cartésien (graphe)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le produit cartésien, ou somme cartésienne, est une opération sur deux graphes et résultant en un graphe . Parler de produit ou de somme pour cette opération n'est pas une contradiction, mais une explication basée sur deux aspects différents : la construction peut se voir comme un produit, tandis que de nombreuses propriétés sont basées sur la somme.

Construction[modifier | modifier le code]

Produit cartésien de deux graphes.

Soient deux graphes et . Le produit cartésien est défini comme suit :

  • . Autrement dit, l'ensemble résultant des sommets est le produit cartésien .
  • . Autrement dit, deux sommets sont voisins si les sommets dont ils sont issus étaient voisins dans l'un des deux graphes.

Propriétés[modifier | modifier le code]

  • Diamètre. Le diamètre du produit cartésien de et est .
  • L'opération est commutative et associative.
  • Spectre. Le spectre d'un produit cartésien est , où est le spectre de et le spectre de ; autrement dit, le spectre est la somme de toutes les paires possibles[1]. Un exemple pratique est donné pour déduire le spectre de l'hypercube à partir des graphes dont il est le produit cartésien.
  • Sommet-transitivité. Le produit cartésien est sommet-transitif si et seulement si et sont sommet-transitifs[2].
  • Connectivité. Le produit cartésien est connexe si et seulement si et sont connexes[2].

Utilisation[modifier | modifier le code]

De nombreux graphes sont définis comme produits cartésiens, et on peut donc utiliser les propriétés de l'opération avec celles des graphes de base pour en déduire les propriétés du graphe obtenu :

  • Le graphe de Hamming est le produit cartésien de graphes complets . Un cas particulier intéressant est l'hypercube .
  • La grille est obtenue par le produit cartésien[3] de chemins .
  • La grille torique est obtenue par le produit cartésien[3] de deux graphes cycles .
  • Le prisme est obtenu par le produit cartésien[4] d'un graphe cycle et d'un chemin .

Références[modifier | modifier le code]

  1. (en) Dragos M. Cvetkovic et Michael Doob et Horst Sachs - Spectra of Graphs, Heidelberg, Leipzig, 1994, (ISBN 3335004078).
  2. a et b Wilfried Imrich et Sandi Klavžar - Product Graphs: Structure and Recognition, Wiley, 2000, (ISBN 0-471-37039-8).
  3. a et b (fr) J-C. Bermond, P. Fraigniaud, A. Germa, M-C. Heydemann, E. Lazard, P. Michallon, A. Raspaud, D. Sotteau, M. Syska et D. Trystram - Communications dans les réseaux de processeurs, Masson, 1994, (ISBN 2225844100). Paru sous le pseudonyme Jean de Rumeur.
  4. (en) Eric W. Weisstein - Graph Cartesian Product, MathWorld--A Wolfram Web Resource, accédé le 17 février 2009.

Lectures complémentaires[modifier | modifier le code]

(en) Wilfried Imrich, Sandi Klavžar et Douglas F. Rall - Topics in graph theory : graphs and their cartesian product, Wellesley, Mass. : A K Peters, 2008, (ISBN 9781568814292).