Graphe grille

Page d’aide sur l’homonymie

Pour les articles homonymes, voir grille.

En théorie des graphes, un graphe grille (grid graph) est un type de graphe ressemblant à une grille.

Propriétés

Un graphe grille est le produit cartésien de deux chemins[1].

Les grilles sont des graphes médians, en effet les chemins sont médians, et la propriété est conservée par produit cartésien.

Une grille carrée de taille n a une largeur d'arbre égale à n[2].

Notes et références

  1. (en) Eric W. Weisstein, « Grid Graph », sur MathWorld
  2. Uli Wagner, « Graphs & Algorithms: Advanced Topics Treewidth ».
  • icône décorative Portail des mathématiques
  • icône décorative Portail de l'informatique théorique