Mathématiques et sciences humaines/Mathematics and social sciences

n° 157, Printemps 2002

Version imprimable   Signaler cette page  

Graphes d'arches

Arch graphs

Bruno Leclerc

Télécharger le texte intégral (536k)

Résumé

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.

Abstract

An arch-graph may be obtained from a simple edge by successive addings of 3-paths, grafted on their extremities. Equivalently, it admits no subgraph of which every vertex has degree at least three, and is maximal with this property, for a fixed number of vertices. It is known that a tree distance may be summarized by 2n-3 of its entries, conveniently chosen. Arch graphs with n vertices correspond to such sets of entries. They include the graphs of the so-called 2-tree type. We study these graphs, and the k-arch graphs and k-trees which naturally generalize them. It is recalled how a tree metric or function is associated to a valued arch graph, and the properties of this correspondence are investigated.

Index

Pour citer cet article

Bruno Leclerc, « Graphes d'arches », Mathématiques et sciences humaines, n° 157, Printemps 2002, [En ligne], mis en ligne le 10 février 2006. URL : http://msh.revues.org/document2858.html. Consulté le 28 novembre 2009.

 
Page générée par Lodel - Nous adhérons à www.revues.org

ISSN : 0987 6936
Ecole des hautes études en sciences sociales