thumb|Un graphe de Halin.
En théorie des graphes, une branche des mathématiques, un graphe de Halin est un graphe planaire construit à partir d'un arbre en reliant toutes ses feuilles dans un cycle qui fait le tour de l'arbre de telle façon que l'arbre reste planaire. On exige de plus que l'arbre comporte au moins quatre sommets et ne comporte pas de sommets de degré 2.
Les graphes de Halin graphs sont nommés d'après le mathématicien allemand Rudolf Halin qui les a étudiés en 1971, mais les graphes de Halin cubiques avaient déjà été étudiés plus d'un siècle auparavant par Thomas Kirkman.
thumb|Le graphe des arêtes d'un prisme triangulaire vu comme un graphe de Halin. L'arbre central est en bleu et le cycle extérieur est en noir.
Les graphes roue (les graphes des arêtes d'une pyramide) sont des graphes de Halin ; leur arbre est un graphe étoile.
Le graphe des arêtes d'un prisme triangulaire est également un graphe de Halin (figure).
Le graphe de Frucht, un des plus petits graphes cubiques sans automorphisme de graphe trivial, est aussi un graphe de Halin.
Tout graphe de Halin est un graphe planaire au nombre minimal d'arêtes qui est 3-connexe. Le permet d'en déduire que c'est un graphe polyédrique.
Tout graphe de Halin a un planaire unique, au choix près de l’espace extérieur, c'est-à-dire un unique plongement dans une 2-sphère.
Tout graphe de Halin est hamiltonien, et chaque arête du graphe appartient à un cycle hamiltonien. De plus, un graphe de Halin reste hamiltonien lorsque l'on supprime n'importe quel sommet.
Tout graphe de Halin est presque pancyclique, dans le sens où il comporte des cycles de toutes les longueurs de à (le nombre de sommets) sauf éventuellement une unique longueur paire. De plus, un graphe de Halin reste presque pancyclique si une seule arête est contractée. Enfin, un graphe de Halin sans sommets intérieurs de degré 3 est pancyclique.
Tout graphe de Halin a une largeur arborescente inférieure ou égale à 3.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.
vignette|Un graphe planaire extérieur maximal, muni d'une 3-coloration. En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes.
En théorie des graphes et en informatique théorique, la largeur arborescente ou largeur d'arbre d'un graphe (treewidth en anglais) est un nombre qui, intuitivement, mesure s'il est proche d'un arbre. Elle peut être définie de plusieurs manières, notamment en utilisant la décomposition arborescente. Souvent, un problème algorithmique facile sur les arbres est en fait facile pour les graphes qui ressemblent à des arbres. Ainsi, ce paramètre est souvent utilisé en algorithmique de graphes, notamment pour les schémas d'approximation polynomiaux et complexité paramétrée.
We study two decomposition problems in combinatorial geometry. The first part of the thesis deals with the decomposition of multiple coverings of the plane. We say that a planar set is cover-decomposable if there is a constant m such that any m-fold coveri ...
EPFL2010
, ,
Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rény ...
Association for Computing Machinery (ACM)2019
Graph theory experienced a remarkable increase of interest among the scientific community during the last decades. The vertex coloring problem (Min Coloring) deserves a particular attention rince it has been able to capture a wide variety of applications. ...