Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна
В роботі встановлені методом φ-перетворення графів структурні властивості 9-ти вершинних графів-обструкцій для поверхні неорієнтованого роду 2. The structure of the 9 vertex obstructive graphs for the nonorientable surface of the genus 2 is established by the method of φ-transformations of the graph...
Gespeichert in:
| Veröffentlicht in: | Кібернетика та комп’ютерні технології |
|---|---|
| Datum: | 2020 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/179347 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна / В.I. Петренюк, Д.А. Петренюк // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 4. — С. 65-86. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-179347 |
|---|---|
| record_format |
dspace |
| spelling |
Петренюк, В.I. Петренюк, Д.А. 2021-04-29T15:52:59Z 2021-04-29T15:52:59Z 2020 Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна / В.I. Петренюк, Д.А. Петренюк // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 4. — С. 65-86. — Бібліогр.: 7 назв. — укр. 2707-4501 DOI:10.34229/2707-451X.20.4.5 https://nasplib.isofts.kiev.ua/handle/123456789/179347 519.85 В роботі встановлені методом φ-перетворення графів структурні властивості 9-ти вершинних графів-обструкцій для поверхні неорієнтованого роду 2. The structure of the 9 vertex obstructive graphs for the nonorientable surface of the genus 2 is established by the method of φ-transformations of the graphs. The problem of establishing the structural properties of 9 vertex obstruction graphs for the surface of the undirected genus 2 by the method of -transformation of graphs is considered. The article has an introduction and 5 sections. The introduction contains the main definitions, which are illustrated, to some extent, in Section 1, which provides several statements about their properties. Sections 2 – 4 investigate the structural properties of 9 vertex obstruction graphs for an undirected surface by presenting as a -image of several graphs homeomorphic to one of the Kuratovsky graphs and at least one pla-nar or projective-planar graph. Section 5 contains a new version of the proof of the statement about the peculi-arities of the minimal embeddings of finite graphs in nonorientable surfaces, namely, that, in contrast to oriented surfaces, cell boundaries do not contain repeated edges. uk Інститут кібернетики ім. В.М. Глушкова НАН України Кібернетика та комп’ютерні технології Математичне моделювання та чисельні методи Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна About Structure of Graph Obstructions for Klein Surface with 9 Vertices Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна |
| spellingShingle |
Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна Петренюк, В.I. Петренюк, Д.А. Математичне моделювання та чисельні методи |
| title_short |
Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна |
| title_full |
Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна |
| title_fullStr |
Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна |
| title_full_unstemmed |
Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна |
| title_sort |
про структуру 9-ти вершинних графів-обструкцій для поверхні клейна |
| author |
Петренюк, В.I. Петренюк, Д.А. |
| author_facet |
Петренюк, В.I. Петренюк, Д.А. |
| topic |
Математичне моделювання та чисельні методи |
| topic_facet |
Математичне моделювання та чисельні методи |
| publishDate |
2020 |
| language |
Ukrainian |
| container_title |
Кібернетика та комп’ютерні технології |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
About Structure of Graph Obstructions for Klein Surface with 9 Vertices |
| description |
В роботі встановлені методом φ-перетворення графів структурні властивості 9-ти вершинних графів-обструкцій для поверхні неорієнтованого роду 2.
The structure of the 9 vertex obstructive graphs for the nonorientable surface of the genus 2 is established by the method of φ-transformations of the graphs. The problem of establishing the structural properties of 9 vertex obstruction graphs for the surface of the undirected genus 2 by the method of -transformation of graphs is considered. The article has an introduction and 5 sections. The introduction contains the main definitions, which are illustrated, to some extent, in Section 1, which provides several statements about their properties. Sections 2 – 4 investigate the structural properties of 9 vertex obstruction graphs for an undirected surface by presenting as a -image of several graphs homeomorphic to one of the Kuratovsky graphs and at least one pla-nar or projective-planar graph. Section 5 contains a new version of the proof of the statement about the peculi-arities of the minimal embeddings of finite graphs in nonorientable surfaces, namely, that, in contrast to oriented surfaces, cell boundaries do not contain repeated edges.
|
| issn |
2707-4501 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/179347 |
| citation_txt |
Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна / В.I. Петренюк, Д.А. Петренюк // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 4. — С. 65-86. — Бібліогр.: 7 назв. — укр. |
| work_keys_str_mv |
AT petrenûkvi prostrukturu9tiveršinnihgrafívobstrukcíidlâpoverhníkleina AT petrenûkda prostrukturu9tiveršinnihgrafívobstrukcíidlâpoverhníkleina AT petrenûkvi aboutstructureofgraphobstructionsforkleinsurfacewith9vertices AT petrenûkda aboutstructureofgraphobstructionsforkleinsurfacewith9vertices |
| first_indexed |
2025-11-24T16:10:10Z |
| last_indexed |
2025-11-24T16:10:10Z |
| _version_ |
1850484080201695232 |
| fulltext |
МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ЧИСЕЛЬНІ МЕТОДИ
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 65
КІБЕРНЕТИКА
та КОМП'ЮТЕРНІ
ТЕХНОЛОГІЇ
В роботі встановлені методом -перетво-
рення графів структурні властивості 9-ти
вершинних графів-обструкцій для поверхні
неорієнтованого роду 2.
Ключові слова: граф, поверхня Клейна, стру-
ктурні властивості графа, графи-обст-
рукції, неорієнтована поверхня, стрічка
Мебіуса.
B.I. Петренюк, Д.А. Петренюк, 2020
УДК 519.85 DOI:10.34229/2707-451X.20.4.5
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
ПРО СТРУКТУРУ 9-ТИ ВЕРШИННИХ
ГРАФІВ-ОБСТРУКЦІЙ ДЛЯ ПОВЕРХНІ КЛЕЙНА
Вступ. Розглянемо задачу вивчення методом -пере-
творення графів структурних властивостей 9-ти вер-
шинних графів-обструкцій для неорієнтованої повер-
хні kN роду k , 2k . Основні поняття та позначення
взятi із [1–3], всі графи неорієнтовані без кратних ре-
бер та петель. B роботах [4, 5] отримано деякі неізо-
морфні графи-обструкції для 2N – поверхні Клейна
на не більш ніж 9-ти вершинах, а в [6] наведено діаг-
рами цих графів та 36-ти нових графів-обструкцій на
9-ти вершинах, окрім цього наведено 27 нових графів-
обструкцій, утворених шляхом розщеплення вершин
8-ми вершинних графів-обструкцій для поверхні 2N .
Нехай 2-многовид S без країв неорієнтованого роду
( )S подано як поверхню 'S орієнтованого роду
( ')S , де ( ') 0S , ( ) 2 ( ')S S r , до якої приклеє-
но r стрічок Мебіуса, 0r ; наприклад, поверхня S
– пляшка Клейна коли ( ') 0S і 2r , чи поверхня
S роду ( ) 3S матиме 'S -тор із однією приклеє-
ною стрічкою Мебіуса. Для заданого вкладення f ,
:f G S , графа G в S та заданої множини точок
, 0 1G G , визначимо , ,Gt S f ,
, ,Gt t S f , число досяжності множини відно-
сно S , якщо існує підмножина
1
t
G iS s ,
\ ( )GS S f G , що задовольняє умові:
1
( )
t
i
i
f s X
1,
( )
t
i
i i j
f s X
,
1,2,..,j t .
Будемо говорити, що множина має число досяж-
ності t , ,Gt S t , відносно S , якщо серед всіх
неізоморфних вкладень f , :f G S число t
є найменшим серед чисел , ,Gt S f . Вважатимемо
надалі, що позначено .
Стаття має вступ та 5 розділів. У чотирьох розділах
досліджено структурні властивості 9-ти вершинних
графів-обструкцій для неорієнтованої поверхні kN шля-
хом подання як -образу одного з графів Куратовського
https://doi.org/10.34229/2707-451X.20.4.5
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
66 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
та принаймні одного площинного підграфа. В розділі 5 наведено варіант вивчення властивостей,
характерних для вкладень графів до неорієнтованих поверхонь і основний результат.
Визначення 1. Нехай задано вкладення f , :f G S , графа G в S , яке реалізує
,t ,Gt S t , де \ ( )GS S f G ,
1
t
G iS s . Будемо говорити, що відносно заданої поверхні
S множина має характеристику ( , , )G X S f , ( , , )G X S f , якщо існує трійок кліток
3
1іs
з множини GS , на границях яких підмножини i , iX X , розміщуються довільним чином
і задовольняють співвідношенню: 0
1 2 1{ }G s s a 0
2 3 2{ }G s s a 0
1 3G s s
3{ }a , та є найменший по включенню підграф 'G графа G , (можливо вироджений в точку), який
містить точки
3
1ia попарного перетину границь кліток
3
1іs . Множина матиме відносно S
характеристику ( , )G X S , якщо ( , ) max ( , , )G GX S X S f , де максимум береться по всім неізо-
морфним вкладенням f , :f G S , що реалізують ,Gt S t .
Визначення 2. Нехай задано вкладення f , :f G S , графа G в S , яке реалізує
,t ,Gt S t , де
1
t
G iS s , \ ( )GS S f G , та виконується рівність ( , ) 0G X S . Будемо
говорити, що відносно S множина матиме характеристику ( , )G X f , ( , )G X f , 1 ,
якщо існує підмножина { , , }і j ks s s множини GS , яка задовольняє:
1
1 1{( , )}i jG s s a b
і
1
2 2{( , )}k jG s s a b , для всіх i j k , , , 1,2,3i j k . На границях { , , }і j ks s s множина
розміщується довільним чином, якщо не містить точок ребер 1 1( , )a b , 2 2( , )a b . На границях
{ , , }і j ks s s множина розміщується особливим чином (без точок множини Х на
1 2 2 20 1 10\ ( , ) {( , ),( , )}js L a a a a a a ), якщо містить принаймні одну точку цих ребер. Також є клітка
0s та, можливо, клітка 00s . Клітка 0s , 0 ( \ ( )) \ Gs S f G S , має границю, яка містить: простий
ланцюг 1 2( , )L a a ненульової довжини із кінцевими вершинами 1 2,a a , що також належить js ;
два простих ланцюги, можливо, вироджених в точку, 1 1 12( , )L a a , 1 2 22( , )L a a , які також належать
is та ks , відповідно; ребро 12 22( , )a a . Клітка 00s , 00 0( \ ( )) \ ( { })Gs S f G S s , має границю,
яка містить простий ланцюг 10 20( , )L a a ненульової довжини із кінцевими вершинами
10 20,a a спільно із js . Множина матиме характеристику ( , )G X S , якщо
( , ) max ( , , )G GX S X S f , де максимум береться по неізоморфним вкладенням, що реалізують
,Gt S t та ( , )G X S .
Визначення 3. Позначимо ( )Gkrt M , ( )Gkr krt M , kr – кратність доступу до елементів підм-
ножини M множини точок графа G , як максимальна кількість варіантів вибору різних підмножин
( , )GS M S множини клітин \ ( )S f G , на границях яких розміщуються всі точки з підмножини М,
де максимум узятий по всіх мінімальних вкладеннях f , :f G S , графа G в S . Іншими слова-
ми, це найбільша кількість зірок, які приєднані кінцевими вершинами до кожного елемента підм-
ножини M та вкладені до різних kr 2-кліток із \ ( )S f G .
Визначення 4. Позначимо ( , , )Gms M s f , ( , , )Gk ms M s f , k – сторонність доступу із довільної
внутрішньої точки замкнутої заданої клітки s до кожної точки заданої підмножини M множини
точок графа G , де 2M , що полягатиме у наявності такої клітки s , ( ) ( , , )f Gs S M S s ,
ПРО СТРУКТУРУ 9-ТИ ВЕРШИННИХ ГРАФІВ-ОБСТРУКЦІЙ ДЛЯ ПОВЕРХНІ КЛЕЙНА
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 67
де f – задане мінімальне вкладення :f G S графа G в поверхню S , яка на своїй границі s
містить k копій підмножини M . Найбільшу кількість копій підмножини M на s серед всіх клі-
тин s заданого мінімального вкладення f , :f G S , графа G в поверхню S позначимо
( , )Gms M f . Іншими словами, це найбільша кількість зірок графа G , які приєднані кінцевими
вершинами до кожного із принаймні трьох елементів множини M та вкладені до однієї клітки
з \ ( )S f G заданого мінімального вкладення f , :f G S , графа G в S .
Визначення 5. Будемо називати 1 2( ( , ), ( , ),..., ( , ))G G G Nms M f ms M f ms M f вектором l сторон-
нього доступу до множини M точок графа G із довільної внутрішньої точки замкнутої заданої
клітки s , \ ( )ks S f G , ( )l l s , до кожної точки заданої підмножини M , де 0l , 2M ,
1{ }N
k kf – множина всіх неізоморфних мінімальних вкладень kf , :kf G S графа G в S . Най-
більше , ( )l l l s , серед чисел ( , )G kms M f узяте по всім s та всім kf , \ ( )ks S f G , називатимемо
характеристикою l стороннього доступу до множини M точок графа G та позначимо ( )Gms M .
Визначення 6. Будемо називати множину підграфів M , 1{ }N
k kM H графа-обструкції H для
2N , вкладеної до евклідової площини, такою, що мінімально покриває множину ребер графа, якщо
матиме місце співвідношення
1 1 1 1 1
1 1( { } ) & (( , 1,2,... )( { } \ ))N N
k k k k jH H j j k H H H .
Позначення 1. Будемо називати підграф K графа-обструкції H для 2N локально проективно-
площинним, якщо | ( )Kf K D , де 2:f H N – мінімальне вкладення графа H в 2N , D – елеме-
нтарний диск поверхні 2N . Будемо позначати
1 2 3, , ,,, ( )
mn n n nSt K граф K , із i -тої вершини якого ви-
ходять , 0,i in n висячих ребер, приєднаних до різних вершин, де 1,2,3,... .i m
Частина 1
Наведемо ілюстрації до вищенаведених визначень. На рис. 1 в 1-му ряду на перших трьох кар-
тах показана циклічна кліткова структура, інші карти ілюструють зіркову структуру на проектив-
ній площині та пляшці Клейна, на 2-му ряду на перших трьох картах показано ланцюжкову клітко-
ву структуру на проективній площині та пляшці Клейна.
РИС. 1. Циклічна, зіркова і ланцюжкова кліткові структури на проективній площині та пляшці Клейна
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
68 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Твердження 1. Мають місце співвідношення.
1. Граф G , 6G K , має на 2N число досяжності множини вершин 0
6 2, 2Gt K N і не має
вершини з подвійним доступом та при видаленні довільного ребра зменшує на 1 число 0
6 2,Gt K N .
2. Граф G , 5G K , має на 2N число досяжності множини вершин 0
2, 1Gt G N та дві верши-
ни з двостороннім доступом, а граф G , 5 \G K e , має на 2N три вершини з двостороннім доступом.
3. Граф G , 7G K , має рід 3G .
4. Граф G , 8 1,2\G K K , має рід 3G .
5. Граф G , 6 2\ 2G K K , має на 2N
число досяжності множини вершин 0
2, 2Gt G N та має
вершину з подвійним доступом, а 6 2\ 3G K K задовольняє на 2N рівності 0
2, 2Gt G N та має
тільки одну вершину без подвійного доступу.
6. Множина вершин
0
3,3K графа 3,3K має кратний доступ і є досяжною відносно 2N .
7. Три графи 4K , що утворюють дві пари із одним спільним ребром, для кожної своїм, мають
три пари ребер, cхрещених на площині, вкладаються на дві стрічки Мебіуса.
Доведення цих тверджень показано на рис. 2, де на перших двох картах – вкладення графа 7K
в 3N , відповідно, побудовані як продовження вкладення 6f графа 6K в 2N та вкладення 5f графа
5K в 2N , причому синім (темним) кольором позначено клітку з множини 2 5 5\ ( )N f K , на якій ма-
ємо подвійний доступ до вершин з підмножин {4}, {1}. На четвертій карті показано мінімальне
вкладення графа 8 1,2\K K в 4N . На п’ятій карті – вкладення графа 6K в 2N , яке реалізує число
0
2, 2Gt G N , та видно зменшення цього числа при видаленні ребра (3, 5).
РИС. 2. На другій карті вершини 1, 4 графа 5K мають на 2N двосторонній доступ, на 3-й, 5-й, 6-й,
8-й, 9-й картах ребра позначені дугами та відрізками товстих ліній. Три підграфи графа 33,G
що ізоморфні, 4K утворюють пару із одним спільним ребром (6, 8) та пару із одним спільним
ребром (7, 9), вкладаються на 1N із двома стрічками Мебіуса
ПРО СТРУКТУРУ 9-ТИ ВЕРШИННИХ ГРАФІВ-ОБСТРУКЦІЙ ДЛЯ ПОВЕРХНІ КЛЕЙНА
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 69
Лема 1. Нехай граф G є φ-образом графів-обструкцій 1G та 2G при φ-перетворенні визначено-
му наступним чином:
2
1 2 1 2
1
( , ( )) ( , )
i
G G e e G e
, де ( , )e a b , 1e G , ( , )i i ie a b є ребром або
частиною ребра графа iG , 1,2i . Для орієнтованого роду ( )G мають місце наступні твердження:
1) якщо принаймні одна кінцева вершина кожного з ребер ie не матиме двостороннього досту-
пу, то маємо рівність 1 2( ) ( ) ( )G G G ;
2) якщо кожна кінцева вершина одного з ребер ie має двосторонній доступ, то матимемо рів-
ність 1 2( ) ( ) ( ) 1G G G .
Доведення леми 1 для довільних графів-обструкцій 1G та 2G аналогічне доведенню для двох
графів 5K , показаному на рис. 3 та 4. Виконання тверджень 1) та 2) проілюстровано для двох вкла-
дених в тор графів, отриманих з двох пар графів 4 3,3( , )K K , 4 5( , )K K , де ребра графа 4K сині (тем-
ні), шляхом φ-перетворень, заданих на парі ребер кожної з цих пар графів. Зазначимо, що наявність
двостороннього доступу до ототожнених кінцевих вершин ребра означитиме відсутність додатко-
вої 2-ручки. Також граф 7 \K e подаємо як склейку графа 5K , вкладеного до 2N – пляшки Клейна
із двостороннім доступом до двох вершин, та двох зірок із суміжними центрами на 5-ти
та 6-ти ребрах. Мінімальне вкладення графа 7 \K e до 2N отримаємо, якщо в кольорову клітку
графа 5K вкладемо (без перетину ребер) дві зірки із суміжними центрами на 5-ти та 6-ти ребрах-
променях.
РИС. 3. До тверджень леми 1 наведено два перші графи (зліва-направо), що отримані з двох графів 5K
двома наступними φ-перетвореннями: 1) по парі ребер; 2) по ребру ( , )e a b та частині ребра ,u
відповідно, де кольоровою (не білою) є клітка вкладення в тор графа 5,K до якої вкладено інший
граф 5K та виконано склейку; 3) наведено склейку по ребру ,e ( , ),e a b графів 5K , 3,3K ;
4) наведено мінімальне вкладення графа 7 \K e до 2N – пляшки Клейна
РИС. 4. Наведемо два вкладені в тор графи (зліва-направо), отримані з двох пар графів 4 3,3( , )K K , 4 5( , )K K
φ-перетвореннями на парах ребер
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
70 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Лема 2. Нехай граф G – φ-образ графів-обструкцій 1G та 2G для проективної площини при
φ-перетворенні визначеному таким чином:
2
1 2 1 2
1
( , ( )) ( , )
i
G G e e G e
, де ( , )e a b , 1e G ,
( , )i i ie a b – ребро або частина ребра графа iG , 1,2i . Тоді для неорієнтованого роду ( )G
не виконуються твердження леми 1.
Доведення. Дійсно, із показаних на рис. 5 вкладень до проективної площини графів 5K
та 3,3K , видно відсутність двостороннього доступу до довільної підмножини їхніх вершин. Але для
5 / (4,7)K є двосторонній доступ до пари суміжних вершин 3, 4, 7, який не впливає на рід графа 2A
зі списку графів-обструкцій для проективної площини.
РИС. 5. Мінімальні вкладення графів 5 / (4,7)K , 2 / (1,4)A , 5K , 3,3K до проективної площини
Частина 2
Твердження 2. Мають місце співвідношення.
1. Граф 1G – φ-образ графа 6K та квазізірки 4,4,4 3( )St K при наступному φ-перетворенні:
4 4
* 4 4
6 4,4,4 3 1 1 1
1 1
( ( ), ( )) ( ,{{ } } )ij i j ij j i
i j
K St K a x G a
, де i jx – кінцеві вершини квазізірки ототож-
нюються із вершинами ija трьох підграфів 4K графа 6K , які попарно мають одне спільне ребро,
а множина ребер графа 1G мінімально покрита трьома графами 4K .
2. Граф 2G – φ-образ графа 6K та квазізірки 4,4,4 3 2( \ )St K K при φ-перетворенні:
4 4
* 4 4
6 4,4,4 3 2 1 1 1
1 1
( ( \ ), ( )) ( ,{{ } } )ij i j ij j i
i j
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ото-
тожнюються із вершинами ija трьох підграфів 4K графа 6K , три з яких утворюють послідовність,
бо мають по одному спільному ребру, причому множина ребер графа 2G мінімально покрита
трьома графами 5K і одним 6K . Доведення цих тверджень показано на рис. 6.
РИС. 6. Граф 1G вкладений до проективної площини 1N із двома стрічками Мебіуса,
граф 2G вкладено на 3N , утвореної з пляшки Клейна та стрічки Мебіуса
9
G1 = K9 –
1
2
3
4
5 6
7 8
7
9
8
1
2
3
4
5
6
G1
ПРО СТРУКТУРУ 9-ТИ ВЕРШИННИХ ГРАФІВ-ОБСТРУКЦІЙ ДЛЯ ПОВЕРХНІ КЛЕЙНА
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 71
Твердження 3. Мають місце співвідношення.
1. Граф 3G – φ-образ графа 5K та квазізірки 4,6,6,6 4( )St K при φ-перетворенні:
4
* 4
5 4,6,6,6 4 3 1
1
( ( ), ( )) ( ,{ } )i i i i
i
K St K a x G a
, де i jx – кінцеві вершини квазізірки ототожнюються
із вершинами ia графа 5K , де
4,6,6,6 4( ) 4deg ( ) 4St K x ,
4,6,6,6 4( )deg ( ) 2St K ix , 1,2,3i , причому мно-
жина ребер графа 3G мінімально покрита двома графами 5K із спільною вершиною та трьома
графами 4K (один з яких містить 3K , який унеможливлює двосторонній доступ до точок з
4
1{ }i ia – множини приєднання).
2. Граф 4G – φ-образ графа 5K та квазізірки 5,5,5,5 4 2( \ 2 )St K K при φ-перетворенні:
4
* 4
5 5,5,5,5 4 2 4 1
1
( ( \ 2 ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототожню-
ються із вершинами ia графа 5K , де
5,5,5,5 4 2( \2 )deg ( ) 2St K K ix , 1,2,3,4i , причому множина ребер
графа 4G мінімально покрита одним графом 5K та чотирма графами 4K .
3. Граф 5G – φ-образ графа 5 \K e та квазізірки 5,5,5,5 4 2( \ )St K K при φ-перетворенні:
4
* 4
5 5,5,5,5 4 2 5 1
1
( \ ( \ ), ( )) ( ,{ } )i i i i
i
K e St K K a x G a
, де i jx – кінцеві вершини квазізірки ототож-
нюються із вершинами ia графа 5 \K e , де
5,5,5,5 4 2( \ )deg ( ) 3St K K ix , 1,2,3,4i , причому множина
ребер графа 5G мінімально покрита одним графом 5 \ (4,5)K , одним колесом 4W з чотирма
спицями (частинним 2,3K на вершинах 4, 5, 6, 7, 8, 9 із ребрами (6, 7), (6, 9)) та двома 4K .
4. Граф 6G – φ-образ графа 5K та квазізірки 2,2,3,4 4 2( \ )St K K при наступному φ-перетворенні:
4
* 4
5 2,2,3,4 4 2 6 1
1
( ( \ ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де кінцеві вершини ix квазізірки ототожнюють-
ся із вершинами ia графа 5K , де
2,2,3,4 4 2( \ )deg ( ) 3St K K ix , 1,2,3,4i , причому множина ребер графа
6G мінімально покрита одним графом 5K , одним 5 \ (7,5)K і трьома графами 4K . Доведення цих
тверджень показано на рис. 7.
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
72 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
РИС. 7. Графи 3G , 4G , 5G , 6G вкладені мінімально на 2N з приклеєною стрічкою Мебіуса
Твердження 4. Мають місце співвідношення.
1. Граф 7G – φ-образ графа 5K та квазізірки 1
2,2,3,3,4 4 3( \ )St K K при φ-перетворенні:
5
1 * 5
5 2,2,3,3,4 4 3 7 1
1
( ( \ ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототожню-
ються із вершинами ia графа 5K , 1x , 2x мають степінь 2, 3x , 4x мають степінь 3,
1
2,2,3,3,4 4 3
4( \ )
deg ( ) 4
St K K
x , причому множина ребер графа 7G мінімально покрита одним графом
5K , одним 2,3K , одним 5 \ (4,5)K і двома графами 4K .
2. Граф 8G – φ-образ графа 5 \K e , де 3 4( , )e a a , та квазізірки 3,3,4,4 4( \ )St C e при φ-пере-
творенні:
4
* 4
5 3,3,4,4 4 8 1
1
( \ ( \ ), ( )) ( ,{ } )i i i i
i
K e St C e a x G a
, де i jx – кінцеві вершини квазізірки
ототожнюються із вершинами ia графа 5 \K e , 1x , 2x мають степінь 3, 3x , 4x мають степінь 4,
де 4 \C e – простий ланцюг довжини 3, причому множина ребер графа 8G мінімально покрита
одним графом 5 \K e і п’ятьма графами 4K . Доведення тверджень показано на рис. 8.
РИС. 8. Графи 7G , 8G вкладено до проективної площини 1N із двома стрічками Мебіуса
Твердження 5. Мають місце співвідношення.
1. Граф 9G – φ-образ графа 5K та квазізірки 2,2,2,2,2 4( )St K при φ-перетворенні:
5
* 5
5 2,2,2,2,2 4 9 1
1
( ( ), ( )) ( ,{ } )i i i i
i
K St K a x G a
, де i jx – кінцеві вершини квазізірки ототожнюються
із вершинами ia графа 5K , ix мають степінь 2, 1,2,3,4,5i , причому множина ребер графа 9G
мінімально покрита одним 5K і чотирма 4K .
ПРО СТРУКТУРУ 9-ТИ ВЕРШИННИХ ГРАФІВ-ОБСТРУКЦІЙ ДЛЯ ПОВЕРХНІ КЛЕЙНА
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 73
2. Граф 10G – φ-образ графа 5K та квазізірки
1
1,1,2,4,4 4 2( \ )St K K при φ-перетворенні:
5
1 * 5
5 1,1,2,4,4 4 2 9 1
1
( ( \ ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототожню-
ються із вершинами ia графа 5K , 1x , 2x мають степінь 1, 3x , 4x мають степінь 4,
1
1,1,2,4,4 4 2
5( \ )
deg ( ) 2
St K K
x , причому множина ребер графа 10G мінімально покрита множинами ребер
графів 5K і трьох графів 4K (рис. 9).
РИС. 9. Графи 9G , 10G вкладені в проективну площину 1N із двома стрічками Мебіуса
Твердження 6. Мають місце співвідношення.
1. Граф 11G – φ-образом графа 5K та квазізірки
1
5,5,5,5 4 2( \ 2 )St K K при φ-перетворенні:
4
1 * 4
5 5,5,5,5 4 2 11 1
1
( ( \ 2 ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототожню-
ються із вершинами ia графа 5K , 1x , 2x мають степінь 2, 3x , 4x мають степінь 4, причому множина
ребер графа 11G мінімально покрита множинами ребер графів 5K , двох 4K та одного
6 2\ 2K K .
2. Граф 12G – φ-образ графа 5K та квазізірки
1
3,4,4,5 4 2( \ )St K K при наступному φ-перетворенні:
5
1 * 5
5 3,4,4,5 4 2 12 1
1
( ( \ ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототожню-
ються із вершинами ia графа 5K , 1x , 2x мають степінь 2, 3x , 4x мають степінь 1,
1
3,4,4,5 4 2
5( \ )
deg 3
St K K
x , причому множина ребер графа 12G мінімально покрита множинами ребер
графів 5K та чотирьох графів 4K .
РИС. 10. Графи 11G , 12G вкладені в проективну площину 1N із двома стрічками Мебіуса
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
74 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Твердження 7. Мають місце співвідношення.
1. Граф 13G – φ-образ графа 5K та квазізірки
1
4,5,5,6 4 2( \ )St K K при такому φ-перетворенні:
5
1 * 5
5 4,5,5,6 4 2 13 1
1
( ( \ ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототожню-
ються із вершинами ia графа 5K , 1x , 2x мають степінь 2, 3x , 4x мають степінь 3,
1
4,5,5,6 4 2
5( \ )
deg 3
St K K
x , причому множина ребер графа 13G мінімально покрита множинами ребер
графів 5K та п’ятьох графів 4K .
2. Граф 14G – φ-образ графа 5K та квазізірки
1
4,5,5,6 4 2( \ )St K K при наступному φ-перетворенні:
4
1 * 4
5 4,5,5,6 4 2 14 1
1
( ( \ ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототожню-
ються із вершинами ia графа 5K , 1x , 3x , 2x мають степінь 2, 4x має степінь 4,
причому множина
ребер графа G14 мінімально покрита множинами ребер графів 5K , одного графа 5 \ (7, 8)K та двох
графів 4K (рис. 11).
РИС. 11. Графи 13G , 14G вкладені мінімально в проективну площину 1N із двома приклеєними
стрічками Мебіуса
Твердження 8. Мають місце співвідношення.
1. Граф 15G – φ-образ графа 5 \K e та квазізірки
1
5,5,5,6 4 2( \ )St K K при φ-перетворенні:
4
1 * 4
5 5,5,5,7 4 2 15 1
1
( \ ( \ ), ( )) ( ,{ } )i i i i
i
K e St K K a x G a
, де i jx – кінцеві вершини квазізірки ототож-
нюються із вершинами ia графа 5K , 1x , 2x мають степінь 2, 3x , 4x мають степінь 4,
причому мно-
жина ребер графа 15G мінімально покрита множинами ребер трьох графів 5 \K e та двох графів 4K .
2. Граф 16G – φ-образ графа 5K та квазізірки
1
4,5,6,6 4 2( \ )St K K при φ-перетворенні:
3
1 * 3
5 4,5,6,6 4 2 16 1
1
( ( \ ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототожню-
ються із вершинами ia графа 5K , 1x , 2x мають степінь 4, 3x мають степінь 3, причому множина
ребер графа 16G мінімально покрита множинами ребер графів 5K , двох графів 5 \ (9, 8)K та
графа 4K (рис. 12).
ПРО СТРУКТУРУ 9-ТИ ВЕРШИННИХ ГРАФІВ-ОБСТРУКЦІЙ ДЛЯ ПОВЕРХНІ КЛЕЙНА
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 75
РИС. 12. Графи 15G , 16G вкладені в евклідову площину із трьома приклеєними стрічками Мебіуса
та в проективну площину 1N із двома приклеєними стрічками Мебіуса, відповідно
Частина 3
Твердження 9. Мають місце співвідношення.
1. Граф 17G – φ-образ графа 5 \K e та квазізірки
1
4,5,6,6 4 1,2( \ )St K K при φ-перетворенні:
5
1 * 5
5 4,5,6,6 4 1,2 17 1
1
( \ ( \ ), ( )) ( ,{ } )i i i i
i
K e St K K a x G a
, де i jx – кінцеві вершини квазізірки ототож-
нюються із вершинами ia графа 5K , 1x , 2x мають степінь 3, 3x має степінь 6, 4x має степінь 1,
5x
має степінь 2, причому множина ребер графа 17G мінімально покрита множинами ребер двох
графів 5 \ (1, 2)K та п’ятьох графів 4K .
2. Граф 18G – φ-образ графа 5K та квазізірки 4,4,4,5 2 2( )St K K при φ-перетворенні:
5
* 5
5 4,4,4,5 2 2 18 1
1
( ( ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототож-
нюються із вершинами ia графа 5K , 1x , 2x , 3x мають степінь 4,
4x має степінь 2, 5x має
степінь 1, причому множина ребер графа 18G мінімально покрита множинами ребер графів 1
7 2\K K
та двох графів 4K (рис. 13).
РИС. 13. Графи 17G , 18G вкладені мінімально в 1N із двома приклеєними стрічками Мебіуса
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
76 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Твердження 10. Мають місце співвідношення.
1. Граф 19G – φ-образ графа 5K та квазізірки
1
5,5,5,5 4 2( \ 2 )St K K при φ-перетворенні:
3
1 * 3
5 5,5,5,5 4 2 19 1
1
( ( \ 2 ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототож-
нюються із вершинами ia графа 5K , 1x , 2x , 3x , 4x мають степінь 4, причому множина ребер гра-
фа 19G мінімально покрита множинами ребер одного графа 4K та 2-х графів 1
5 2\K K .
2. Граф 20G – φ-образ графа 5K та квазізірки
1
4,5,5,5 4 2( \ )St z K при φ-перетворенні:
5
1 * 5
5 4,5,5,5 4 2 20 1
1
( ( \ ), ( )) ( ,{ } )i i i i
i
K St z K a x G a
, де 4z – простий цикл довжини 4, ix – кінцеві
вершини квазізірки ототожнюються із вершинами ia графа 5K , 1x , 2x мають степінь 1, 3x , 4x , 5x
мають степінь 4, причому множина ребер графа 20G мінімально покрита множинами ребер графів
5K та шістьма графами 4K (рис. 14).
РИС. 14. Графи 19G , 20G вкладені мінімально в 1N із двома приклеєними стрічками Мебіуса
та в евклідову площину із трьома приклеєними стрічками Мебіуса, відповідно
Твердження 11. Мають місце співвідношення.
1. Граф 21G – φ-образ графа 5 \K e та квазізірки 5,5,6,7 4( )St K при φ-перетворенні:
5
* 5
5 5,5,6,7 4 21 1
1
( \ ( ), ( )) ( ,{ } )i i i i
i
K e St K a x G a
, де i jx – кінцеві вершини квазізірки ототожню-
ються із вершинами ia графа 5 \K e , 1x має степінь 1, 2x , 3x мають степінь 2, 4x , 5x мають
степінь 3, причому множина ребер графа 21G мінімально покрита ребрами графа 5 \K e і чотирьох
графів 4K .
2. Граф 22G – φ-образ графа 5K та квазізірки
1
5,5,5,5 4 2( \ 2 )St K K φ-перетворенні:
5
1 * 5
5 5,5,5,5 4 2 22 1
1
( ( \ 2 ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототож-
нюються із вершинами ia графа 5K , 1x , 2x мають степінь 1, 3x має степінь 2, 4x , 5x
мають сте-
пінь 4, причому множина ребер графа 22G мінімально покрита множинами ребер графа 5K
та чотирьох графів 4K (рис. 15).
ПРО СТРУКТУРУ 9-ТИ ВЕРШИННИХ ГРАФІВ-ОБСТРУКЦІЙ ДЛЯ ПОВЕРХНІ КЛЕЙНА
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 77
РИС. 15. Графи 21G , 22G вкладені в евклідову площину із трьома приклеєними стрічками Мебіуса
та в 1N із двома стрічками Мебіуса, відповідно
Твердження 12. Мають місце співвідношення.
1. Граф 23G – φ-образ графа 5K та квазізірки 4,5,5,6 4( )St K при φ-перетворенні:
4
* 4
5 4,5,5,6, 4 23 1
1
( ( ), ( )) ( ,{ } )i i i i
i
K St K a x G a
, де i jx – кінцеві вершини квазізірки ототожнюються
із вершинами ia графа 5K , 1x , 2x , 3x мають степінь 2, 4x має степінь 3, причому множина ребер
графа 23G мінімально покрита множинами ребер графа 5K та чотирьох графів 4K .
2. Граф 24G – φ-образ графа 5K та квазізірки 4,5,6,6 4( )St K при φ-перетворенні:
4
* 4
5 4,5,6,6 4 24 1
1
( ( ), ( )) ( ,{ } )i i i i
i
K St K a x G a
, де i jx – кінцеві вершини квазізірки ототожнюються
із вершинами ia графа 5K , 1x має степінь 1, 2x має степінь 2, 4x , 3x мають степінь 3, причому
множина ребер графа 24G мінімально покрита множинами ребер графа 5K та чотирьох графів 4K
(рис. 16).
РИС. 16. Графи 23G , 24G вкладені мінімально в 1N із двома приклеєними стрічками Мебіуса
Твердження 13. Мають місце співвідношення.
1. Граф 25G – φ-образ графа 5 \K e та квазізірки 5,5,5,6 4( \ )St K e при φ-перетворенні:
5
* 5
5 5,5,5,6, 4 25 1
1
( \ ( \ ), ( )) ( ,{ } )i i i i
i
K e St K e a x G a
, де i jx – кінцеві вершини квазізірки ототож-
нюються із вершинами ia графа 5 \K e , 1x , 2x , 3x
мають степінь 2, 4x має степінь 4, 5x має
степінь 1, причому множина ребер графа 25G мінімально покрита множинами ребер двох 5 \K e
та чотирьох 4K .
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
78 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
2. Граф 26G – φ-образ графа 5 \K e та квазізірки 5,5,6,6 4( \ )St K e при φ-перетворенні:
5
* 5
5 5,5,5,6, 4 26 1
1
( \ ( \ ), ( )) ( ,{ } )i i i i
i
K e St K e a x G a
, де i jx – кінцеві вершини квазізірки ототож-
нюються із вершинами ia графа 5 \K e , 1x , 2x
мають степінь 1, 4x
має степінь 2,
3x , 5x мають
степінь 4, причому множина ребер графа 26G мінімально покрита множинами ребер трьох 5 \K e
та двох 4K (рис. 17).
РИС. 17. Графи 25G , 26G вкладені в евклідову площину із трьома стрічками Мебіуса
Твердження 14. Мають місце співвідношення.
1. Граф 27G – φ-образ графа 5K та квазізірки 5,5,5,6 4( )St K при φ-перетворенні:
3
* 3
5 5,5,5,6, 4 27 1
1
( ( ), ( )) ( ,{ } )i i i i
i
K St K a x G a
, де i jx – кінцеві вершини квазізірки ототожнюються
із вершинами ia графа 5K , 1x , 2x , 3x мають степінь 3, причому множина ребер 27G мінімально
покрита множинами ребер 5K та трьох 4K .
2. Граф 28G – φ-образ графа 5 \K e та квазізірки
1
4,4,5,7 4 1,2( \ )St K K при φ-перетворенні:
5
1 * 5
5 4,4,5,7 4 1,2 28 1
1
( \ ( \ ), ( )) ( ,{ } )i i i i
i
K e St K K a x G a
, де i jx – кінцеві вершини квазізірки ототож-
нюються із вершинами ia графа 5 \K e , 1x , 2x , 3x мають степінь 2, 4x , 5x мають степінь 2, причо-
му множина ребер графа 28G мінімально покрита множинами ребер графа 5 \K e та чотирьох
графів 4K (рис. 18).
РИС. 18. Графи 27G вкладено в 1N із двома приклеєними стрічками Мебіуса,
28G вкладено в евклідову площину із трьома приклеєними стрічками Мебіуса
ПРО СТРУКТУРУ 9-ТИ ВЕРШИННИХ ГРАФІВ-ОБСТРУКЦІЙ ДЛЯ ПОВЕРХНІ КЛЕЙНА
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 79
Частина 4
Твердження 15. Мають місце співвідношення.
1. Граф 29G – φ-образ графа 5 \K e та квазізірки 5,5,5,5 4( )St K при φ-перетворенні:
4
* 4
5 5,5,5,5 4 29 1
1
( \ ( )), ( )) ( ,{ } )i i i i
i
K e St K a x G a
, де i jx – кінцеві вершини квазізірки ототожню-
ються із вершинами ia графа 5 \K e , 1x , 2x , 3x мають степінь 2, 4x має степінь 3, причому мно-
жина ребер графа 29G мінімально покрита множинами ребер двох графів 5 \K e та трьох графів 4K .
2. Граф 30G – φ-образ графа 5K та квазізірки
1
4,4,6,6 4 2( \ )St K K при φ-перетворенні:
4
1 * 4
5 4,4,6,6 4 2 30 1
1
( ( \ ), ( )) ( ,{ } )i i i i
i
K St K K a x G a
, де i jx – кінцеві вершини квазізірки ототожню-
ються із вершинами ia графа 5K , 1x , 2x мають степінь 1, 3x має степінь 2,
4x , 5x мають степінь
3, причому множина ребер графа 30G мінімально покрита множинами ребер графа 5K та трьох
графів 4K (рис. 19).
РИС. 19. Графи 29G , 30G вкладені в 1N із двома приклеєними стрічками Мебіуса
Твердження 16. Мають місце співвідношення.
1. Граф 31G – φ-образ графа 5K та квазізірки 4,4,6,6 4( )St K при φ-перетворенні:
4
* 4
5 4,4,6,6 4 31 1
1
( ( ), ( )) ( ,{ } )i i i i
i
K St K a x G a
, де i jx – кінцеві вершини квазізірки ототожнюються
із вершинами ia графа 5K , 1x , 2x , 3x , 4x мають степінь 2,
причому множина ребер графа 31G
мінімально покрита множинами ребер графа 5K та чотирьох графів 4K .
2. Граф 32G – φ-образ графа 5 \K e та квазізірки 3,5,5,6 4( \ )St z e при φ-перетворенні:
5
* 5
5 3,5,5,6 4 32 1
1
( \ ( \ )), ( )) ( ,{ } )i i i i
i
K e St z e a x G a
, де 4 \z e – простий ланцюг довжини 3, ix –
кінцеві вершини квазізірки ототожнюються із вершинами ia графа 5 \K e , 1x має степінь 1, 3x , 2x ,
4x мають степінь 3, 5x має степінь 2, причому множина ребер графа 32G мінімально покрита
множинами ребер графа 5 \K e та чотирьох графів 4K (рис. 20).
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
80 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
РИС. 20. Графи 31G , 32G вкладені мінімально в 1N із двома стрічками Мебіуса
Твердження 17. Мають місце співвідношення.
1. Граф 33G – φ-образ графа 5K та квазізірки 5,5,5,5 4( )St K при φ-перетворенні:
4
* 4
5 5,5,5,5 4 33 1
1
( ( ), ( )) ( ,{ } )i i i i
i
K St K a x G a
, де i jx – кінцеві вершини квазізірки ототожнюються
із вершинами ia графа 5K , 1x , 2x , 3x , 4x
мають степінь 2,
причому множина ребер графа 33G
мінімально покрита множинами ребер графа 5K та трьох графів 4K .
2. Граф 34G – φ-образ графа 5K та квазізірки 3,3,5,6 4( )St K при φ-перетворенні:
5
* 5
5 3,3,5,6 4 34 1
1
( ( ), ( )) ( ,{ } )i i i i
i
K St K a x G a
, де i jx – кінцеві вершини квазізірки ототожнюються
із вершинами ia графа 5K , 1x , 2x , 3x , 4x
мають степінь 2,
5x
має степінь 1, причому множина
ребер графа 34G мінімально покрита множинами ребер графа 5K та трьох графів 4K (рис. 21).
РИС. 21. Графи 33G , 34G вкладені мінімально в 1N із двома стрічками Мебіуса
Твердження 18. Мають місце співвідношення.
1. Граф 35G – φ-образ графа 5K та квазізірки 4,4,6,6 4( )St K при φ-перетворенні:
3
* 3
5 4,4,6,6 4 35 1
1
( ( ), ( )) ( ,{ } )i i i i
i
K St K a x G a
, де i jx – кінцеві вершини квазізірки ототожнюються
із вершинами ia графа 5K , 1x , 2x мають степінь 2,
3x має степінь 4,
причому множина ребер гра-
фа 35G мінімально покрита множинами ребер двох графів 5K та графа 4K .
ПРО СТРУКТУРУ 9-ТИ ВЕРШИННИХ ГРАФІВ-ОБСТРУКЦІЙ ДЛЯ ПОВЕРХНІ КЛЕЙНА
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 81
2. Граф 36G – φ-образ графа 5K та квазізірки 5,5,5,6 4( )St K при φ-перетворенні:
4
* 4
5 5,5,5,6 4 36 1
1
( ( ), ( )) ( ,{ } )i i i i
i
K St K a x G a
, де i jx – кінцеві вершини квазізірки ототожнюються
із вершинами ia графа 5K , 1x , 2x , 3x мають степінь 2,
4x
має степінь 3, причому множина ребер
графа 36G мінімально покрита множинами ребер графів 5K , 5 \ (8,5)K
та графа
4K (рис. 22).
РИС. 22. Графи 35G , 36G вкладено в 1N із двома приклеєними стрічками Мебіуса
Частина 5
Твердження 19. Для довільного мінімального вкладення f простого графа G до неорієнтова-
ної поверхні N мають місце співвідношення.
1. Немає ребер , ', ( , ), ' ( , )e e e a b e b a на границі довільної клітки s , ( , )Gs S N f , але мо-
жуть мати місце повторення деяких вершин.
2. Немає повторення двох пар вершин чи двох пар частин ребер , ( , )e e a b ,
', ' ( , )e e c d , які
попарно розділяють одна одну та лежать на границі довільної клітки s , ( , )Gs S N f .
3. Немає двох 2-кліток 1 2,s s , де 1 2, ( , )Gs s S N f , на границях яких розташовані повторення
трьох виділених ребра із різним порядком слідування.
Доведення. Співвідношення 1. Припустимо, методом від протилежного, що для деякого міні-
мального вкладення f графа G до неорієнтованої поверхні N границі клітки s , ( , )Gs S N f , є
два ребра e , 'e , ( , )e a b , ' ( , )e b a , які є протилежно направленими копіями ребра
( ) ( ( ), ( )),e a b що розташовані на границі s , тобто на поверхні N є одна стрічка Мебіуса, яка
містить одне ребро ( )e , де операція – ототожнення точок на границях кліток є оберненою до
операції розбиття на клітки поверхні .N Оскільки кожне з цих ребер належить перетину однієї з
двох пар кліток 1( , )s s , 2( , )s s , то видаливши ребро e , ми, тим самим, видаляємо й ребро 'e , утво-
рюючи простий цикл Z , який містить всі ті ребра простого графа \G e , що належали границям
кліток s , 1s , 2s , та стане границею нової клітки 0s , 0 \ ( , )G es S N f . Побудуємо вкладення 'f ,
' :f G N , де \ \' | |G e G ef f , 0'( )f e s , причому вершинами нового ребра стане кінцева вершина
ребра ( , )a b та початкова вершина ребра ( , )b a . Отримаємо розбиття клітки 0s на дві клітки, при-
чому одна з них буде утворена шляхом ототожнення двох пар діаметрально протилежних вершин,
тобто стрічкою Мебіуса без ребра, яку замінимо 2-кліткою зменшивши рід ( )N , як показано на
рис. 23. Тим самим маємо суперечність умові про рід графа G . Отже припущення неправильне.
Доведення співвідношення 1 закінчено.
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
82 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
РИС. 23. Ряд з трьох карт ілюструє співвідношення 1 твердження 19
Доведення. Співвідношення 2. Припустимо, методом від протилежного, що деяким мінімаль-
ним вкладенням f графа G до неорієнтованої поверхні N із, принаймні, двома 2-ручками та од-
нією стрічкою Мебіуса, які розташовані на границі деякої клітки s , ( , )Gs S N f , є повторення або
двох пар вершин, або двох пар частин ребер e , 'e , де ( , )e a b , ' ( , )e c d , які розміщені на грани-
ці s як копії ребер ( )e , ( ')e , де ( ) ( ( ), ( )),e a b ( ') ( ( ), ( ))e c d . Тобто, на поверхні N дві
ручки містять по одному ребру ( )e чи ( ')e , де операція – ототожнення вершин та ребер на
границях кліток є оберненою до операції розбиття на клітки поверхні N мінімальним вкладенням
f графа G . Розглянемо простий шлях L , що лежить в середині клітки s і з’єднує середні точки
копій ребра e чи його частини та який стане негомотопним нулю простим циклом ( )L на повер-
хні N після операції – ототожнення копій ребер (частин) та вершин графа G . Видалимо цикл
( )L і ребро ( )e тим самим відріжемо звільнену ручку поверхні та розглянемо вкладення 'f ,
\' |G ef f , як звуження вкладення f на підграф \G e до неорієнтованої поверхні 'N роду ( ')N ,
( ') ( ) 2N N , причому ребро ( ') ( ( ), ( ))e c d буде вкладене на ручці 'h , так, що з одного
боку якого розташовано клітку 's з вершиною ( )a на границі 's , а з другого боку розташовано
клітку "s з вершиною ( )b на "s , де ( ') ' "e s s . Приклеїмо до цих кліток ' "s s стрічку
Мебіуса та вкладемо ребро '( ( ), ( ))f a b до ' "s s не перетинаючи '( ( '))f e . Тим самим отрима-
ємо вкладення графа G до поверхні "N роду ( ")N , ( ") ( ( ) 2) 1N N , яке суперечить спів-
відношенню 2. Отже припущення неправильне. Доведення співвідношення 2 закінчено (рис. 24).
РИС. 24. Ряд з чотирьох карт ілюструє співвідношення 2 твердження 19
Доведення. Співвідношення 3. Припустимо, методом від протилежного, що деяким мінімальним
вкладенням f графа G до неорієнтованої поверхні N із, принаймні, 2-ручкою R та стрічкою Ме-
біуса ,M три ребра e , 'e , "e розташовані на границях деяких 2-кліток 1 2,s s , де 1 2, ( , )Gs s S N f ,
де ( , )e a b , ' ( , )e c d , " ( , )e g h , які розміщені на границі 1s в порядку ( )e , ( ')e , ( ")e , а на
границі 2s в порядку ( )e , ( ")e ,
( ')e , де ( ) ( ( ), ( ))e a b , ( ') ( ( ), ( ))e c d ,
( ") ( ( ), ( ))e g h , де – операція ототожнення вершин та ребер на границях кліток, яка є обер-
неною до операції розбиття на клітки поверхні N мінімальним вкладенням f графа G . Тоді ребра
( )e , ( ')e з
1
1 2( )G s s мають розміщуватися на 2-ручці R та на M стрічці Мебіуса,
ПРО СТРУКТУРУ 9-ТИ ВЕРШИННИХ ГРАФІВ-ОБСТРУКЦІЙ ДЛЯ ПОВЕРХНІ КЛЕЙНА
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 83
на якій переставимо місцями кінцеві вершини (перевернемо ребро) ( )e . Розглянемо прості лан-
цюги 1 2,L L , які з’єднують середини ребер , 'e e на клітках 1 2,s s , відповідно, та утворюють про-
стий цикл Z в результаті операції ототожнення вершин та ребер на границях кліток 1 2,s s . Вида-
лимо ребра ( )e і ( ')e та отримаємо вільну від ребер 2-ручку R . Видалимо простий цикл Z , тоб-
то розріжемо 2-ручку R , причому не розділяємо поверхню N на дві частини. Отримаємо вкладен-
ня 'f , \{ , '}' |G e ef f , графа \{ , '}G e e до неорієнтованої поверхні 'N , утвореної з N шляхом вида-
лення ручки R , де ( ') ( ) 2N N . Оскільки таке вкладення є 2-клітковим, то розмістимо на
стрічці М ребро '( ")f e , яке разом з вершинами видаленого ребра 'e належатиме двом псевдокліт-
кам, на границях яких розділятимуть одна одну пари кінцевих вершин ребер , 'e e . Продовжимо
вкладення 'f на ребра , 'e e , які перехрещені на площинному диску, уникаючи перетину шляхом
розташування їх на стрічці М, де вже вкладено вершини ребра "e . Тим самим отримаємо супереч-
ність умові про мінімальність вкладення f графа G до неорієнтованої поверхні N , тобто припу-
щення неправильне. Доведення співвідношення 3 закінчено (рис. 25). Доведення твердження 19
закінчено.
РИС. 25. Ілюструє співвідношення 3 твердження 19
Твердження 20. Для довільного мінімального вкладення f простого графа G до орієнтованої
поверхні N не мають місця співвідношення твердження 19.
Доведення. В кожному із співвідношень твердження 19 є стрічка Мебіуса, тому для орієнтова-
ної поверхні N кожне з цих співвідношень не матиме місця.
Теорема. Кожен граф-обструкція H для 2N – неорієнтованої поверхні рода 2 задовольняє
співвідношенням.
1. Довільне ребро , ( , )u u a b розміщується на стрічці Мебіуса деяким мінімальним вкладен-
ням графа H в 3N та існує мінімальний по включенню проективно-площинний підграф K графа
\H u чи його частина, що задовольняє умові: 3 \ 2( ({ , }, ) 1) ( ({ , }, ) 2)K K ut a b N t a b N .
2. Існує найменша за включенням множина різних підграфів iK , яка покриває множину ребер
2-зв’язного графа ,H де K – локальний проективно-площинний підграф чи частинний підграф
графа \H e , гомеоморфний 5 \K e чи 3,3 \K e , де 5K , 3,3K графи Куратовського.
Доведення. Співвідношення 1 доводимо таким чином. Нехай u , ( , )u a b , довільне ребро гра-
фа-обструкції H для неорієнтованої поверхні 2N роду 2 та мінімальне вкладення ,f
2: \f H u N , яке розташовує кінцеві вершини ребра ( , )u a b на границях двох кліток 1 2,s s ,
2( , )i Hs S N f , 2 2( , ) \ ( )HS N f N f H , де 1 2,a s b s . Тоді це ребро не може з’єднувати два
підграфи графа-обструкції H та існуватиме підграф 5K графа-обструкції H гомеоморфний або
5K , або 3,3K , який вкладенням f розміщується на проективній площині із однією приклеєною
стрічкою Мебіуса так, що всі його вершини виходитимуть на границю однієї клітки, причому деякі
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
84 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
з подвійним доступом. Тоді ребро ( , )u a b буде розміщено на стрічці Мебіуса разом з, принаймні,
одним ребром, яке на проективній площині схрещене із u . Зазначимо, що 1 2s s , тобто матимемо
рівняння \ 2({ , }, ) 2H ut a b N , бо у разі однієї клітки 1 2s s було б можливо продовжити вкладення
шляхом розміщення ребра ( )f u в середину клітки 1s , що суперечитиме визначенню граф-
обструкції для неорієнтованої поверхні 2N роду 2. Тоді існуватиме найменший за включенням ло-
кально площинний підграф K графа \H u , який на неорієнтованій поверхні 2N містить всі вер-
шини, що виходять на границі кліток 1 2s s , тобто задовольняє рівності \ 2({ , }, ) 2H ut a b N . До-
визначивши вкладення f шляхом додавання відрізка [ , ]a b до 2-зв’язного підграфа ( )f K , мати-
мемо перетин принаймні одного ребра ( ')f u з [ , ]a b . Приклеїмо до 2N стрічку Мебіуса в місці пе-
ретину ребер ( ')f u та перевизначимо вкладення 2:f H u N шляхом розведення на стрічці Ме-
біуса ребра ( ')f u з ребром '( )f u . Тим самим отримаємо мінімальне вкладення 'f , 3' :f H N ,
яке роз-ташовує кінцеві вершини ребра ( , )u a b на границі однієї клітки, та рівність
3({ , }, ) 1Ht a b N . Доведення співвідношення 1 закінчено.
Доведення. Співвідношення 2 доводимо використовуючи вищенаведені позначення для виді-
лення локально площинних підграфів iK графа \H u , який задовольняє умові:
3( ({ , }, ) 1)Kit a b N \ 2( ({ , }, ) 2)
iK ut a b N . Розглянемо всі можливі випадки для графа \H u :
1) існує простий цикл ( )f z графа \H u , ( , )u a b , який містить вершини 1 2,a s b s ; 2) не іс-
нує простого циклу ( )f z графа \H u , який містив би вершини 1 2,a s b s .
Випадок 1. Циклом ( )f z буде простий цикл, який містить ребра з кінцевими вершинами
1 2,a s b s та входить до об’єднання границь тих кліток чи псевдокліток is , 2 \ ( )is N f H ,
1,2,...,i n , що утворюють ланцюжок з початком в 1s та кінцем в ns , 2ns s , а кожна наступна
клітка ланцюжка матиме принаймні одне спільне ребро із попередньою кліткою цього ланцюжка.
У виродженому випадку цей ланцюжок кліток складатиметься тільки з двох трикутних кліток чи
псевдокліток 1 2,s s . У графа \H u має існувати найменший за включенням локально площинний
підграф K , який задовольняє умові: 3 \ 2( ({ , }, ) 1) ( ({ , }, ) 2)K K ut a b N t a b N , бо інакше порушува-
тиметься умова про H як граф-обструкцію. Тобто мають бути або три ланцюги ненульової довжи-
ни, що належать границям кліток ланцюжка і мають спільну кінцеву вершину, або два схрещених
на площині діагональних відносно ( )f z ланцюги 1 2,L L ненульової довжини (один з них належа-
тиме до границь кліток ланцюжка, а інший не матиме спільних ребер із границею жодної клітки
ланцюжка), які парами своїх кінцевих вершин розділятимуть один одного та пару вершини ,a b на
( )f z . Тоді локально площинний підграф K матиме вигляд 1 2( )f z L L , тобто 4( )f K K , та
задовольнятиме умові \ 2({ , }, ) 2K ut a b N для довільного ребра ( , )u a b . У випадку, коли вершини
,a b є внутрішніми точками несуміжних ребер графа K , то граф 3,3( , )K a b K .
Випадок 2. Нехай не існує простого циклу ( )f z графа \H u , який містив би вершини
1 2,a s b s . Це означитиме, що видалене ребро ( , )u a b розірвало той простий цикл 'z графа
H , що за умови 2-зв’язності графа H проходив через вершини ,a b . Тоді має бути 2-зв’язний під-
граф 'H графа \H u , який має вершину a та простий ланцюг 'L , який задовольнятиме умові
' ' 'H L u z . Для 2-зв’язного підграфа 'H виконуватиметься наведений вище випадок 1.
Доведення для випадку 2 закінчено. Таким чином для кожного ребра u 2-зв’язного графа H
ПРО СТРУКТУРУ 9-ТИ ВЕРШИННИХ ГРАФІВ-ОБСТРУКЦІЙ ДЛЯ ПОВЕРХНІ КЛЕЙНА
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 85
є підграф iK , uKK i , тобто це локально площинний підграф K із добавленим ребром u ,
принаймні 5KuK чи 3,3KuK . Тоді об’єднання всіх таких iK покриває множину ребер
графа H . Доведення співвідношення 2 закінчено. Доведення теореми закінчено.
Наслідок 1. Граф-обструкція H для неорієнтованої поверхні роду 2 є φ-образом двох квазі-
зірок
11, 2,.., 1( )n n nkSt H ,
21, 2,.., 2( )m m mkSt H з центрами-підграфами iH , | |i ik H , , , 1,2i j i j ,
де квазізірка може не мати висячих ребер, а у випадку наявності висячих ребер кожна l -та висяча
вершина інцидентна nl висячим вершинам тих ребер, що приєднуються кінцевими вершинами до
'ml вершин підграфа jH , де 11,2,..,l k , 2' 1,2,..,l k , , , 1,2i j i j . Cаме ці кінцеві вершини ут-
ворюють множину точок приєднання з числом досяжності 2 відносно 2N та мають наступні
властивості для 2-зв’язного H :
а) кожна вершина центру iH з підмножини точок приєднання приєднана або висячим ребром
до однієї вершини підграфа jH , або двома висячими ребрами до кожної з кінцевих вершин деяко-
го ребра підграфа jH , або трьома висячими ребрами до кожної вершини підграфа 3K графа jH ,
де , , 1,2i j i j ;
б) кожне ребро підграфа iH чи jH є суттєвим при операції його видалення або відносно не-
орієнтованого роду ( )iH чи ( )jH , де , , 1,2i j i j , або відносно числа досяжності 2( , )
iH i jt X N
множини точок приєднання i jX , ( , )i j i jX X H H , квазізірки
11, 2,.., 1( )n n nkSt H до графа jH ,
де , , 1,2i j i j , або, як бокове ребро підграфа 3K , відносно числа багатосторонності
2( , )
iH i jms X N , множини точок приєднання i jX , ( , )i j i jX X H H , квазізірки
11, 2,.., 1( )n n nkSt H
до графа jH , де , , 1,2i j i j (рис. 26).
РИС. 26. На картах наведено приклад підграфа K графа H з теореми,
вкладеного до елементарного диска проективної площини
Висновок. Методом φ-перетворення графів досліджено структурні властивості 9-ти вершин-
них графів обструкцій для поверхні неорієнтованого роду 2, а саме: шляхом подання їх як -образу
кількох графів, гомеоморфних одному із графів Куратовського та принаймні одному площинному
чи проективно-площинному графу. Також наведено інші властивості характерні для вкладень скін-
чених графів до неорієнтованих поверхонь, що, на відміну від орієнтованих поверхонь, границі
кліток не містять повторних ребер.
Список літератури
1. Хоменко М.П. -пеpетвоpення гpафiв. Пpепp. ИМ АHУ. Киев, 1973. 383 с.
2. Хоменко М. П. Топологические аспекты теории графов. Пpепp. ИМ АHУ. Киев, 1970. 299 c.
3. Петpенюк В.I., Петpенюк Д.А., Шулінок І.С. Нова верхня межа орієнтованого роду склейки простих графів.
Теорія оптимальних рішень. 2018. С. 69–79. http://dspace.nbuv.gov.ua/handle/123456789/144974
http://dspace.nbuv.gov.ua/handle/123456789/144974
B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК
86 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
4. Cashy J. Irreducible graphs for the Klein bottle. Ph.D. Thesis, Ohio State University, 2000.
5. Mohar B., Thomassen C. Graphs on Surfaces. Johns Hopkins University Press, 2001.
6. Hur S. Тhe Кuratowski covering conjecture for graphs of order less than 10. Phd, Ohio State University, 2008.
https://etd.ohiolink.edu/rws_etd/send_file/send?accession=osu1209141894&disposition=inline
7. Петренюк В.І., Петренюк Д.А. Нова верхня межа неорієнтованого роду простого графа. Комп’ютерна мате-
матика. 2019. 1. С. 10–19. http://dspace.nbuv.gov.ua/handle/123456789/161928
Одержано 02.07.2020
Петренюк Володимир Ілліч,
кандидат фізико-математичних наук, доцент
Центральноукраїнського національного технічного університету, Кропивницький,
petrenjukvi@i.ua
Петренюк Дмитро Анатолійович,
кандидат фізико-математичних наук, старший науковий співробітник
Інституту кібернетики имені В.М. Глушкова НАН України, Київ.
guitar_player@ukr.net
UDC 519.85
V. Petrenjuk 1, D. Petrenjuk 2
About Structure of Graph Obstructions for Klein Surface with 9 Vertices
1 Central Ukrainian National Technical University, Kropyvnytskyi
2 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
1 Correspondence: petrenjukvi@i.u
The structure of the 9 vertex obstructive graphs for the nonorientable surface of the genus 2 is established
by the method of -transformations of the graphs. The problem of establishing the structural properties of 9
vertex obstruction graphs for the surface of the undirected genus 2 by the method of -transformation of graphs
is considered. The article has an introduction and 5 sections. The introduction contains the main definitions,
which are illustrated, to some extent, in Section 1, which provides several statements about their properties.
Sections 2 – 4 investigate the structural properties of 9 vertex obstruction graphs for an undirected surface by
presenting as a -image of several graphs homeomorphic to one of the Kuratovsky graphs and at least one pla-
nar or projective-planar graph. Section 5 contains a new version of the proof of the statement about the peculi-
arities of the minimal embeddings of finite graphs in nonorientable surfaces, namely, that, in contrast to
oriented surfaces, cell boundaries do not contain repeated edges.
Also in section 5 the other properties peculiar to embeddings of graphs to non-oriented surfaces and the
main result are given.
The main result is Theorem. Each obstruction graph H for a non-oriented surface N2 of genus 2 satisfies
the following.
1. An arbitrary edge u,u = (a,b) is placed on the Mebius strip by some minimal embedding of the graph H
in N3 and there exists a locally projective-planar subgraph K of the graph H \ u which satisfies the condition:
(tK({a,b},N3) = 1) (tK\u({a,b},N2) = 2), where tK({a,b},N) is the number of reachability of the set {a,b} on the
nonorientable surface N.
2. There exists the smallest inclusion of many different subgraphs Ki of a 2-connected graph H homeo-
morphic to the graph K+e, where K is a locally planar subgraph of the graph H (at least K+e is homemorphic
to K5 or K3,3), which covers the set of edges of the graph H.
Keywords: graph, Klein surface, graph structure, graph obstruction, non-oriented surface, Möbius strip.
https://etd.ohiolink.edu/rws_etd/send_file/send?accession=osu1209141894&disposition=inline
http://dspace.nbuv.gov.ua/handle/123456789/161928
mailto:petrenjukvi@i.ua
mailto:guitar_player@ukr.net
mailto:petrenjukvi@i.u
|