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.

Un graphe cactus.

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[1],[2]. 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[3].

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 K4[4].

Cactus triangulaire
Les graphes d'amitié sont des cactus triangulaires

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[5].

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[6].

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[7]. 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 et , de la somme

,

où est le nombre de sommets du graphe et est le nombre de classes de sommets que rencontre la classe d'arêtes .

En 2019, une borne extrémale précise a été donnée[8] qui montre qu'étant donné un graphe planaire quelconque, il existe toujours un sous-graphe cactus contenant au moins des faces triangulaires de . 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[9], 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[10],[11].

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[12].

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[13],[14].

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[15].

Si un cactus est connexe et que chacun de ses sommets appartient à au plus deux blocs, alors il est appellé 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[16].

Notes et références
  1. Harary et Uhlenbeck (1953).
  2. Husimi (1950).
  3. Par exemple, le compte-rendu lien Math Reviews, de 1983 par Robert E. Jamison d'un article utilisant l'autre définition attribue l'ambiguïté à une erreur dans un livre de Mehdi Behzad et Gary Chartrand.
  4. El-Mallah et Colbourn (1988).
  5. Farley et Proskurowski (1982).
  6. Călinescu et al. (2002).
  7. Lovász et Plummer (2009).
  8. Chalermsook, Schmid et Uniyal (2019).
  9. Rosa (1988).
  10. Ben-Moshe, Bhattacharya et Shi (2005).
  11. Zmazek et Zerovnik (2005).
  12. Korneyenko (1994).
  13. Nishi et Chua (1986).
  14. Nishi (1991).
  15. Paten et al..
  16. Nordhaus et al. (1972).

Bibliographie
  • Jasine Babu, Veena Prabhakaran et Arko Sharma, « A linear time algorithm for computing the eternal vertex cover number of cactus graphs », arxiv,‎ (arXiv 2005.08058).
  • Csilla Bujtás et Marko Jakovac, « Relating the total domination number and the annihilation number of cactus graphs and block graphs », Ars Mathematica Contemporanea, vol. 16, no 1,‎ , p. 183–202 (DOI 10.26493/1855-3974.1378.11d, lire en ligne).
  • Ehab El-Mallah et Charles J. Colbourn, « The complexity of some edge deletion problems », IEEE Transactions on Circuits and Systems, vol. 35, no 3,‎ , p. 354–362 (DOI 10.1109/31.1748).
  • Arthur M. Farley et Andrzej Proskurowski, « Networks immune to isolated line failures », Networks, vol. 12, no 4,‎ , p. 393–403 (DOI 10.1002/net.3230120404, Math Reviews 686540).
  • Gruia Călinescu, Cristina G Fernandes, Ulrich Finkler et Howard Karloff, « A Better Approximation Algorithm for Finding Planar Subgraphs », Journal of Algorithms, vol. 27, no 2,‎ , p. 269–302 (DOI 10.1006/jagm.1997.0920, S2CID 8329680, CiteSeerx 10.1.1.47.4731).
  • Parinya Chalermsook, Andreas Schmid et Sumedha Uniyal, « A Tight Extremal Bound on the Lovasz Cactus Number in Planar Graphs », CoRR, vol. abs/1804.03485,‎ (DOI 10.4230/LIPIcs.STACS.2019.19, arXiv 1804.03485, S2CID 4751972).
  • Alexander Rosa, « Cyclic Steiner Triple Systems and Labelings of Triangular Cacti », Scientia, vol. 1,‎ , p. 87–95..
  • Boaz Ben-Moshe, Binay Bhattacharya et Qiaosheng Shi, « Efficient algorithms for the weighted 2-center problem in a cactus graph », Lecture Notes in Computer Science, vol. 3827 « Algorithms and Computation, 16th Int. Symp., ISAAC 2005 »,‎ , p. 693–703 (ISBN 978-3-540-30935-2, DOI 10.1007/11602613_70).
  • Blaz Zmazek et Janez Zerovnik, « Estimating the traffic on weighted cactus networks in linear time », dans Ninth International Conference on Information Visualisation (IV'05), (ISBN 978-0-7695-2397-2, DOI 10.1109/IV.2005.48, S2CID 15963409), p. 536–541.
  • Korneyenko, N. M., « Combinatorial algorithms on a class of graphs », Discrete Applied Mathematics, vol. 54, nos 2–3,‎ , p. 215–217 (DOI 10.1016/0166-218X(94)90022-1 ) — Traduction depuis Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci., (1984) no. 3, p. 109-111.
  • Tetsuo Nishi et Leon O. Chua, « Topological proof of the Nielsen-Willson theorem », IEEE Transactions on Circuits and Systems, vol. 33, no 4,‎ , p. 398–405 (DOI 10.1109/TCS.1986.1085935).
  • Tetsuo Nishi et Leon O. Chua, « Uniqueness of solution for nonlinear resistive circuits containing CCCS's or VCVS's whose controlling coefficients are finite », IEEE Transactions on Circuits and Systems, vol. 33, no 4,‎ , p. 381–397 (DOI 10.1109/TCS.1986.1085934).
  • Tetsuo Nishi, « On the number of solutions of a class of nonlinear resistive circuit », dans Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore, , p. 766–769.
  • Benedict Paten, Mark Diekhans, Dent Earl, John St. John, Jian Ma, Bernard Suh et David Haussler, « Cactus Graphs for Genome Comparisons », Lecture Notes in Computer Science, vol. 6044 « Research in Computational Molecular Biology »,‎ , 410–425 (ISBN 978-3-642-12682-6, DOI 10.1007/978-3-642-12683-3_27).
  • Tom Leighton et Ankur Moitra, « Some Results on Greedy Embeddings in Metric Spaces », Discrete & Computational Geometry, vol. 44, no 3,‎ , p. 686–705 (DOI 10.1007/s00454-009-9227-6 , S2CID 11186402, lire en ligne).
  • E. A. Nordhaus, R. D. Ringeisen, B. M. Stewart et A. T. White, « A Kuratowski-type theorem for the maximum genus of a graph », Journal of Combinatorial Theory, vol. 12, no 3,‎ , p. 260–267 (DOI 10.1016/0095-8956(72)90040-8 , Math Reviews 0299523).
  • Frank Harary et George E. Uhlenbeck, « On the number of Husimi trees, I », Proceedings of the National Academy of Sciences, vol. 39, no 4,‎ , p. 315–322 (PMID 16589268, PMCID 1063779, DOI 10.1073/pnas.39.4.315, Math Reviews 0053893).
  • Kodi Husimi, « Note on Mayers' theory of cluster integrals », Journal of Chemical Physics, vol. 18, no 5,‎ , p. 682–684 (DOI 10.1063/1.1747725, Math Reviews 0038903).

Lien externe
  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.