Одержано 22.02.2024; Виправлено 08.03.2024; Прийнято 19.03.2024

Надруковано 29.03.2024; Вперше Online 31.03.2024

https://doi.org/10.34229/2707-451X.24.1.4

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

УДК 519.85

Моделі графів-обструкцій поверхні Клейна

В.I. Петренюк ^{1 *} ,   Д.А. Петренюк ²

¹ Центральноукраїнський національний технічний університет, Кропивницький

² Інститут кібернетики імені В.М. Глушкова НАН України, Київ

^* Листування: petrenjukvi@i.u

 

Розглянуто задачу дослідження структури графів заданої зв’язності, які є обструкціями для заданої поверхні неорієнтованого роду та побудови їхніх моделей, з яких шляхом видалення чи стискання деякої множини ребер, утворюються графи-обструкції. Розглянуто питання про реберне покриття графe-обструкції заданого роду мінімальним числом квазізірок з центрами – площинними графами, які мають задані множини точок і всі ребра є суттєвими відносно числа досяжності 2 на евклідовій площині та має досяжність на проективній площині чи поверхні Клейна, наприклад, K₄, K_2,3 чи вироджений граф. Задача дослідження структури графів неорієнтованого роду розглядалася [4–6]. В роботі [7] методом релятивних компонент була стиснута множина мінорів для проективної площини до 12-ти базисних мінорів та побудовано множину з 62-х мінорів поверхні Клейна. Для цього розглядали всі неізоморфні мінімальні вкладення кожного з базисних мінорів та знаходили множину всіх різні пари вершин, які є досяжними на проективній площині при операціях видалення чи стискання в точку довільного ребра цього графа, потім до обраної пари точок приєднували пару несуміжних вершин графу K₅\e. В роботі [8] обчислена кількість 2-зв’язних графів-обструкцій для поверхні Клейна, частина діаграм цих графів наведена в [10]. Зазначимо, що наведене далі визначення кліткової відстані має аналогічне в [11].

Наш підхід, як продовження [9], полягатиме в знаходженні реберного покриття графу-обструкції G заданого роду мінімальним числом підграфів покриття з числа квазізірок з центрами – графами з суттєвими ребрами відносно числа досяжності чи неорієнтованого роду при операціях стискання в точку чи видалення ребра відносно заданої множини точок з числом досяжності 2 відносно евклідової площини та досяжними на проективні площині чи поверхні Клейна, наприклад, це підмножини множини точок графів K₄, K_2,3, K₅\е, K_r, r ³ 2, чи граф-обструкцій проективної площини. Також знайдено необхідні умови для побудови графів-обструкцій для поверхні Клейна шляхом ототожнення пар точок центрів та висячих вершин трьох квазізірок, тим самим маємо основу алгоритма побудови більшого числа графів-обструкцій для поверхні Клейна. Гіпотетично граф-обструкція заданого неорієнтованого роду n, n ³ 2, має вигляд циліндричної поверхні з n дисками-основами та бічною частиною, які можуть мати спільні множини точок на границях та на яких вкладені, принаймні частиною, графи-центри квазізірок, що мають задану множину точок досяжності 2 на евклідовій площині, а на бічній поверхні розміщуються висячі ребра, що перетинаються на площині та вкладаються без перетину за допомогою приклеєних до бічної поверхні лент Мебіуса. При цьому ребра матимуть, принаймні, два варіанти вкладення в бічну частину циліндричної поверхні, але не більше кількості приклеєних лент Мебіуса, завдяки цьому кожне висяче ребро вкладатиметься на ленті Мебіуса, або тільки з одним ребром, або з двома суміжними ребрами. Знайдено необхідні умови побудови моделей графів-обструкцій для поверхні Клейна шляхом ототожнення пар точок центрів та висячих вершин трьох квазізірок, тим самим маємо основу алгоритма побудови більшого числа графів-обструкцій для поверхні Клейна.

Основний результат: твердження 1, 2, 3 та алгоритм побудови моделей 3-зв’зних графів-обструкцій поверхні Клейна.

 

Ключові слова: j-пеpетвоpення гpафiв, неорієнтована поверхня, молелі графів-обструкцій неорієнтованого роду.

 

Цитувати так: Петренюк В.I., Петренюк Д.А. Моделі графів-обструкцій поверхні Клейна. Cybernetics and Computer Technologies. 2024. 1. С. 47–63. https://doi.org/10.34229/2707-451X.24.1.4

 

Список літератури

           1.     Хоменко М.П. j-пеpетвоpення гpафiв. Пpепpинт ИМ АHУ. Киев. 1973. 383 с.

           2.     Хоменко М.П. Топологические аспекты теории графов. Пpепpинт ИМ АHУ. Киев. 1970. 299 c.

           3.     Mohar B., Thomassen C. Graphs on Surfaces. Johns Hopkins University Press, 2001. 412 p. https://www.sfu.ca/~mohar/Book.html

           4.     Hur S. Тhe Кuratowski covering conjecture for graphs of order less than 10. Phd, Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1209141894

           5.     Archdeacon D., Huneke P. A Kuratowski Theorem for Nonorientable Surfaces. Journal of combinatorial theory, Series B. 1989. 46. P. 173–231. https://doi.org/10.1016/0095-8956(89)90043-9

           6.     Петренюк В.І. Про структуру площинних підграфів графів-обструкцій неорієнтованої поверхні заданого роду. Фізико математичне моделювання та інформаційні технології. 2021. № 33. C. 105–109. https://doi.org/10.15407/fmmit2021.33.105

           7.     Flȍtotto A. Embeddability of graphs into the Klein surface. Dissertation, University Bielefeld. 2010. 174 p.

           8.     Skoda P. Obstructions for embedding graphs into surfaces, Simon Frazer University, PhD dissertation. 2012. 133 р.

           9.     Петренюк В.І., Петренюк Д.А., Оришака О.В. Структура проективно площинних підграфів графів-обструкцій заданої поверхні. Кібернетика та комп'ютерні технології. 2022. № 2. С. 1–20. https://doi.org/10.34229/2707-451X.22.2

       10.     Петренюк В.І., Петренюк Д.А. Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна. Фізико-математичне моделювання та нформаційні технології. 2023. № 37. С. 72–74. https://doi.org/10.15407fmmit2023.37.072

       11.     Van Dam E.R., Koolen J.H., Tanaka H. Distance-regular graphs, E-JC, DS22: Apr 15. 2016. https://doi.org/10.37236/4925

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна