Graphes d'arches
Résumés
Un graphe d'arches s'obtient à partir d'une simple arête par ajouts successifs de 3-chaînes, greffées sur leurs extrémités. De façon équivalente, c'est un graphe sans sous-graphe dont tous les sommets sont de degré au moins trois et maximal avec cette propriété à nombre de sommets fixé. Il est connu qu'une distance d'arbre est résumable par 2n-3 de ses entrées, bien choisies. Les graphes d'arches à n sommets correspondent à de tels ensembles d'entrées. Ils contiennent la sous-classe bien étudiée des 2-arbres . Nous étudions ces graphes, et les graphes de k-arches et k-arbres qui les généralisent naturellement. Nous rappelons comment on passe d'un graphe d'arches valué à une fonction ou une distance d'arbre et nous examinons les propriétés de cette correspondance.
Entrées d’index
Haut de pagePour citer cet article
Référence électronique
Bruno Leclerc, « Graphes d'arches », Mathématiques et sciences humaines [En ligne], 157 | Printemps 2002, mis en ligne le 10 février 2006, consulté le 22 mars 2023. URL : http://journals.openedition.org/msh/2858 ; DOI : https://doi.org/10.4000/msh.2858
Haut de page