Верхня межа орієнтованого роду склейки простих графів

Уточнено верхню межу орієнтованого роду γ(G) простого графа G. Він є φ-образ двох не вироджених графів Gi без спільних ребер орієнтованого роду γ(Gi) при ототожненні пар точок (x1j, x2j) із множин точок приєднання Xi, j=1,2,..,|Xi|, де під точкою розумітимемо або вершину, або довільну точку ребра...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Теорія оптимальних рішень
Дата:	2018
Автори:	Петренюк, В.І., Петренюк, Д.А., Шулінок, І.Е.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2018
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/144974
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Верхня межа орієнтованого роду склейки простих графів / В.І. Петренюк, Д.А. Петренюк, І.Е. Шулінок // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 69-78. — Бібліогр.: 6 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-144974
record_format	dspace
spelling	Петренюк, В.І. Петренюк, Д.А. Шулінок, І.Е. 2019-01-12T17:13:09Z 2019-01-12T17:13:09Z 2018 Верхня межа орієнтованого роду склейки простих графів / В.І. Петренюк, Д.А. Петренюк, І.Е. Шулінок // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 69-78. — Бібліогр.: 6 назв. — укр. 2616-5619 https://nasplib.isofts.kiev.ua/handle/123456789/144974 519.1 Уточнено верхню межу орієнтованого роду γ(G) простого графа G. Він є φ-образ двох не вироджених графів Gi без спільних ребер орієнтованого роду γ(Gi) при ототожненні пар точок (x1j, x2j) із множин точок приєднання Xi, j=1,2,..,\|Xi\|, де під точкою розумітимемо або вершину, або довільну точку ребра графа G. Уточнена верхняя граница ориентированного рода γ(G) простого графа G. Он является φ-образом двух невырожденных графов Gi без общих ребер ориентированного рода γ(Gi) при отождествлении пар точек (x1j, x2j) из множеств точек присоединения Xi, j=1,2,..,\|Xi\|, где под точкой понимаем либо вершину, либо произвольную точку ребра графа G. Upper bound of oriented genus γ(G) of a simple graph G is estimated. The graph is a φ-image of two двух no-degenerate graphs Gi without common edges of orientable genus γ(Gi), with identifying pairs of points (x1j, x2j) from the set of joint points Xi, j=1,2,..,\|Xi\|, where a point is either a vertex or and arbitrary point of an edge of graph G. uk Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Верхня межа орієнтованого роду склейки простих графів Верхняя граница ориентированного рода склейки простых графов Upper bound of oriented genus of a simple graph gluing Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Верхня межа орієнтованого роду склейки простих графів
spellingShingle	Верхня межа орієнтованого роду склейки простих графів Петренюк, В.І. Петренюк, Д.А. Шулінок, І.Е.
title_short	Верхня межа орієнтованого роду склейки простих графів
title_full	Верхня межа орієнтованого роду склейки простих графів
title_fullStr	Верхня межа орієнтованого роду склейки простих графів
title_full_unstemmed	Верхня межа орієнтованого роду склейки простих графів
title_sort	верхня межа орієнтованого роду склейки простих графів
author	Петренюк, В.І. Петренюк, Д.А. Шулінок, І.Е.
author_facet	Петренюк, В.І. Петренюк, Д.А. Шулінок, І.Е.
publishDate	2018
language	Ukrainian
container_title	Теорія оптимальних рішень
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Верхняя граница ориентированного рода склейки простых графов Upper bound of oriented genus of a simple graph gluing
description	Уточнено верхню межу орієнтованого роду γ(G) простого графа G. Він є φ-образ двох не вироджених графів Gi без спільних ребер орієнтованого роду γ(Gi) при ототожненні пар точок (x1j, x2j) із множин точок приєднання Xi, j=1,2,..,\|Xi\|, де під точкою розумітимемо або вершину, або довільну точку ребра графа G. Уточнена верхняя граница ориентированного рода γ(G) простого графа G. Он является φ-образом двух невырожденных графов Gi без общих ребер ориентированного рода γ(Gi) при отождествлении пар точек (x1j, x2j) из множеств точек присоединения Xi, j=1,2,..,\|Xi\|, где под точкой понимаем либо вершину, либо произвольную точку ребра графа G. Upper bound of oriented genus γ(G) of a simple graph G is estimated. The graph is a φ-image of two двух no-degenerate graphs Gi without common edges of orientable genus γ(Gi), with identifying pairs of points (x1j, x2j) from the set of joint points Xi, j=1,2,..,\|Xi\|, where a point is either a vertex or and arbitrary point of an edge of graph G.
issn	2616-5619
url	https://nasplib.isofts.kiev.ua/handle/123456789/144974
citation_txt	Верхня межа орієнтованого роду склейки простих графів / В.І. Петренюк, Д.А. Петренюк, І.Е. Шулінок // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 69-78. — Бібліогр.: 6 назв. — укр.
work_keys_str_mv	AT petrenûkví verhnâmežaoríêntovanogoroduskleikiprostihgrafív AT petrenûkda verhnâmežaoríêntovanogoroduskleikiprostihgrafív AT šulínokíe verhnâmežaoríêntovanogoroduskleikiprostihgrafív AT petrenûkví verhnââgranicaorientirovannogorodaskleikiprostyhgrafov AT petrenûkda verhnââgranicaorientirovannogorodaskleikiprostyhgrafov AT šulínokíe verhnââgranicaorientirovannogorodaskleikiprostyhgrafov AT petrenûkví upperboundoforientedgenusofasimplegraphgluing AT petrenûkda upperboundoforientedgenusofasimplegraphgluing AT šulínokíe upperboundoforientedgenusofasimplegraphgluing
first_indexed	2025-11-26T08:26:40Z
last_indexed	2025-11-26T08:26:40Z
_version_	1850618475581538304
fulltext	ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 69 ТЕОРIЯ ОПТИМАЛЬНИХ РIШЕНЬ Уточнено верхню межу орієнтова- ного роду γ( )G простого графа .G Він є φ-образ двох не вироджених графів iG без спільних ребер орієн- тованого роду ( )iG при ототож- ненні пар точок 1 2( , )j jx x із множин точок приєднання , 1,2,.., \| \|, i i j   де під точкою розумітимемо або вершину, або довільну точку ребра графа .G  B.I. Петренюк, Д.А. Петренюк, І.Е. Шулінок, 2018 УДК 519.1 B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК, І.Е. ШУЛІНОК ВЕРХНЯ МЕЖА ОРІЄНТОВАНОГО РОДУ СКЛЕЙКИ ПРОСТИХ ГРАФІВ Вступ. Основні позначення взяті з [1 – 3]. B роботі [4] отриманo наступний резуль- тат для площинних графів :G якщо граф  – φ-образ графа G та простої зірки 0( )mSt a з центром 0a та m висячими ребрами з кінцевими вершинами ,ia що попарно ототожнюються з точками мно- жини X з числом досяжності ,t 3,t  то     1,G t      де   0 G ,  ,G     0,1 , змінна  описує де- які структурні властивості множини точок X, розташованої на границях кліток гра- ней графа .G Задача: 1) узагальнення цьо- го результату [4] для не площинних неорі- єнтованих графів G та квазізірки з цент- ром-графом без кратних ребер та дуг, що містять множину точок  iз числом до- сяжності ,t 0;t  2) узагальнення  і  – характеристик множини  наведених да- лі та показаних на рис. 1 для орієнтовано- го роду та на рис. 2 – для неорієнтованого роду. Нехай S – 2 – многовид без країв. Визначення 1. Нехай задане вкладення ,f : ,f G S графа G в ,S яке реалізує ,t   ,Gt t  де   \ ( ),GS S f G     1. t G iS s  Будемо говорити, що мно- жина  матиме характеристику ( , ),G X f ( , ) ,G X f   1,  якщо існує  трійок кліток   3 1іs з множини  GS , на границях яких множина  розміщу- ється довільним чином, та кожна з яких B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК, І.Е. ШУЛІНОК 70 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 задовольняє для всіх ji  співвідношенню 0 i jG s s      , , 1, 2, 3,i j  причому 0 1 2 1{ }G s s a   і 0 2 3 2{ },G s s a   0 1 3 3{ },G s s a   та породжує наймен- ший по включенню підграф 'G графа ,G яке реалізує ,t   ,Gt t  де     1 , t G iS s  можливо вироджений в точку, який містить точки   3 1ia попар- ного перетину границь кліток   3 1 .іs Множина  матиме характеристику ( ),G X якщо ),(max)( fXX GG  , де максимум береться по всім вкладенням f , SGf : , що реалізують   ,Gt t    0,G   ,G     0, 1 ,  – описує деякі структурні властивості множини точок X, що розташована на границях гра- ней графа G. Визначення 2. Нехай задане вкладення ,f : ,f G S графа G в ,S   \ ( ),GS S f G  та виконується рівність ( ) 0.G X  Будемо говорити, що мно- жина  матиме характеристику ( , ),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  . На границях },,{ kjі sss  множина  розміщується довільним чином, якщо не містить точок ребер 1 1( , ),a b 2 2( , )a b та особливим чином (без точок множини Х на )},(),,{(),(\ 10120221 aaaaaaLs j  ), якщо містить принаймні точку цих ре- бер. Також існуватимуть клітка 0s та, можливо, клітка 00s . 1 2( , )L a a ненульової довжини із кінцевими вершинами 21,aa спільно із js і два простих ланцюги, можливо вироджених в точку, 1 1 12( , ),L a a ),( 2221 aaL спільними з is та ,ks від- повідно, та ребро 12 22( , ).а а Клітка 00s ,  00 0( \ ( )) \ ( { }),Gs S f G S s   має грани- цю яка містить простий ланцюг 10 20( , )L a a ненульової довжини із кінцевими вер- шинами 10 20,a a спільно із .js Множина  матиме характеристику ( ),G X якщо ),(max)( fXX GG  , де максимум береться по всім вкладенням ,f : ,f G S що реалізують   ttG  та ( ) 0.G X  Твердження 1. Нехай на множині  GS задано відношення інцидентності наявністю, принаймні однієї спільної точки на границях двох кліток. Мають міс- це наступні співвідношення: 1) для S – орієнтованого роду визначення 1 вико- нуються в загальному випадку, а для визначення 2 є два варіанти: а) множина Х не має точок на жодному із ребер, які є спільними для двох різних пар кліток включають другу клітку, б) множина Х не має точок на тій частині границі дру- гої клітки, що має спільні ребра з двома іншими, та не належить до кожної з них та до 0 00;s s  2) для S – неорієнтованого роду визначення 1 не виконуються ВЕРХНЯ МЕЖА ОРІЄНТОВАНОГО РОДУ СКЛЕЙКИ ПРОСТИХ ГРАФІВ ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 71 в загальному випадку, а виконується тільки тоді, коли точки множини X відсутні на трьох ребрах ),( ji aa трикутника ',G а ланцюжкова кліткова структура не за- довольняє визначенню 2 в загальному випадку, але задовольняє тоді, коли клітка 0s має на 0s тільки одне ребро графа ,G що не належить до 1,is G  1, 2, 3;i  3)           2 2 2. 2 2 G G G G G t t t                         Доведення. На торі зіркову та трикутну кліткову структуру, що задовольняє визначенню 1, описуватиме 1,  , як показано на рис. 1, перший ряд; другий ряд описує ланцюжкову структуру із 1 . На проективній площині зіркову структуру описуватиме 1,  що показана на першій карті верхнього ряду рис. 2, на інших парах карт цього ряду показано, що трикутна кліткова структура, як узагальнена незіркова структура, не задо- вольняє визначенню 1 навіть у випадку, коли три ребра ),( ji aa трикутника 'G не входять до L= 3 1 ,i i s   а ланцюжкова кліткова структура задовольняє визначенню 2 тільки тоді, коли внутрішніми гранями будуть тільки клітки з 3 0}{  iis , на 0s є ребро, можливо 1-підрозділене, графа G , що не належить до L. Оскільки 2-многовид S – орієнтованого роду ( ),S то являтиме собою тор із приклеєною ( ) 1S  2-ручкою. Співвідношення 1 випливає з того, що на торі перетворення зіркової та циклічної кліткових структур описуватиме перший ряд рис. 1 (для 1 ), а другий ряд цього ж рисунка для перетворення на торі лан- цюжкової структури із 1.  2-многовид S – неорієнтованого роду ( )S явля- тиме собою проективну площину із приклеєними лентами Мебіуса у кількості ( ) 1.S  Співвідношення 2 випливає з того, що на проективній площині зіркову структуру 1 описуватимуть перші дві карти верхнього ряду рис. 2, а на двох інших парах карт цього ряду показано, що циклічна кліткова структура задо- вольняє визначенню 1 тільки тоді, коли три ребра ),( ji aa трикутника 'G не вхо- дять до 3 1 ,i i s   то )(),( 3 1 3 1,, Xsaaf i i jiji ji    , а ланцюжкова кліткова структура задовольняє визначенню 2 тільки тоді, коли внутрішніх граней графа G окрім кліток з множини 3 0}{  iis не буде, а на 0s є ребро графа, можливо 1-підрозді- лене, графа ,G що не належить до 3 1 ,i i s   коли клітка s має на s тільки одне ребро графа ,G яке не належить до 3 1 ,i i s   та на спільних ребрах немає точок множини Х. Доведення співвідношень 1) та 2) закінчене. B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК, І.Е. ШУЛІНОК 72 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 РИС. 1 РИС. 2 Наслідок. Перетворення множини кліток-граней графа ,G вкладеного до 2-многовида ,S виконані за визначеннями 1 та 2, трансформують елементи з )(XSG не змінюючи сусідні з ними клітки; клітки задіяні в деяких випадках. Алгоритм_О Вхід. До 2-многовида S орієнтованого роду вкладено граф G мінімальним вкладенням f , SGf : , що реалізує   ttG  та   G . Занумеруємо пе- рші три клітки з  GS , що задовольняють визначенню 1, як підмножину   3 1 .іs Вважатимемо заданими функції (М) та  (М), які визначають характеристики , ,  відповідно, для М – множини кліток, впорядкованої відношенням суміж- ності на множині границь кліток з М. Крок 0. Якщо 0,  то переходимо до кроку 3, інакше, доки 0 виконува- ти циклічно наступні дії: початок циклу 1. ВЕРХНЯ МЕЖА ОРІЄНТОВАНОГО РОДУ СКЛЕЙКИ ПРОСТИХ ГРАФІВ ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 73 Крок 1. Для  GS використання характеристики  для орієнтованого роду означає приклеювання нової 2-ручки h на заміну трьох клітин-граней   3 1іs із границями, що мають, принаймні, одну спільну вершину чи вони попарно ма- ють спільні вершини, на нову клітку-грань s поверхні на 1 більшого роду, що має границею 3 1 ,іs s   : .S S h  Крок 2.       3 1 : ( \ ) { };G G іS S s s    : функція_ ( ( )),GS    1 :  ; пере- нумеруємо всі елементи нової множини  GS так, щоб перші три клітки з  GS , для яких має місце визначення 1, мали номери 1, 2, 3; кінець циклу 1. Крок 3. : функція_ ( ( )),GS X   де  GS побудована циклом 1 множина кліток. Якщо 0,  то перенумеруємо клітки з побудованої вищенаведеним циклом множини кліток  GS , що задовольняють визначенню 2, як  3 1іs та 0s . Якщо 0 , то переходимо до кроку 6, інакше, доки 0 виконувати на- ступні дії: початок циклу 2. Крок 4. Для  GS використання характеристики  для орієнтованого роду означає приклеювання нової 2-ручки h на заміну трьох клітин-граней   3 1іs із границями, де 2s одна з трьох має два спільні ребра з двома іншими, та четвер- тої клітки 0s ,   GSGfSs \))(\(0 на нову клітку-грань s поверхні на 1 біль- шого роду, що має границею Rss і \ 3 1  , де множина R складена, або з двох попарно спільних ребер без точок з множини ,X або з тієї частини границі 2,s що не належить до границь 021 sss  та без точок з множини ;X ( ) : ( ) 1.S S    Крок 5.       3 1 : ( \ ) { };G G іS S s s    : функція_ ( ( ))GS    : 1.   Якщо 0,  то перенумеруємо всі елементи нової множини  GS так, щоб три клітки   3 1іs та четверта 0,s для яких має місце визначення 2, мали номери 1, 2, 3. Кінець циклу 2. Крок 6. Виводимо  GS та «Множина Х розташована на границях кліток- граней з множини  GS , перетвореної до нульових характеристик , ,  2-многовида орієнтованого роду )(S », кінець алгоритму. Твердження 2. Алгоритм_О коректно перетворює 2-многовид S та вкла- дення SGf : графа G в ,S де ( ) ( ),G S   в 2-многовид 'S та вкладення ':' SGf  графа G в ',S де ( ') ( ),S S   шляхом використання характеристик , ,  одна з яких має бути нульовою, множини точок X графа G та має поліномі- альну часову складність. B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК, І.Е. ШУЛІНОК 74 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 Доведення. Алгоритм перетворення орієнтованого 2-многовида S із вкладе- ним графом G в орієнтований 2-многовид ',S де ( ') ( ),S S   шляхом приклею- вання нових 2-ручок до S спирається на використання характеристики  мно- жини точок X графа G. Вважатимемо, що ручка h приклеєна до кліток  fGSss ,",'  і позначатимемо її  ', " ,h s s якщо задано  – перетворення ' в такий спосіб:       ' ' " \ , , ,s s h            де ,   – такі регулярні двок- літки, що задовольняють ', ", ' " .s s s s            Вважатимемо зада- ними функції_(М) та  (М), які визначають характеристики , ,  відповідно, на множини кліток М, що впорядкована відношенням суміжності заданим на множині границь кліток з М, то якщо границі двох кліток мають принаймні спільну точку, то ці клітки суміжні. Нехай до 2-многовиду S орієнтованого роду )(G вкладено граф G вкладенням ,f : ,f G S що реалізує   ttG  та   .G    Занумеруємо перші три клітки з  GS , що задовольняють визначен- ню 1, як підмножину   3 1іs та позначимо 'G найменший по включенню підграф графа ,G можливо вироджений у точку, який містить точки   3 1ia попарного пе- ретину границь кліток   3 1,іs причому }{ 121 0 assG  , }{ 232 0 assG  , }{ 331 0 assG  . Розглянемо плаский диск d з центром в 1a та нескінченно малим радіусом , який своєю границею перетинатиме ребра підграфа ',G що інциденті вершини 1a , у внутрішніх точках ja1 , де 1, 2, ... .j k Розщепимо кож- ну вершину ja1 на ' 1 ,ja ' 2 ,ja де 1,2, ...j k степеня 2. Цим розіб’ємо підграф 'G на частини ' ,iG 1, 2,i  де ' 1G містить ' 1 ja та всі ребра ),( ' 11 jaa , ' 2G містить ' 2 ja . Відображенням  перевернемо на 180 підграф )( ' 1Gf як множину образів ребер на поверхні, симетрично навколо вісі симетрії, яка є простим ланцюгом 2 3( , ),L a a що проходить через точки 2,a 3a та задовольняє умові: ' 2 3( )f G s  3 2 3( ') ( , ).f G s L a a   В результаті отримаємо підграф ' 2( )f G вкладений до 3,s де 333 sss  . Відображенням ' вигнемо за часовою стрілкою на 180 всі ви- сячі ребра інциденті ' 2 ja , де 1, 2,... ,j k не змінюючи порядок слідування, і роз- містимо їхні висячі вершини на лівій частині границі регулярної підклітки , де )(\' ' 23 Gfs  . В підграфі )( ' 2Gf вкладеному до 1 2 ,s s де 3 3 3,s s s  відо- браженням '' поміняємо місцями ребра в парах виду ' 1 1( , ),ja a ' 1( 1) 1( , )k ja a  для всіх ,j 1, 2,... ,j k та за часовою стрілкою розмістимо на правій частині гра- ниці регулярної підклітки ', де )(\)('' ' 121 Gfss  . Ототожнимо, за часовою ВЕРХНЯ МЕЖА ОРІЄНТОВАНОГО РОДУ СКЛЕЙКИ ПРОСТИХ ГРАФІВ ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 75 стрілкою, пари вершин ),( ' 2 ' 1 jj aa у внутрішню точку ' ja деякого j-го ребра ' ' ' 1 2( , , ),j j ja a a для всіх j, 1, 2,... .j k Приклеєна ручка h до кліток 3' ,s s 1 2" ,s s s   ', " , ' ,s s S G f позначена  ', " ,h s s матиме вкладені відображенням ''' склеєні половинки ребра ' ' ' 1 2'' ' (( , , )),j j jf a a a   які розрізають її на клітки, де 1, 2,... .j k В результаті суперпозиції ''' '' ' f    вищенаведених відображень отримаємо вкладення ',f ' : ',f G S ' ''' '' ' ,f f     графа G до 2-многовиду 'S орієнтованого роду ( ) 1,G  причому  ' , 'S G f  =  ',' fGS =      k j jjj aaafsshsssfGS 1 ' 2 '' 1321 ),,('\)",'(}),,{\,( , тобто ті ж самі клітки, тільки замість 321 ,, sss буде клітка ,s ' ' ' 1 2 1 ( ', ") \ '( , , ), k j j j j s h s s f a a a    така, що 3 1 .i i s s     Крім цього множина )(' Xf на 'S буде розміщуватися на границях 2)( XtG та матиме характеристику  G . Тим самим виконані всі дії однієї ітерації циклу 1 алгоритма_О. Нехай до 2-многовиду S орієнтованого роду ( )G вкладено граф G вкладенням ,f : ,f G S що реалізує   ,Gt t    0G   та   ,G    0.  Перші три з чотирьох кліток з множини  GS , що задо- вольняють визначенню 2, утворюють підмножину   3 1,іs а четверта 0.s Для  GS  використання характеристики  для орієнтованого роду означає прик- леювання нової 2-ручки ,h  1 0,h h s s чи  1 00, ,h h s s на заміну чотирьох кліток- граней   3 1 ,іs 0,s де 1s одна з трьох має два спільні ребра ie з 3 2,s s та клітки 0,s  0 ( \ ( )) \ ,Gs S f G S  на нову клітку-грань s з границею 3 1 \ ,іs s R   де мно- жина R матиме два наступні варіанти складання: 1) якщо  1 0, ,h h s s то R є тією частиною границі 1,s що не належить до границь 0s та без точок з множини }{\ 21 eeX  ; 2) якщо  00 0,h h s s (за умови існування такої клітки 00,s що множина точок )()( 10100 ssss  містить кінцеві вершини обох ребер ie ), то 1 2R e e  і ребра ie не містять точок з множини 1 2\{ },X e e  де 1 2 1,e s s  2 1 3.e s s  В кожному з цих випадків на приклеєній 2-ручці розміщуються ребра ie вкладенням ',f ' : ',f G S 2 2 2 2' \| \{ , } \| \{ , },f G e e f G e e графа G до 2-многовиду 'S орієнтованого роду ( ) 1,G  причому множина B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК, І.Е. ШУЛІНОК 76 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17  ' , 'S G f для варіанту 2) матиме вид   )),('\),((}){\,( 1 2100000 3 0    k ji i eefsshssfGS  , для варіанту 1) є   3 1 0 1 2 10 ( , \ { }) ( ( , ) \ '( , )). k i ji S G f s h s s f e e    Тим самим всі дії однієї ітерації циклу 2 алгоритму_0 виконані. Кількість ітерацій в обох циклах дорів- нюватиме     GG . Оскільки       2 GGG t і  Gt не пере- вищує числа кліток – граней графа G орієнтованого роду, вкладеного до 2-многовиду S роду ( ),G то алгоритм рекурсивно перетворюватиме множину кліток поки не отримає перетворену множину кліток-граней із нульовими ха- рактеристиками , .  Число ітерацій обох циклів не перевищуватиме 0 12(2 2 ( ) \| \| \| \|),G G G    тобто матиме поліноміальну часову складність. Тверджен- ня 2 доведено. Теорема. Якщо задано наступне φ-перетворення зв’язних графів iG та )( 2GStm орієнтованого роду ( ) :iG 1 2 1 2 1 1 : ( ( ), ( ) ( ,{ } ), m m m j j j j G St G x x G a       де )( 2GStm – квазізірка з центром 2G та кількома ребрами-променями, що суміжні вершинам з множини 2 ,i i множина точок графа ,iG 1{ } ,m i ijx  матиме характеристики it . , ,i i  то     2 1 1 ( ) 4 ,i i i i i G G t k st             де 1 1 1 1 ( , ), t j j st st X G      1 1 21 ),(44 t j jj XXkk , stk 4 – число 2-ручок приклеєних до клітки s з множини )(\ 11 Gfr , 04  stk f – мінімальне вкладення 11: rGf  ,   1 ( ),i i i i ir G t       із st – стороннім доступом до тих точок приєднання на границі s клітці ,s до якої приклеєно 2r 2-ручки і вкладено граф 2G , що при ототодженні пар точок приєднання ),( 21 jj xx породжують 4k різних підграфів гомеоморфних 4 2,3, .K K Наслідок. Нехай * 1 2 1 2 1 1 : ( ( ), ( ) ( ,{ } ) m m m j j j j G St G x x G a       та виконується умова теореми 1 і рівності: 0, 0,i i    0s , mtt  11 . Тоді     2 2 1 2i i G G m m        . Доведення випливатиме із наведеної в теоремі 1 нерівності та умови mti  за якою всі 0, 0,i i    0,s  а число 4k є числом всіх різних пар пере- хрещених ребер на множині всіх висячих ребер квазізірки 2( ),mSt G то     2 1 2 2 ( 1).i i G G k k k         ВЕРХНЯ МЕЖА ОРІЄНТОВАНОГО РОДУ СКЛЕЙКИ ПРОСТИХ ГРАФІВ ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 77 На рис. 3 на першій карті показано вкладення в 2-тор графа 1H із 4 0,k st  на другій карті вкладення графа 4G із 4 0,k  1st в 2-тор, відповідно, на третій карті вкладення в тор графа eGG \44  із 4 2,k st  четверта та п’ята карти – вкладення в 2-тор графів 8G із 4 0, 2,k st  14G із 4 0, 2,k st  відповідно. РИС. 3 Приклад. Точна верхня оцінка роду та роль двостороннього доступу видні на графі G з другої карти рис. 3, де 3,31 KG  , 32 KG  , 2m , 121  tt , 0 ii , )},3(),,3(),,2(),,2(),,1(),,1{()( 1 32 1 2 bababaKGSt  , 2}),({1 bast , 02 st , 24 k , тоді   1 G , та на третій карті рис. 3, де 51 KG  , 32 KG  , 2m , )},3(),,3(),,2(),,2(),,1(),,1{()( 1 32 1 2 bababaKGSt  , 121  tt , 0 ii , 1}),({1 bast , 0}),({2 bast , 24 k , тоді   2 G . В.И. Петренюк, Д.А. Петренюк, И.Э. Шулинок ВЕРХНЯЯ ГРАНИЦА ОРИЕНТИРОВАННОГО РОДА СКЛЕЙКИ ПРОСТЫХ ГРАФОВ Уточнена верхняя граница ориентированного рода ( )G простого графа .G Он является φ-образом двух невырожденных графов iG без общих ребер ориентированного рода )( iG при отождествлении пар точек ),( 21 jj xx из множеств точек присоединения Xj, \|\|,..,2,1 ij  , где под точкой понимаем либо вершину, либо произвольную точку ребра графа .G V.I. Petrenjuk, D.A. Petrenjuk, I.E. Shulinok UPPER BOUND OF ORIENTED GENUS OF A SIMPLE GRAPH GLUING Upper bound of oriented genus )(G of a simple graph G is estimated. The graph is a φ-image of two двух no-degenerate graphs iG without common edges of orientable genus, with identifying pairs of points ),( 21 jj xx from the set of joint points Xj, \|\|,..,2,1 ij  , where a point is either a vertex or and arbitrary point of an edge of graph .G B.I. ПЕТРЕНЮК, Д.А. ПЕТРЕНЮК, І.Е. ШУЛІНОК 78 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 Список літератури 1. Хоменко М.П. -пеpетвоpення гpафiв. Киев, 1973. (Пpепpинт ІМ АHУ 73). 2. Хоменко М. П. Топологические аспекты теории графов. Киев, 1970. (Пpепpинт ИМ АHУ 70). 3. Хоменко H.П. Остpовеpхий Е.Б. Существенные элементы и pод гpафа. Киев, 1972. (Пpепpинт «Минимальные вложения гpафов» ИМ АHУ 72). 4. Петpенюк В.I. Об оценке pода специальних гpафов. Деп. pукопись в УкpHИИТИ № 2259-Ук86 22.09.1986. 5. Петpенюк В.I. О стpуктуpе плоских гpафов с заданным числом достижимости некоторого множества точек. Деп. pукопис в УкpHИИТИ N 2245-Ук86 22.09.1986. 6. Bodendiek R., Wagner K. A characterization of the minimal basis of the torus. Combinato- rica 6, 3, 1986. P. 245 – 260. Одержано 23.03.2018

Верхня межа орієнтованого роду склейки простих графів

Репозитарії

Схожі ресурси