Graphe grille

Un article de Wikipédia, l'encyclopédie libre.
Ceci est la version actuelle de cette page, en date du 14 février 2019 à 19:32 et modifiée en dernier par Michel Awkal (discuter | contributions). L'URL présente est un lien permanent vers cette version.
(diff) ← Version précédente | Voir la version actuelle (diff) | Version suivante → (diff)

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

Propriétés[modifier | modifier le code]

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[modifier | modifier le code]