Maille (théorie des graphes)


Maille (théorie des graphes)

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

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.

Exemples


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Maille (théorie des graphes) de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Cage (théorie des graphes) — En théorie des graphes, une cage est un graphe régulier minimal pour une maille donnée. Plus précisément, une (r,g) cage est un graphe régulier de degrés r et minimal pour la maille g. Quand le terme de g cage est employé, il s agit en fait d une …   Wikipédia en Français

  • Lexique De La Théorie Des Graphes — Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique de la theorie des graphes — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique en théorie des graphes — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique de la théorie des graphes — Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Acyclique (grap …   Wikipédia en Français

  • Morphisme de graphes — Un morphisme de graphe ou homomorphisme de graphe est une application entre deux graphes qui respecte la structure de ces graphes. Autrement dit l image d un graphe G dans un graphe H doit respecter les relations d adjacence présentes dans G.… …   Wikipédia en Français

  • Graphe partiel — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique (graphe) — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Graphe de Moore — En théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal. Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F …   Wikipédia en Français

  • Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.