Graphe grille

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.

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.