Produit cartésien de graphes

Produit cartésien de graphes

Produit cartésien (graphe)

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.

Sommaire

Construction

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

  • Diamètre. Le diamètre DH du produit cartésien de G et G' est DH = DG + DG'.
  • L'opération \square est commutative et associative.
  • Spectre. Le spectre d'un produit cartésien A \square B est {αi,βj}, où {αi} est le spectre de A et {β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

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 Kq. Un cas particulier intéressant est l'hypercube Qd = 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 Ym,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

  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

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

Opérations en théorie des graphes
Décomposition arborescente · Produit cartésien
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Produit cart%C3%A9sien (graphe) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Produit cartésien de graphes de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Produit cartesien — Produit cartésien Cet article fait référence au concept mathématique sur les ensembles. Pour les graphes, voir produit cartésien de graphes. En mathématiques, le produit cartésien de deux ensembles X et Y, appelé ensemble produit, est l ensemble… …   Wikipédia en Français

  • Produit cartésien — Cet article fait référence au concept mathématique sur les ensembles. Pour les graphes, voir produit cartésien de graphes. En mathématiques, le produit cartésien de deux ensembles X et Y, appelé ensemble produit, est l ensemble de tous les… …   Wikipédia en Français

  • Produit cartésien (graphe) — Le produit cartésien, ou somme cartésienne, est une opération sur deux graphes G et G 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… …   Wikipédia en Français

  • Ensemble-Produit — Produit cartésien Cet article fait référence au concept mathématique sur les ensembles. Pour les graphes, voir produit cartésien de graphes. En mathématiques, le produit cartésien de deux ensembles X et Y, appelé ensemble produit, est l ensemble… …   Wikipédia en Français

  • Ensemble-produit — Produit cartésien Cet article fait référence au concept mathématique sur les ensembles. Pour les graphes, voir produit cartésien de graphes. En mathématiques, le produit cartésien de deux ensembles X et Y, appelé ensemble produit, est l ensemble… …   Wikipédia en Français

  • Espace produit — Produit cartésien Cet article fait référence au concept mathématique sur les ensembles. Pour les graphes, voir produit cartésien de graphes. En mathématiques, le produit cartésien de deux ensembles X et Y, appelé ensemble produit, est l ensemble… …   Wikipédia en Français

  • Somme cartésienne de graphes — Produit cartésien (graphe) Le produit cartésien, ou somme cartésienne, est une opération sur deux graphes G et G 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… …   Wikipédia en Français

  • Graphe de Hamming — H(4,2) Notation H(d,q) Nombre de sommets qd Nombre d arêtes …   Wikipédia en Français

  • Graphe grille — En théorie des graphes, un graphe grille est un produit cartésien de graphes de deux graphes chemin. Portail de l informatique théorique Catégorie : Famille de graphes …   Wikipédia en Français

  • Somme cartésienne (graphe) — Produit cartésien (graphe) Le produit cartésien, ou somme cartésienne, est une opération sur deux graphes G et G 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… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”