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 G et G' résultant en un graphe G \square G'. 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 G = (V, E) et G' = (V', E'). Le produit cartésien H = G \square G' est défini comme suit :

  • V(H) = \{(ss')|s \in V, s' \in V'\}. Autrement dit, l'ensemble résultant des sommets V(H) est le produit cartésien V(G) \times V(G').
  • E(H) = \{e_{uu'-vv'}|(u=v \wedge d(u',v') = 1) \vee (u' = v' \wedge d(u,v) = 1)\}. 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 D_H du produit cartésien de G et G' est D_H = D_G + D_{G'}.
  • L'opération \square est commutative et associative.
  • Spectre. Le spectre d'un produit cartésien A \square B est \{\alpha_i,\beta_j\}, où \{\alpha_i\} est le spectre de A et \{\beta_j\} le spectre de B; 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 A \square B est sommet-transitif si et seulement si A et B sont sommet-transitifs[2].
  • Connectivité. Le produit cartésien A \square B est connexe si et seulement si A et B 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 H(d,q) est le produit cartésien de d graphes complets K_q. Un cas particulier intéressant est l'hypercube Q_d = H(d,2).
  • La grille M(m,n) est obtenue par le produit cartésien[3] de chemins P_m \square P_n.
  • La grille torique MT(m,n) est obtenue par le produit cartésien[3] de deux graphes cycles C_m \square C_n.
  • Le prisme Y_{m,n} est obtenu par le produit cartésien[4] d'un graphe cycle et d'un chemin C_m \square P_n.

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).