Graphe de Dyck
- Graphe de Dyck
-
Le graphe de Dyck est, en théorie des graphes, un graphe 3-régulier possédant 32 sommets et 48 arêtes.
Propriétés
Propriétés générales
Le diamètre du graphe de Dyck, l'excentricité maximale de ses sommets, est 5, son rayon, l'excentricité minimale de ses sommets, est 5 et sa maille, la longueur de son plus court cycle, est 6. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.
Coloriage
Le nombre chromatique du graphe de Dyck est 2. C'est-à-dire qu'il est possible de le colorer avec 2 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.
L'indice chromatique du graphe de Dyck est 3. Il existe donc une 3-coloration des arêtes du graphe tels que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.
Propriétés algébriques
Le graphe de Dyck est symétrique, c'est-à-dire que son groupe d'automorphismes agit transitivement sur ses arêtes, ses sommets et ses arcs. Son groupe d'automorphismes est un groupe d'ordre 192.
Le polynôme caractéristique du graphe de Dyck est : (x − 3)(x − 1)9(x + 1)9(x + 3)(x2 − 5)6.
Voir aussi
Liens internes
Liens externes
Références
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de Dyck de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Walther von Dyck — Walther Franz Anton von Dyck[1], né le 6 décembre 1856 à Munich et mort le 5 novembre 1934 à Munich, est un mathématicien allemand. Il est considéré comme le premier[réf. souhaitée] à avoir donné la définition moderne des … Wikipédia en Français
Langage de Dyck — En informatique théorique, et plus spécialement en théorie des langages, les langages de Dyck sont des langages formels particuliers. Un langage de Dyck est l ensemble des mots bien parenthésés, sur un alphabet formé de parenthèses ouvrantes, et… … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
Nombre de Catalan — En mathématiques combinatoires, les nombres de Catalan forment une suite de nombres naturels utilisée dans divers problèmes de dénombrement , impliquant souvent de façon récursive des objets définis. Ils sont nommés ainsi d après le mathématicien … Wikipédia en Français
Nombre De Catalan — Nombres de Catalan Les nombres de Catalan sont des entiers naturels qui se rencontrent souvent dans les problèmes de combinatoire. Ils forment une suite dont le terme d indice n, appelé nème nombre de Catalan est défini par (voir coefficient… … Wikipédia en Français
Nombre de Segner — Nombres de Catalan Les nombres de Catalan sont des entiers naturels qui se rencontrent souvent dans les problèmes de combinatoire. Ils forment une suite dont le terme d indice n, appelé nème nombre de Catalan est défini par (voir coefficient… … Wikipédia en Français
Nombre de catalan — Nombres de Catalan Les nombres de Catalan sont des entiers naturels qui se rencontrent souvent dans les problèmes de combinatoire. Ils forment une suite dont le terme d indice n, appelé nème nombre de Catalan est défini par (voir coefficient… … Wikipédia en Français
Nombres de Catalan — Les nombres de Catalan sont des entiers naturels qui se rencontrent souvent dans les problèmes de combinatoire. Ils forment une suite dont le terme d indice n, appelé nème nombre de Catalan est défini par (voir coefficient binomial). Les premiers … Wikipédia en Français
Nombres de Segner — Nombres de Catalan Les nombres de Catalan sont des entiers naturels qui se rencontrent souvent dans les problèmes de combinatoire. Ils forment une suite dont le terme d indice n, appelé nème nombre de Catalan est défini par (voir coefficient… … Wikipédia en Français
Suites de Catalan — Nombres de Catalan Les nombres de Catalan sont des entiers naturels qui se rencontrent souvent dans les problèmes de combinatoire. Ils forment une suite dont le terme d indice n, appelé nème nombre de Catalan est défini par (voir coefficient… … Wikipédia en Français
