Graphe grille
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
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
Portail des mathématiques
Portail de l'informatique théorique