Accueil Dernière Parution Auteurs Thèmes Mots-clefs Parutions Videos Recherche guidée Comité de lecture Contact Abonnement Soumission d'article   Version anglaise Collection numérisée également sur NUMDAM pour les n°1 à n°148 et sur Revues.org pour les n° 149 et suivants

Recherche selon le critère: Mot-clef: Codage d'arbre Affiner ou élargir la recherche 1 entrée référencée Titre Graphes d'arches Auteur LECLERC Bruno Mots-clefs 2-arbre, Algorithme, Arbre, Codage d'arbre, Cycle, Distance, Graphe Thèmes Algorithmes - Algorithmique, Arbres, Distances, Graphes 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. Numéro 157, Printemps 2002 Langue   Français Lire l'article Droits des utilisateurs : Cette création est mise à disposition sous un contrat Creative Commons