Graphe 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
- (en) Eric W. Weisstein, « Grid Graph », sur MathWorld
- Uli Wagner, « Graphs & Algorithms: Advanced Topics Treewidth ».
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.