Produit cartésien (graphe)

opération sur deux graphes

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
 
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
  • 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

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 de chemins  [3].
  • 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
  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.

Bibliographie

modifier

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