Concept
Largeur arborescente
Concepts associés (35)
Graphe série-parallèle
vignette|Opérations de composition en série et en parallèle pour les graphes série-parallèle. En théorie des graphes, les graphes série-parallèle sont des graphes avec deux sommets distingués, la source et le puits, et formés récursivement par deux opérations qui sont la composition en série et la composition parallèle. Ces graphes peuvent servir pour modéliser des circuits électriques en série et en parallèle . Dans ce contexte, le terme graphe signifie multigraphe. Il existe plusieurs façons équivalentes de définir des graphes série-parallèle.
Branch-decomposition
In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.
Pseudo-forêt
vignette|upright=1.2 |Une 1-forêt (une pseudo-forêt maximale), composée de trois 1-arbres En théorie des graphes, une pseudo-forêt est un graphe non orienté, ou même un multigraphe dans lequel chaque composante connexe possède au plus un cycle. De manière équivalente, une pseudo-forêt est un graphe dans lequel deux cycles ne sont pas connectés par une chaîne. Un pseudo-arbre est une pseudo-forêt connexe. Les noms évoquent l'analogie avec les arbres et les forêts plus couramment étudiés : un arbre est un graphe connexe sans cycle ; une forêt est une union disjointe d'arbres.
Arbre de Trémaux
En théorie des graphes, un arbre de Trémaux, pour un graphe non orienté G, est un arbre couvrant de G, enraciné en l'un de ses sommets, avec la propriété que deux sommets qui sont voisins dans G sont reliés l'un à l'autre en tant qu'ascendant et descendant dans l'arbre. Les arbres obtenus par un parcours en profondeur (en anglais depth-first search trees) et les chaînes hamiltoniennes sont des arbres de Trémaux.
Graphe cop-win
En théorie des graphes, un graphe cop-win est un graphe non orienté sur lequel le gendarme (cop) peut toujours gagner (win) une partie de course-poursuite contre le voleur, les joueurs jouant à tour de rôle, et pouvant choisir de se déplacer le long d'une arête du graphe ou de rester sur place, jusqu'à ce que le gendarme arrive sur le sommet du voleur.