Produit cartésien (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 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).

v · théorie des graphes
Décomposition arborescente · Produit cartésien

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

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

  • 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

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

  • Graphe tesseract — Une représentation du graphe tesseract. Nombre de sommets 16 Nombre d arêtes 32 Distribution des degrés 4 régulier Rayon 4 …   Wikipédia en Français

  • Graphe hexaédrique — Représentation du graphe hexaédrique. Nombre de sommets 8 Nombre d arêtes 12 Distribution des degrés 3 régulier Rayon 3 …   Wikipédia en Français

  • graphe — [ graf ] n. m. • 1926; du gr. graphein « écrire » ♦ Math., log. Ensemble des couples d éléments vérifiant une relation donnée. Diagramme représentant le graphe d une relation. Théorie des graphes. Représentation graphique d une fonction. ● graphe …   Encyclopédie Universelle

  • Graphe d'une relation — Correspondance et relation En algèbre générale (ou abstraite), le concept de correspondance, ou de relation, est une abstraction de notions telles que l’égalité, l’ordre alphabétique, ou la comparaison. De manière informelle, une relation dans un …   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

  • Graphe médian — En théorie des graphes, les médians d un triplet de sommets sont les sommets z se trouvant sur les plus courts chemins entre ces sommets[1]. Autrement dit, si I(u,v) est l ensemble de sommets sur les plus courts chemins entre u et v, alors l… …   Wikipédia en Français

Share the article and excerpts

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