Maille (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Maille.

En théorie des graphes, la maille d'un graphe est la longueur du plus court de ses cycles[1]. Un graphe acyclique est généralement considéré comme ayant une maille infinie (ou, pour certains auteurs, une maille de -1).

Exemples[modifier | modifier le code]

Familles associées[modifier | modifier le code]

  • Un graphe régulier de degrés r et de maille g étant minimal en nombre de sommets pour cette maille donnée est appelé une (r,g)-cage.
  • Les graphes de maille supérieure ou égale à quatre sont les graphes sans triangle.

Notes et références[modifier | modifier le code]

  1. Reinhard Diestel, Graph Theory, Springer, coll. « Graduate Texts in Mathematics » (no 173),‎ 2012, 4e éd., 451 p. (ISBN 978-3-642-14278-9, présentation en ligne), p. 11