# Graphe cactus

En théorie des graphes, un graphe cactus (parfois appelé arbre cactus) est un graphe connexe dans lequel deux cycles simples quelconques ont au plus un sommet en commun. De manière équivalente, c'est un graphe connexe dans lequel chaque arête appartient à au plus un cycle simple, ou (pour les cactus non triviaux) dans lequel chaque bloc (sous-graphe maximal sans point d'articulation) est une arête ou un cycle.

## Terminologie

Les graphes cactus ont d'abord été étudiés sous le nom d'arbres de Husimi, nom qui leur a été attribué par Frank Harary et George Eugene Uhlenbeck en l'honneur des travaux antérieurs sur ces graphes de Kôdi Husimi$^,$. Dans l'article de Harary et Uhlenbeck, le nom de « cactus » est réservé aux seuls graphes dans lesquels chaque cycle est un triangle ; depuis, cette restriction a été levée.
Entretemps, le nom d'arbre de Husimi en est venu à désigner des graphes dans lesquels chaque bloc est un graphe complet (de manière équivalente, les graphes d'intersection des blocs dans un autre graphe). Cet usage avait peu à voir avec les travaux de Husimi, et le terme plus pertinent de graphe de blocs est maintenant utilisé pour cette famille.

## Propriétés

Les cactus sont des graphes planaires extérieurs. Toute pseudo-forêt est un cactus. Un graphe non trivial est un cactus si et seulement si chaque bloc est soit un cycle simple, soit une arête unique.
La famille de graphes dans laquelle chaque composante est un cactus est fermée sous des opérations de mineurs du graphe. Cette famille de graphes peut être caractérisée par un seul mineur exclu, à savoir le graphe diamant à quatre sommets formé en supprimant une arête du graphe complet K$_4$.

## Cactus triangulaire

Un cactus triangulaire est un graphe cactus dans lequel tout cycle a longueur trois et toute arête appartient à un cycle. Par exemple, les graphes d'amitié (qui sont des graphes formés à partir d'une collection de triangles réunis en un seul sommet partagé) sont des cactus triangulaires. En plus d'être des graphes de cactus, les cactus triangulaires sont également des graphes de blocs et des graphes localement linéaires (en).
Les cactus triangulaires ont la propriété de rester connexes si on supprime un couplage ; pour un nombre de sommets donné, ces graphes ont le moins d'arêtes possibles avec cette propriété. Chaque arbre avec un nombre impair de sommets peut être augmenté en un cactus triangulaire en lui ajoutant des arêtes, cette adjonction est minimale avec la propriété de rester connexe après la suppression d'un couplage.
Le plus grand cactus triangulaire d'un graphe peut être déterminé en temps polynomial en utilisant un algorithme pour le problème de parité des matroïdes (en). Comme les graphes cactus triangulaires sont des graphes planaires, le plus grand cactus triangulaire peut être utilisé comme approximation du plus grand sous-graphe planaire, un sous-problème important de la planarisation (qui est une méthode d'extension des méthodes de tracé de graphes planaires à des graphes qui ne sont pas planaires, en plongeant les graphes non planaires dans un graphe planaire plus grand). En tant qu'algorithme d'approximation, cette méthode a un rapport d'approximation égal à 4/9, le meilleur rapport connu pour le problème du sous-graphe planaire maximum.
L'algorithme pour trouver le plus grand cactus triangulaire repose sur un théorème de Lovász et Plummer qui caractérise le nombre de triangles dans ce plus grand cactus. Lovász et Plummer considèrent des paires de partitions des sommets et des arêtes du graphe donné en sous-ensembles, avec la propriété que chaque triangle du graphe a soit deux sommets dans une même classe de la partition de sommets, soit les trois arêtes dans une même classe de la partition des arêtes ; ils appellent une paire de partitions avec cette propriété une paire « valide ». Le nombre de triangles dans le plus grand cactus triangulaire est égal au maximum, sur des paires de partitions valides ${\mathcal {P}}=\{V_{1},V_{2},\dots ,V_{k}\}$ et ${\mathcal {Q}}=\{E_{1},E_{2},\dots ,E_{m}\}$, de la somme
    $\sum _{i=1}^{m}{\frac {(u_{i}-1)}{2}}+n-k$,
où $n$ est le nombre de sommets du graphe et $u_{i}$ est le nombre de classes de sommets que rencontre la classe d'arêtes $E_{i}$.
En 2019, une borne extrémale précise a été donnée qui montre qu'étant donné un graphe planaire $G$ quelconque, il existe toujours un sous-graphe cactus $C\subseteq G$ contenant au moins $1/6$ des faces triangulaires de $G$. Ce résultat permet une analyse directe de l'algorithme d'approximation en 4/9 pour le problème du sous-graphe planaire maximum sans utiliser la formule min-max ci-dessus.

## La conjecture de Rosa

Une conjecture notable liée aux cactus triangulaires est la conjecture de Rosa, du nom d'Alexander Rosa, qui dit que tous les cactus triangulaires sont gracieux ou presque gracieux. Plus précisément,
    Tout cactus triangulaire avec t ≡ 0, 1 mod 4 blocs est gracieux, et tout cactus triangulaire avec t ≡ 2, 3 mod 4 est presque gracieux.

## Algorithmes et applications

Certains problèmes de l'emplacement d'installations qui sont NP-difficiles pour les graphes généraux, ainsi que d'autres problèmes de théorie des graphes, peuvent être résolus en temps polynomial pour les cactus$^,$.
Comme les cactus sont des cas particuliers de graphes planaires extérieurs, un certain nombre de problèmes d'optimisation combinatoire sur les graphes peuvent être résolus pour eux en temps polynomial.
Les cactus représentent des circuits électriques qui ont des propriétés utiles. Une des premières applications des cactus a été associée à la représentation des amplificateurs opérationnels$^,$.
Les cactus ont également été utilisés en génomique comparative comme moyen de représenter la relation entre différents génomes ou parties de génomes.
Si un cactus est connexe et que chacun de ses sommets appartient à au plus deux blocs, alors il est appelé un cactus de Noël. Chaque graphe polyédrique a un sous-graphe qui est un cactus de Noël qui inclut tous ses sommets, un fait qui joue un rôle essentiel dans une preuve de Leighton et Moitra 2010 que tout graphe polyédrique a un plongement glouton dans le plan euclidien, une attribution de coordonnées aux sommets pour lesquels le transfert glouton réussit à acheminer les messages entre toutes les paires de sommets.
En théorie topologique des graphes, les graphes dont les plongements cellulaires sont tous planaires sont exactement la sous-famille des graphes cactus avec la propriété supplémentaire que chaque sommet appartient à au plus un cycle. Ces graphes ont deux mineurs interdits, le graphe diamant et le graphe de l'amitié à cinq sommets.