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.
Introduction 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.
Définitions et structure 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 cycleDéfinition donnée par exemple par .. 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 sommetsDéfinition donnée par .. 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.
Si l'on enlève à un 1-arbre l'une des arêtes de son cycle, le résultat est un arbre. Réciproquement, si l'on augmente un arbre en connectant deux de ses sommets par une nouvelle arête, le résultat est un 1-arbre ; la chaîne dans l'arbre reliant les deux extrémités de l'arête ajoutée, ainsi que l'arête ajoutée elle-même, forment le cycle unique du 1-arbre. Si ajoute à un 1-arbre une arête qui relie l'un de ses sommets à un sommet nouveau, le résultat est à nouveau un 1-arbre, avec un sommet de plus ; une méthode pour construire les 1-arbres consiste donc à commencer par un seul cycle, puis à répéter l'opération d'augmentation un nombre arbitraire de fois. Les arêtes de n'importe quel 1-arbre peuvent être divisées de manière unique en deux sous-graphes, dont l'un est un cycle et l'autre est une forêt, de sorte que chaque arbre de la forêt contient exactement un sommet du cycleExemple de démonstration dans , Lemme 4..
Certaines familles plus particulières de pseudo-forêts ont également été étudiés :
Une 1-forêt, parfois appelée pseudo-forêt maximale, est une pseudo-forêt à laquelle on ne peut ajouter une arête sans qu'une composante du graphe contienne plusieurs cycles. Si une pseudo-forêt contient un arbre comme l'une de ses composantes, ce n'est pas une 1-forêt, car on peut ajouter soit une arête reliant deux sommets à l'intérieur de cet arbre, formant un seul cycle, soit une arête reliant cet arbre à une autre composante. Ainsi, les 1-forêts sont exactement les pseudo-forêts dans lesquelles chaque composante est un 1-arbre. Les pseudo-forêts couvrantes d'un graphe non orienté G sont les sous-graphes de G qui contiennent tous les sommets de G et qui sont des pseudo-forêts. Une telle pseudo-forêt n'a pas besoin d'avoir d'arêtes, puisque par exemple le sous-graphe qui contient tous les sommets de G et aucune arête est une pseudo-forêt (dont les composants sont des arbres constitués d'un seul sommet). Les pseudo-forêts maximales de G sont les sous-graphes de G qui sont des pseudo-forêts qui ne sont contenus dans aucune pseudo-forêt plus grande de G . Une pseudo-forêt maximale de G est toujours une pseudo-forêt couvrante, mais la réciproque est fausse. Si G n'a pas de composante connexe qui est un arbres, alors ses pseudo-forêts maximales sont des 1-forêts, mais si G a un composante qui est un arbre, ses pseudo-forêts maximales ne sont pas des 1-forêts. Plus précisément, dans tout graphe G, ses pseudo-forêts maximales sont constituées de chaque composante de G qui est un arbre, et de 1-arbres disjoints couvrant les sommets restants de G .
Des versions orientées de ces définitions sont également utilisées pour les graphes orientés. Une pseudo-forêt orientée est un graphe orienté dans lequel chaque sommet a au plus un arc sortant ; c'est-à-dire qu'il a un degré sortant 0 ou 1. Une 1-forêt dirigée — plus souvent appelée un graphe fonctionnel ou des fois pseudo-forêt orientée maximale — est un graphe orienté dans lequel le degré sortant est exactement égal à un appellent graphes unicircular les graphes transposés, où chaque sommet a degré entrant égal à 1.. Si D est une pseudo-forêt orientée, le graphe non orienté formé en supprimant la direction de chaque arête de D est une pseudo-forêt non orientée.
Dénombrement Nombre d'arêtes Toute pseudo-forêt à n sommets a au plus n arêtes, et toute pseudo-forêt maximale sur n sommets a exactement n arêtes. Réciproquement, si pour chaque sous-ensemble S de sommets d'un graphe G, le nombre d'arêtes dans le sous-graphe induit par S est au plus égal au nombre de sommets dans S, alors G est une pseudo-forêt. Les 1-arbres peuvent être définis comme des graphes connexes avec autant de sommets et d'arêtes.
Si une famille de graphes a la propriété que chaque sous-graphe d'un graphe de la famille est également dans la famille, et que chaque graphe de la famille a au plus autant d'arêtes que de sommets, alors la famille contient seulement des pseudo-forêts. Par exemple, chaque sous-graphe d'une Le terme « thrackle » est traduit par « manoque » dans la traduction, par Frederic Havet, du livre de Bondy et Murty Théorie des Graphes. (un graphe qui peut être tracé de sorte que chaque paire d'arêtes a un point d'intersection) est également une manoque ; la conjecture des manoques de Conway selon laquelle chaque manoque a au plus autant d'arêtes que de sommets peut être reformulée en disant que chaque manoque est une pseudo-forêt. Une caractérisation plus précise est que, si la conjecture est vraie, alors les manoques sont exactement les pseudo-forêts sans cycle à quatre sommets et au plus un cycle impair ; ..
Streinu et Theran. généralisent les conditions de parcimonie définissant les pseudo-forêts : ils définissent un graphe comme étant -creux si chaque sous-graphe non vide à n sommets a au plus arêtes, et )-serré s'il est -creux et a exactement arêtes. Ainsi, les pseudo-forêts sont les graphes (1,0)-creux, et les pseudo-forêts maximales sont les graphes (1,0)-serrés. Plusieurs autres familles importantes de graphes peuvent être définies à partir d'autres valeurs de k et l, et lorsque les -graphes creux peuvent être caractérisés comme les graphes qui sont l'union disjointe de forêts et de pseudo-forêts.
Presque tous les graphes aléatoires suffisamment creux sont des pseudo-forêts, Corollary 24, p.120, et Corollary 19, p.113.. Plus précisément, si c est une constante avec , et si est la probabilité pour que le choix aléatoire uniforme, parmi les graphes à n sommets de cn arêtes donne une pseudo-forêt, alors tend vers 1 pour n grand. Cependant, pour , presque tous les graphes aléatoires avec cn arêtes contiennent une grande composante qui n'est pas unicyclique.
Énumération Un graphe est simple s'il est sans boucles et sans arêtes multiples. Le nombre de 1-arbres simples à n sommets étiquetés est
Les valeurs pour n jusqu'à 300 figurent dans la séquence de l'Encyclopédie en ligne des suites de nombres entiers .
Le nombre de pseudo-forêts maximales orientées sur n sommets avec boucles, est n n, car pour chaque sommet il y a n extrémités possibles pour l'arête sortante. André Joyal a utilisé ce fait pour fournir une preuve bijective de la formule de Cayley selon laquelle le nombre d'arbres non orientés sur n nœuds est : il donne une bijection entre les pseudo-forêts maximales orientées et les arbres non orientés avec deux nœuds distingués.. Le nombre de pseudo-forêts maximales orientées sans boucles est .
Graphes fonctionnels vignette| upright=1.2| Une fonction de l'ensemble {0,1,2,3,4,5,6,7,8} dans lui-même, et son graphe fonctionnel. Les pseudo-forêts orientées et les endo-fonctions sont en un sens équivalentes. Toute fonction ƒ d'un ensemble X dans lui-même (c'est-à-dire un endomorphisme de X ) peut être vue comme définissant une pseudo-forêt orientée qui a une arête de x à y si et seulement si ƒ( x ) = y . La pseudo-forêt orientée résultante est maximale et contient une boucle pour chaque x tel que ƒ( x ) = x . Réciproquement, toute pseudo-forêt orientée maximale détermine une fonction ƒ telle que ƒ( x ) est l'extrémité terminale de l'arc sortant de x, et toute pseudo-forêt orientée non maximale peut être rendue maximale en ajoutant des boucles puis convertie dans une fonction de la même manière. Pour cette raison, les pseudo-forêts maximales orientées sont parfois appelées graphes fonctionnels. Le tracé d'une fonction sous la forme d'un graphe fonctionnel fournit un cadre pratique pour décrire des propriétés qui ne sont pas aussi faciles à décrire du point de vue de la théorie des fonctions ; cette technique est particulièrement adaptée aux problèmes impliquant des fonctions itérées, qui correspondent à des cheminements dans les graphes fonctionnels.
La détection de cycle est le problème algorithmique qui consiste à suivre un chemin dans un graphe fonctionnel pour y trouver un cycle ; ce problème a des applications en cryptographie et en théorie algorithmique des nombres, dans le cadre de algorithme rho de Pollard pour la factorisation d'entiers et en tant que méthode pour détecter des collisions dans les fonctions de hachage cryptographiques . Dans ces applications, on s'attend à ce que ƒ se comporte de manière aléatoire ; Flajolet et Odlyzko. étudient les propriétés théoriques des graphes fonctionnels issus de fonctions tirées au hasard. En particulier, une forme du paradoxe des anniversaires implique que, dans un graphe fonctionnel aléatoire à n sommets, le chemin partant d'un sommet sélectionné au hasard revient en général sur lui-même pour former un cycle en O( ) pas. Koniaguine et al. ont fait des progrès analytiques et informatiques sur les statistiques des graphes..
Martin, Odlyzko et Wolfram. étudient les pseudo-forêts qui modélisent la dynamique des automates cellulaires. Ces graphes fonctionnels, qu'ils appellent diagrammes de transition d'états, ont un sommet pour chaque configuration de l'ensemble des cellules de l'automate, et une arête reliant une configuration à la configuration suivante si elle est obtenue par l'application des règles de l'automate. On peut déduire certaines propriétés de l'automate à partir de la structure de ces diagrammes, telles que le nombre de composantes, la longueur des cycles limites, la profondeur des arbres reliant des états non limites à ces cycles, ou les symétries du diagramme. Par exemple, tout sommet sans arête entrante correspond à un jardin d'Éden et un sommet avec une boucle automatique correspond à une structure stable.