Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна
The paper considers the problem of constructing diagrams of 2-connected minors of the Klein surface, that is, the simple graphs of nonorientable genus 3 that are minimal with respect to the genus during compression or removal of an arbitrary edge of it. The main result is a linear&a...
Saved in:
| Date: | 2023 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Subjects: | |
| Online Access: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/308 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Physico-mathematical modeling and informational technologies |
| Download file: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479680107413504 |
|---|---|
| author | Petrenjuk, Volodymyr Petrenjuk, Dmytro |
| author_facet | Petrenjuk, Volodymyr Petrenjuk, Dmytro |
| author_institution_txt_mv | [
{
"author": "Volodymyr Petrenjuk",
"institution": "к. фіз.-мат. н., доцент, Центральноукраїнський нац. техн. ун.-т, 25006, Україна, Кропивницький, пр-т. Університетський, 8"
},
{
"author": "Dmytro Petrenjuk",
"institution": "к. фіз.-мат. н., ІК ім. Глушкова В.М. НАН України, 03187, Україна, Київ, пр-т акад. Глушкова, 40"
}
] |
| author_sort | Petrenjuk, Volodymyr |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:31:10Z |
| description | The paper considers the problem of constructing diagrams of 2-connected minors of the Klein surface, that is, the simple graphs of nonorientable genus 3 that are minimal with respect to the genus during compression or removal of an arbitrary edge of it. The main result is a linear algorithm. which correctly solves this problem. |
| first_indexed | 2026-06-09T01:10:07Z |
| format | Article |
| fulltext |
72
doi.org/10.15407/fmmit2023.37.072
Про алгоритм побудови 2-зв’язних мінорів поверхні
Клейна
Володимир Петренюк1, Дмитро Петренюк2
1 к. фіз.-мат. н., доцент, Центральноукраїнський нац. техн. ун.-т, 25006, Україна, Кропивницький, пр-т.
Університетський, 8, , e-mail: petrenjukvi@i.ua
2 к. фіз.-мат. н., ІК ім. Глушкова В.М. НАН України, 03187, Україна, Київ, пр-т акад. Глушкова, 40, e-mail:
guitar_player@ukr.net
У роботі розглянута задача побудови діаграм 2-зв’язних мінорів поверхні Клейна, тобто
графів неорієнтованого роду 3 – мінімальних відносно роду при операціях стисканні чи
видаленні довільного його ребра. Основний результат – лінійний алгоритм, який коректно
вирішує цю задачу.
Ключові слова: граф-обструкція, поверхня Клейна, мінор, 2-зв’зність.
Вступ. Основні визначення та позначення узяті з [1, 2, 3]. Під точкою графа
розумітимемо або його вершину, або внутрішню точку його ребра. Розглянемо
задачу побудови всіх 2-зв’язних графів-обструкцій для 2 – поверхні Клейна із
множинами ребер, кожне з яких є суттєвим відносно неорієнтованого роду 3 при
операціях видалення ребра чи стискання його в точку, тобто мінорів
неорієнтованого роду 3. В [4] наведено числом 668, як потужність множини всіх
неізоморфних 2-зв’язних мінорів неорієнтованого роду 3, але немає їхніх
діаграм. Використаємо для побудови діаграм 2-зв’язних мінорів неорієнтованого
роду 3 структурні властивості таких графів, виписані в [5, 8]. Список всіх
неізоморфних мінорів неорієнтованого роду 2 містить 35 графів. В [6] наведено
12 базисних графів проективної площини, утворених перетвореннями методу
релятивних компонент, та наведено множину з 63-х базисних графів для
поверхні Клейна. Подібна задача побудови графів-обструкцій неорієнтованого
роду на основі множини відомих графів-обструкцій для неорієнтованого роду k
, має розв’язок для не більш ніж на 10 вершинах [7], а саме, повної множини для
проективної площини та неповної для інших поверхонь, зокрема, поверхні
Клейна.. Використаємо метод φ-перетворень графів та теорему 2 [8].
Твердження 1. Нехай іG - мінор неорієнтованого роду 2, а граф G поданий
як φ-образ )}{,())(),(\( 2
1
*
2
1
11
ij
j
jjnі aGgaHStеG , де 35)1(1i , еGі \ є іG -
мінор із видаленим ребром е та заданими точками з множини iM , },{ 21 jji aaM ,
досяжною на поверхні Клейна. Задано )(HStn - квазізірку з центром графом H
УДК 519.1
mailto:petrenjukvi@i.ua
mailto:guitar_player@ukr.net
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 72-76
73
та множиною висячих ребер як сумою підмножин m
iji ga 11 )},{( та n
mkjk gb 12 )},{( ,
де 1 mn , які висячими вершинами ia , kb приклеєно довільним чином до
двох точок з множини X , ),{ 21 jj ggX , причому множина точок Y ,
n
kiki baY 1},{ , на евклідовій площині має число досяжності ),( 0SYtH , де
2),( 0 SYtH , a множина X на поверхні Клейна має число досяжності
),( 2)( NXt HStn
, де 1),( 2)( NXt HStn
.
Якщо граф Н гомеоморфний одному з графів }\,,{ 53,24 eKKK та має задану
множину точок YХ , де YХ , досяжну на проективній площини, та з
числом досяжності ),( 0SYХtG відносно евклідової площини 0S , де
2),( 0 SYХtG , то граф G - мінор чи граф-обструкція неорієнтованого роду 3.
Доведення. Граф G , 17DG , можливо подати як призму, в основах якої лежать
два підграфи ізоморфних 4K , вершини яких попарно з’єднані ребрами.
Множину 1G ребер графа G розіб’ємо на класи еквівалентності відносно групи
автоморфізмів цього графа, тобто підмножини ребер графів обох основ та
множина з чотирьох ребер граней. Для кожного представника класу
еквівалентності проведемо стискання в точку. Результат наведено на рис.1. для
ребер класу з представником (4.6), на другій карті для (7,8). Згідно цих карт
кожна пара вершин цих стиснутих графів лежить або на границі 2-клітки чи
псевдоклітки, тобто є досяжною на проективній площині. Тому можливо
приклеїти до червоних пар квазізірки, з числа наведених на рис.2, ототожнивши
з парою неінцидентних вершин графа G . Варіанти склеєних φ-образів графів
наведені на рис.3.
Рис.1. Вкладення 17D в 2N на 1-й карті, на 2-й та на 3-й графи )6,4(G , )8,7(G вкладені в 1N .
Рис.2. Квазізірки )(HStn зі склеєними в пару точок підмножинами висячих вершин.
Володимир Петренюк, Дмитро Петренюк
Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна
74
Для побудови 2-зв’язних мінорів для 2N використаємо множину всіх неізомор-
фних мінорів проективної площини. Нехай 17: DG . Перебираємо всі різні
варіанти склейки по множині з двох точок графа G та пари точок квазізірки із
центром Н, можливим є ототодження кількох висячих вершинами в одну чи
другу точку пари склейки. Можливими будуть наступні варіанти φ-образу
зображені на рис 2, де виділено пару склеєних висячих вершин, які
приклеюватимемо до пари вершин графа 17D . Відмітимо, що деякі висячі ребра
квазізірки )(HStn стягнуті в точку як несуттєві відносно неорієнтованої поверхні
2N . Виберемо точки склейки робимо серед тих пар вершин, які є елементами
досяжної множини на 2N . Видалимо одне з ребер ),( ba та приклеїмо попарно
до кінцевих вершин видаленого ребра ті вершини квазізірки із центром Н та
множиною висячих вершин, розбитою на дві підмножини, що утворились при
ототожненні цих двох підмножин. Можливими є випадки склейок зображені на
рис.2. Доведення твердження 1 закінчене.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 72-76
75
Рис. 3. Діаграми 2-зв’язних мінорів для поверхні Клейна..
Твердження 2. Приблизне число 2-зв’язних мінорів поверхні Клейна - 700.
Доведення. Кількість зв’язних мінорів для проективної площини дорівнює 32.
Для вибраного наосліп серед цих графів мінору 17D маємо множину з 21-го
графа, наведену на рис. 3. Вважатимемо, що для кожного з графів-мінорів
проективної площини кількість мінорів приблизно однакова . Отже матимемо
число 2-зв’язних мінорів поверхні Клейна приблизно 700. Схематичне доведення
закінчене. Твердження 1 є основою лінійного алгоритму 1 яким можливо
побудовати всі 2-зв’язні мінори поверхні Клейна.
Алгоритм 1. Вхід: Множина
35
1}{ iiG із 35-ти мінорів проективної площини,
множина всіх неізоморфних вкладень цих графів в поверхню Клейна,
7
1)}({ jjjn HSt множина квазізірок для склеювання по двом парам виділених
вершин. Вихід: Множина 2-звязних графів-обструкцій
R
kkG 1)}({ неорієнто-
ваного роду 3.
Для циклу з параметром i від 1 до 35 виконати наступні дії:
1. ;: iGG
2. Побудуємо множину
||
1)},{( B
kkk baB всіх пар вершин графа G ,
які розташовані на границі 2-клітки поверхні клейна чи її
Володимир Петренюк, Дмитро Петренюк
Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна
76
псевдоклітки та зберігають досяжність в графах, отриманих
шляхом видалення довільного ребра чи стискання ребра в точку.
3. Для циклу з параметром k від 1 до |B| виконати наступні дії:
4. );,{:),( kk baba
5. Для циклу з параметром j від 1 до 7 виконати наступні дії:
a. );(:)( jjnn HStHSt
b. Склеїмо попарно (G , ),( ba ) та )(( HStn , )','( ba );
c.Отримаємо пару )(G , ),( ba ;
d. Виводимо )(G ;
e. Кінець циклу по j.
6. Кінець циклу по k
7. Кінець циклу по i.
8. Кінець алгоритму 1
Висновки. Таким чином в роботі наведена побудова лінійного побудови
діаграм 2-зв’язних мінорів поверхні Клейна.
Література
[1] Хоменко М. П. Топологические аспекты теории графов. Пpепpинт ИМ АHУ. Киев.. –
1973. -383 с.
[2] Хоменко М. П. -пеpетвоpення гpафiв. Пpепpинт ИМ АHУ. Киев. 1970. -299 с.
[3] Mohar B.,Thomassen C. Graphs on Surfaces. Johns Hopkins University Press, 2001. – 412 p.
[4] P.Skoda. Obstructions for embedding graphs into surfaces, Simon Frazer University, PhD
dissertation, 2012.-133 p.
[5] Петренюк В.І. Про структуру площинних підграфів графів-обструкцій неорієнтованої
поверхні заданого роду. Фізико математичне моделювання та інформаційні
технології. 2021, № 33. с. 105–109.
[6] Anna Flototto. Embeddability of graphs into the Klein surface. Dissertation, University
Bielefeld, 2010, -174 pp.
[7] 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.
[8] Петренюк В.І., Петренюк Д.А., Оришака О.В. Структура проективно площинних підграфів
графів - обструкцій заданої поверхні. Кібернетика та комп’ютерні технології, №2, Інститут
кібернетики НАНУ, Київ,2022, с.13-30.
http://cctech.org.ua/images/docs/Articles/2022/paper_22_2_2.pdf
On the algorithm for constructing 2-connected minors of the Klein
surface
Volodymyr Petrenjuk, Dmytro Petrenjuk
The paper considers the problem of constructing diagrams of 2-connected minors of the Klein
surface, that is, the simple graphs of nonorientable genus 3 that are minimal with respect to the
genus during compression or removal of an arbitrary edge of it. The main result is a linear
algorithm. which correctly solves this problem.
Отримано 28.03.23
http://rave.ohiolink.edu/etdc/view?acc_num=osu1209141894
http://cctech.org.ua/ua/index.php?option=com_content&view=article&id=357:abstract-22-2-2-artu&catid=11:vertikalnoe-menyu-ua&Itemid=101
http://cctech.org.ua/ua/index.php?option=com_content&view=article&id=357:abstract-22-2-2-artu&catid=11:vertikalnoe-menyu-ua&Itemid=101
http://cctech.org.ua/images/docs/Articles/2022/paper_22_2_2.pdf
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-308 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:10:07Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/1d/7a3295e23758b1bee69abe393a77641d.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-3082025-02-21T17:31:10Z On the algorithm for constructing 2-connected minors of the Klein surface Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна Petrenjuk, Volodymyr Petrenjuk, Dmytro граф-обструкція, поверхня Клейна, мінор, 2-зв’зність The paper considers the problem of constructing diagrams of 2-connected minors of the Klein surface, that is, the simple graphs of nonorientable genus 3 that are minimal with respect to the genus during compression or removal of an arbitrary edge of it. The main result is a linear algorithm. which correctly solves this problem. У роботі розглянута задача побудови діаграм 2-зв’язних мінорів поверхні Клейна, тобто графів неорієнтованого роду 3 – мінімальних відносно роду при операціях стисканні чи видаленні довільного його ребра. Основний результат – лінійний алгоритм, який коректно вирішує цю задачу. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-27 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/308 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 72-76 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 72-76 2617-5258 1816-1545 10.15407/fmmit2023.37 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/308/276 Авторське право (c) 2023 Володимир Петренюк, Дмитро Петренюк (Автор) |
| spellingShingle | граф-обструкція поверхня Клейна мінор 2-зв’зність Petrenjuk, Volodymyr Petrenjuk, Dmytro Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна |
| title | Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна |
| title_alt | On the algorithm for constructing 2-connected minors of the Klein surface |
| title_full | Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна |
| title_fullStr | Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна |
| title_full_unstemmed | Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна |
| title_short | Про алгоритм побудови 2-зв’язних мінорів поверхні Клейна |
| title_sort | про алгоритм побудови 2-зв’язних мінорів поверхні клейна |
| topic | граф-обструкція поверхня Клейна мінор 2-зв’зність |
| topic_facet | граф-обструкція поверхня Клейна мінор 2-зв’зність |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/308 |
| work_keys_str_mv | AT petrenjukvolodymyr onthealgorithmforconstructing2connectedminorsofthekleinsurface AT petrenjukdmytro onthealgorithmforconstructing2connectedminorsofthekleinsurface AT petrenjukvolodymyr proalgoritmpobudovi2zvâznihmínorívpoverhníklejna AT petrenjukdmytro proalgoritmpobudovi2zvâznihmínorívpoverhníklejna |