Kaktuszgráf

A matematika, azon belül a gráfelmélet területén egy kaktuszgráf (cactus) (néha kaktuszfa – cactus tree) olyan összefüggő gráf, melynek bármely két körének legfeljebb egy közös csúcsa van. Ezzel egyenértékű definíció szerint olyan összefüggő gráf, melynek minden éle legfeljebb egy egyszerű körhöz tartozik, vagy (nemtriviális kaktuszoknál) melyek minden blokkja (kétszeresen összefüggő komponense) él vagy kör.

Tulajdonságok

A kaktuszok külsíkgráfok. Minden pszeudofa kaktusz. Egy nemtriviális gráf pontosan akkor kaktusz, ha minden kétszeresen összefüggő komponense vagy él, vagy egyszerű kör. Azon gráfok családja, melyek minden összefüggő komponense kaktuszgráf, a gráfminorképzés műveletére nézve zárt. A család egyetlen tiltott minorával meghatározható, ez a K₄ teljes gráfból egyetlen él eltávolításával kapott gyémántgráf.^[1]

Háromszögű kaktusz

A háromszögű kaktuszgráfok olyan speciális kaktuszok, melyek minden köre három hosszúságú. Ezek a kaktuszgráfok egyben blokkgráfok is. A legnagyobb háromszögű kaktuszt tetszőleges gráfban polinom időben meg lehet keresni matroidparitás-probléma egy algoritmusa segítségével. Mivel a háromszögű kaktuszok síkba rajzolhatók, a legnagyobb háromszögű kaktusz felhasználható a legnagyobb síkbarajzolható részgráf keresésekor, ami a planarizáció fontos részproblémája. Approximációs algoritmusként az elért approximációs arány 4/9, ami a legnagyobb síkbarajzolható részgráf problémájánál ismert legjobb arány.^[2]

Algoritmusok és alkalmazások

Néhány probléma, köztük létesítmény-elhelyezési problémák, melyek általános gráfokon NP-nehéz bonyolultságúak, kaktuszgráfokon polinom időben megoldhatók.^[3]^[4] Mivel a kaktuszok a külsíkgráfok speciális esetei, egyes kombinatorikus optimalizálási problémák polinom időben megoldhatók rajtuk.^[5] A kaktuszok által reprezentált elektromos áramkörök hasznos tulajdonságokkal rendelkeznek. A kaktuszok egyik korai alkalmazása a műveleti erősítők ábrázolásában volt.^[6]^[7]^[8] A kaktuszokat az összehasonlító genomikában a különböző genomok vagy genomrészek közötti kapcsolatok ábrázolására használják.^[9] Ha egy kaktuszgráf összefüggő, és minden csúcsa legfeljebb két blokkhoz tartozik, akkor karácsonyi kaktusznak nevezik. Minden poliédergráfban található olyan karácsonyi kaktusz részgráf, ami az összes csúcsot tartalmazza; ez a tény jelentős szerepet kapott (Leighton & Moitra 2010) bizonyításában, miszerint minden poliédergráfnak van az euklideszi síkba történő mohó beágyazása.^[10] A topologikus gráfelméletben azok a gráfok, melyek celluláris beágyazásai mind síkbarajzolhatók a kaktuszgráfoknak pontosan azzal a részhalmazával egyezik meg, melyekben minden csúcs legfeljebb egy körhöz tartozik. Ezeknek a gráfoknak két tiltott minoruk van, a gyémántgráf és az öt csúcsú barátsággráf (pillangó).^[11]

Történet

A kaktuszgráfokat Husimi-fák néven tanulmányozta Frank Harary és George Uhlenbeck, Kôdi Husimi korábbi, megegyező témájú munkái előtt tisztelegve.^[12]^[13] Ugyanebben a Harary–Uhlenbeck-cikkben még csak azokat a gráfokat nevezte közülük kaktusznak, melyek minden köre háromszög volt, a jelenleg elterjedt definíció tetszőleges hosszúságú köröket megenged. Eközben a Husimi-fa kifejezést elkezdték azokra a gráfokra alkalmazni, melyek minden blokkja teljes gráf; az összekeverhetőség elkerülése érdekében azokra a blokkgráf, a Husimi-fákra inkább a kaktuszgráf kifejezést kezdték használni.^[14]

Fordítás

Ez a szócikk részben vagy egészben a Cactus graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ El-Mallah, Ehab & Colbourn, Charles J. (1988), "The complexity of some edge deletion problems", IEEE Transactions on Circuits and Systems 35 (3): 354–362, DOI 10.1109/31.1748
↑ Călinescu, Gruia; Fernandes, Cristina G & Finkler, Ulrich et al. (2002), "A Better Approximation Algorithm for Finding Planar Subgraphs", Journal of Algorithms, 2 27: 269– 302, DOI 10.1006/jagm.1997.0920
↑ Ben-Moshe, Boaz; Bhattacharya, Binay & Shi, Qiaosheng (2005), "Efficient algorithms for the weighted 2-center problem in a cactus graph", Algorithms and Computation, 16th Int. Symp., ISAAC 2005, vol. 3827, Lecture Notes in Computer Science, Springer-Verlag, pp. 693–703, DOI 10.1007/11602613_70
↑ Zmazek, Blaz & Zerovnik, Janez (2005), "Estimating the traffic on weighted cactus networks in linear time", Ninth International Conference on Information Visualisation (IV'05), pp. 536–541, ISBN 0-7695-2397-8, DOI 10.1109/IV.2005.48
↑ Korneyenko, N. M. (1994), "Combinatorial algorithms on a class of graphs", Discrete Applied Mathematics 54 (2–3): 215–217, DOI 10.1016/0166-218X(94)90022-1 Translated from Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci., (1984) no. 3, pp. 109-111 (oroszul)
↑ Nishi, Tetsuo & Chua, Leon O. (1986), "Topological proof of the Nielsen-Willson theorem", IEEE Transactions on Circuits and Systems 33 (4): 398–405, DOI 10.1109/TCS.1986.1085935
↑ Nishi, Tetsuo & Chua, Leon O. (1986), "Uniqueness of solution for nonlinear resistive circuits containing CCCS’s or VCVS’s whose controlling coefficients are finite", IEEE Transactions on Circuits and Systems 33 (4): 381–397, DOI 10.1109/TCS.1986.1085934
↑ Nishi, Tetsuo (1991), "On the number of solutions of a class of nonlinear resistive circuit", Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore, pp. 766–769
↑ Paten, Benedict; Diekhans, Mark & Earl, Dent et al. (2010), "Cactus Graphs for Genome Comparisons", Research in Computational Molecular Biology, vol. 6044, Lecture Notes in Computer Science, pp. 410–425, ISBN 978-3-642-12682-6, DOI 10.1007/978-3-642-12683-3_27
↑ Leighton, Tom & Moitra, Ankur (2010), "Some Results on Greedy Embeddings in Metric Spaces", Discrete & Computational Geometry 44 (3): 686–705, doi:10.1007/s00454-009-9227-6, <http://people.csail.mit.edu/moitra/docs/dcg-greedy.pdf>.
↑ Nordhaus, E. A.; Ringeisen, R. D. & Stewart, B. M. et al. (1972), "A Kuratowski-type theorem for the maximum genus of a graph", Journal of Combinatorial Theory, Series B 12: 260–267, DOI 10.1016/0095-8956(72)90040-8
↑ Harary, Frank & Uhlenbeck, George E. (1953), "On the number of Husimi trees, I", Proceedings of the National Academy of Sciences 39 (4): 315–322, DOI 10.1073/pnas.39.4.315
↑ Husimi, Kodi (1950), "Note on Mayers' theory of cluster integrals", Journal of Chemical Physics 18 (5): 682–684, DOI 10.1063/1.1747725
↑ Lásd pl. MR 0659742, Robert E. Jamison egy 1983-as értékelését egy másik cikkről, ami a blokkgráfokat Husimi-fáknak nevezi; Jamison a hibát Mehdi Behzad és Gary Chartrand könyvének tulajdonítja.

További információk

Application of Cactus Graphs in Analysis and Design of Electronic Circuits

Matematikaportál • összefoglaló, színes tartalomajánló lap

[1] El-Mallah, Ehab & Colbourn, Charles J. (1988), "The complexity of some edge deletion problems", IEEE Transactions on Circuits and Systems 35 (3): 354–362, DOI 10.1109/31.1748

[2] Călinescu, Gruia; Fernandes, Cristina G & Finkler, Ulrich et al. (2002), "A Better Approximation Algorithm for Finding Planar Subgraphs", Journal of Algorithms, 2 27: 269– 302, DOI 10.1006/jagm.1997.0920

[3] Ben-Moshe, Boaz; Bhattacharya, Binay & Shi, Qiaosheng (2005), "Efficient algorithms for the weighted 2-center problem in a cactus graph", Algorithms and Computation, 16th Int. Symp., ISAAC 2005, vol. 3827, Lecture Notes in Computer Science, Springer-Verlag, pp. 693–703, DOI 10.1007/11602613_70

[4] Zmazek, Blaz & Zerovnik, Janez (2005), "Estimating the traffic on weighted cactus networks in linear time", Ninth International Conference on Information Visualisation (IV'05), pp. 536–541, ISBN 0-7695-2397-8, DOI 10.1109/IV.2005.48

[5] Korneyenko, N. M. (1994), "Combinatorial algorithms on a class of graphs", Discrete Applied Mathematics 54 (2–3): 215–217, DOI 10.1016/0166-218X(94)90022-1 Translated from Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci., (1984) no. 3, pp. 109-111 (oroszul)

[6] Nishi, Tetsuo & Chua, Leon O. (1986), "Topological proof of the Nielsen-Willson theorem", IEEE Transactions on Circuits and Systems 33 (4): 398–405, DOI 10.1109/TCS.1986.1085935

[7] Nishi, Tetsuo & Chua, Leon O. (1986), "Uniqueness of solution for nonlinear resistive circuits containing CCCS’s or VCVS’s whose controlling coefficients are finite", IEEE Transactions on Circuits and Systems 33 (4): 381–397, DOI 10.1109/TCS.1986.1085934

[8] Nishi, Tetsuo (1991), "On the number of solutions of a class of nonlinear resistive circuit", Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore, pp. 766–769

[9] Paten, Benedict; Diekhans, Mark & Earl, Dent et al. (2010), "Cactus Graphs for Genome Comparisons", Research in Computational Molecular Biology, vol. 6044, Lecture Notes in Computer Science, pp. 410–425, ISBN 978-3-642-12682-6, DOI 10.1007/978-3-642-12683-3_27

[10] Leighton, Tom & Moitra, Ankur (2010), "Some Results on Greedy Embeddings in Metric Spaces", Discrete & Computational Geometry 44 (3): 686–705, doi:10.1007/s00454-009-9227-6, <http://people.csail.mit.edu/moitra/docs/dcg-greedy.pdf>.

[11] Nordhaus, E. A.; Ringeisen, R. D. & Stewart, B. M. et al. (1972), "A Kuratowski-type theorem for the maximum genus of a graph", Journal of Combinatorial Theory, Series B 12: 260–267, DOI 10.1016/0095-8956(72)90040-8

[12] Harary, Frank & Uhlenbeck, George E. (1953), "On the number of Husimi trees, I", Proceedings of the National Academy of Sciences 39 (4): 315–322, DOI 10.1073/pnas.39.4.315

[13] Husimi, Kodi (1950), "Note on Mayers' theory of cluster integrals", Journal of Chemical Physics 18 (5): 682–684, DOI 10.1063/1.1747725

[14] Lásd pl. MR 0659742, Robert E. Jamison egy 1983-as értékelését egy másik cikkről, ami a blokkgráfokat Husimi-fáknak nevezi; Jamison a hibát Mehdi Behzad és Gary Chartrand könyvének tulajdonítja.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]