Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна
Анотація
У роботі розглянута задача побудови діаграм 2-зв’язних мінорів поверхні Клейна, тобто графів неорієнтованого роду 3 – мінімальних відносно роду при операціях стисканні чи видаленні довільного його ребра. Основний результат – лінійний алгоритм, який коректно вирішує цю задачу.
Посилання
Khomenko M.P. (1973). Topological aspects of graph theory. Kyiv: Preprint of the IM AHU. [in Ukrainian].
Khomenko M. P. (1970). -the transformation of graphs. Kyiv: Preprint of the IM AHU. [in Ukrainian].
Mohar B., Thomassen C. (2001). Graphs on Surfaces. Johns Hopkins University Press.
P. Skoda. (2012). Obstructions for embedding graphs into surfaces, Simon Frazer University, Ph.D. dissertation.
Petrenjuk V.I. (2021). On the structure of planar subgraphs of obstruction graphs of the nonorientable surface of a given genus. Physical-mathematical modeling and information technologies, 33, 105–109. Retrieved from: https://doi.org/10.15407/fmmit2021.33.105. [in Ukrainian].
Anna Flototto. (2010). Embeddability of graphs into the Klein surface. University Bielefeld. Ph.D. dissertation.
Hur Sur J. (2008). The Kuratowski covering conjecture for graphs of the order less than 10. Ohio State University, Ph.D. dissertation. Retrieved from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1209141894.
Petrenyuk V.I., Petrenyuk D.A., Orishaka O.V. (2022), The structure of projective planar subgraphs of graphs - obstructions of a given surface. Cybernetics and computer technologies, 2, 13-30. Retrieved from: http://cctech.org.ua/images/docs/Articles/2022/paper_22_2_2.pdf. [in Ukrainian].
Авторське право (c) 2023 Володимир Петренюк, Дмитро Петренюк (Автор)
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.