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. Gabow et Tarjan attribuent l'étude des pseudo-forêts au livre de 1963 de Dantzig sur la programmation linéaire, livre dans lequel les pseudo-forêts apparaissent dans la solution de certains problèmes de réseaux de flot. Les pseudo-forêts forment également des modèles graphiques de fonctions et apparaissent dans plusieurs problèmes algorithmiques. Les pseudo-forêts sont des graphes creux – le nombre de leurs arêtes est borné linéairement par le nombre de sommets (en fait, ils ont au plus d'arêtes qu'ils ont de sommets) – et leur structure matroïde permet de décomposer plusieurs autres familles de graphes creux en des unions de forêts et de pseudo-forêts. Le nom « pseudo-forêt » vient d'un article de Picard et Queyranne en 1982. vignette|upright=1.2| Les 21 graphes unicycliques avec au plus six sommets On considère ici des graphes ou multigraphes non orientés avec boucles. Une pseudo-forêt est un graphe non orienté dans lequel chaque composante connexe contient au plus un cycle. De manière équivalente, il s'agit d'un graphe non orienté dans lequel chaque composante connexe n'a pas plus d'arêtes que de sommets. Les composantes sans cycle sont des arbres ; les composantes qui ont un cycle sont appelés 1-arbres ou graphes unicycliques . Autrement dit, un 1-arbre est un graphe connexe contenant exactement un cycle. Une pseudo-forêt avec une seule composante connexe est appelée un pseudo-arbre ; c'est soit un arbre ou un 1-arbre; en général, une pseudo-forêt peut avoir plusieurs composants connexes qui sont toutes des arbres ou 1-arbres.