Структура площинних графів із множиною точок, досяжною на торі. Частина I.
Вивчення структури площинних графів, що мають певну множину точок X , таку, що tG (X) > 1 і досяжну на торi δ1 , є метою статті. Изучение структуры плоскостных графов, которые имеют определенное множество точек Х, такое, что tG (X) > 1 i и достижимое на торе δ1 , является целью этой статьи....
Saved in:
| Date: | 2008 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/7158 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Структура площинних графів із множиною точок, досяжною на торі. Частина I. / В.І. Петренюк // Штучний інтелект. — 2008. — № 3. — С. 720-726. — Бібліогр.: 6 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859903522592522240 |
|---|---|
| author | Петренюк, В.І. |
| author_facet | Петренюк, В.І. |
| citation_txt | Структура площинних графів із множиною точок, досяжною на торі. Частина I. / В.І. Петренюк // Штучний інтелект. — 2008. — № 3. — С. 720-726. — Бібліогр.: 6 назв. — укр. |
| collection | DSpace DC |
| description | Вивчення структури площинних графів, що мають певну множину точок X , таку, що tG (X) > 1 і досяжну на торi δ1 , є метою статті.
Изучение структуры плоскостных графов, которые имеют определенное множество точек Х, такое, что tG (X) > 1 i и достижимое на торе δ1 , является целью этой статьи.
|
| first_indexed | 2025-12-07T15:58:55Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 3’2008 720
8П
УДК 519.1
В.І. Петренюк
Кiровоградський національний технiчний унiверситет, м. Кіровоград, Україна
Структура площинних графів із множиною
точок, досяжною на торі. Частина I.
Вивчення структури площинних графів, що мають певну множину точок ,X таку, що ( ) 1Gt X >
і досяжну на торi 1,δ є метою статті.
Вступ
Розглянемо задачу побудови скінченного простого графа G, G = (V,E) із зада-
ними наперед родом P та числом досяжності R множини вершин, де P, R > 0. У світлі
теорії мінорів Сеймура та Робертсона, яка спирається на теорему, за якою для зада-
ного графа із нескінченної множини скінченних графів знайдеться інший граф, що
буде мінором заданого графа. Відзначимо, що мінор означатиме результат виконання
операцій стягування в точку чи видалення певної послідовності ребер скінченного
простого графа G доти, доки його сутність пов’язана із поставленою задачею. А саме
для випадку нашої задачі із параметрами P = 1, R = 1 такими є графи Куратовського-
Понтрягіна К3,3 та К5. Згідно з [6] наш спосіб побудови полягатиме в заміні деяких
ребер ui (чи їхньої частини) графа G’, гомеоморфного К3,3 чи К5, на графи К2,3 та К4,
якi приєднуються до графа G\ui, де i = 1,2,...m, шляхом ототожнення граничних
вершин (чи двох внутрішніх точок) довільного ребра ui із двома заданими верши-
нами графів К2,3 чи К4. Точніше будемо розглядати такий спосіб приєднання як одне
ϕ-перетворення графів G’ та H на граф G, де H = К2,3 чи H = К4, визначене за двома
точками, розуміючи під точкою або кінцеву вершину ребра, або внутрішню точку ребра.
Матимемо твердження: якщо площинний граф G, отриманий зазначеним вище способом,
то число досяжності множини вершин не перевищуватиме m + 1.
Основна частина
Основні визначення та позначення взятi із [ ] [ ]1 , 2 .
Визначення 1. Позначимо через ( )δ,GF множину усіх неiзоморфних 2-кліткових
вкладень δ→Gff :, графа G в 2-многовид .δ Будемо говорити, що вiдносно
вкладення ( )δ,, GFff ∈ множина ,X складена з точок графа ,G має число досяжностi
( )fXtG ′, , де ( ) tfXtG ′=′, , якщо існує найменша за включенням пiдмножина { } t
is ′
1
множини ( )fG,δ , що задовольняє умові:
( )( ) ( )( )( ) ( )( ) ( ) ( )
t
i i i i i i
i 1
i, j X i j, i, j 1 1 t X X, X f X ds & f X f X .
′
=
′∀ ∃ ≠ = ⊂ ≠ ∅ ⊂ ⊆
∑
Структура площинних графів із множиною точок, досяжною на торі...
«Штучний інтелект» 3’2008 721
8П
Визначення 2. Будемо говорити, що множина X має на δ число досяжності
( )δ,XtG , якщо виконується умова: ( ) ( )fXtXt GG ,min, =δ , де f∀ , ( )δ,GFf ∈ ,
причому вкладення ,f при якому досягатиметься мінімум, назвемо вкладенням, ре-
алізуючим число ( )δ,XtG . Множина X зветься досяжною на δ , якщо виконується рів-
ність ( ) 1, =δXtG .
Позначення 1. Позначимо через найменшу по включенню підмножину { } t
is 1
множини ( )fG,δ , що задовольняє умовi визначення 1, де вкладення f реалізує ,t
( )δ,Xtt G= .
Надалі будемо вважати, що G – блок, а вкладення 0:, δ→Gff реалізує число
досяжностi ( )XtG , де ( ) tXtG = , ( )XGθ – характеристика множини ,X наведена в [ ]3 .
Вважатимемо, що ( ) 0=XGθ . Через 0s позначимо зовнiшню грань графа ( ).f G′
Будемо позначати через 1:, δ→Gff таке вкладення, при якому множина X
досяжна на торi 1δ .
Зауваження 1. Будемо позначати через ,a b замкнутi кривi тора, не гомотопнi 0, та
будемо називати ці геодезичні кривi тора aмеридіаном тора, b – паралеллю тора; від-
ношення гомотопiї позначимо ~.
Визначення 3. Будемо позначати через jiHij <>, , найменший за включенням
пiдгpаф графа ,G що мiстить jiUdsds , де ( )fGss ji ,, δ∈ , та частинний підграф ,H ′
стягнутий вiдносно HX ′ до наступних п’яти графів, де jjii dsXXdsXX ∩=∩= , .
1. 3,2K , у якого вершини степені 2 мають своїми прообразами точки ix ′ , що
задовольняють відношенню: ( )( ) { }( ) { }( )33
1 1
, & .i k i i jk k i j x X x X UX′ ′
∀ = ∩ ≠ ∅ ⊆
2. ( )1
4K , де ( )
4
1
4 KK = , у якого точки 21, yy належать несуміжним ребрам, мають
прообразами 1 2, .i jx X x X∈ ∈
3. 4 ,K усi вершини якого мають своїми прообразами точки ix ′ , ( )411=′i , якi за-
довольняють вiдношенню: ( )( ) { }( ) { }( )4 4
1 1
, & .i k i i jk k i j x X x X UX′ ′
∀ <> ∩ ≠ ∅ ⊆
4. *4K -φ – образ графа ( )4 5 0 ,z St y+ отриманий в результаті φ-перетворення:
( ) ( ) { }( )4 4* *
4 0 i i 4 1 1
i 1
ц z St y , a y K , a ,
=
+ + ==
∑
де 0
4z – простий цикл довжини 4, { } ( )0
4
14 , yStaz i= – зiрка iз центром в точцi y0,
( ) { }4
004 iyySt = . Двi точки графа ( ) ( )030011
*
4 *,*, yayyayK ∈∈ мають прообразами 11, yx ,
якi задовольняють вiдношенню: ( ) { }( )2
1
, , .i kk k i j x X∀ = ∩ ≠ ∅
5. ( )* 1
4 ,K отриманого шляхом наступного φ -перетворення:
( ) ( ) ( ) { }( )2
1
**
k
1*
4
2
1k
k2
*
k242
*
1 a,Kaa,aaKц ==
+∪ ∑
=
i такого, що його вершини *
3
*
1 ,aa мають своїми прообразами точки 2,1 xx , вiдповiдно,
задовольняють спiввiдношенню: ( ) { }( )2
1
, , .i kk k i j x X′∀ = ∩ ≠ ∅
Петренюк В.І.
«Искусственный интеллект» 3’2008 722
8П
Лема 1. Нехай X – скінченна множина точок площинного гpафа G , де
( ) ( ) { }t
iGGG sSXttXt 1,0,1, >>= θ , задане вкладення 1:, δ→Gff pеалізує ( )1,δXtG ,
{ }ijHM = – множина пiдгpафiв ijH гpафа ,G якi задовольняють визначенню 3. Якщо
множина X досяжна на 1,δ то мають мiсце наступнi твеpдження:
а) кожний пiдгpаф ,H H M∈ гpафа G мiстить пpостий цикл ,z такий, що ( )zf –
замкнута кpива, не гомотопна 0;
б) якщо кожен пiдгpаф MHH ∈, має ту властивість, що довiльний його пpостий
цикл z має образ ( )f z або гомотопний 0, або гомотопний a ( a – геодезична кpива
тора), то тодi icнyє пpостий цикл z′ гpафа ,G такий, що:
1) z′ не входить в ,ijUH де ;ijH M∀ ∈
2) ( )zf ′ гомотопний b-дpугiй геодезичнiй кривій тоpа;
в) якщо icнують пiдгpафи HH ′′′, з множини ∅=′′∩′ HHM , , то кожний пpостий
цикл цих пiдгpафiв гpафа G має обpаз, гомотопний або 0, або однiй i тiй же
геодезичнiй кpивiй тоpа;
г) якщо існують пpостi цикли iz гpафа iH , де { }3
1
1, 2,3, ,ii H M= ⊆ якi задовольняють
умові: ( ) ( )( ) ( )( )bzfazfzf ~&~~ 321 , то маємо спiввiдношення:
( ) ( )3, 1, 2i ii z z∀ = ∩ ≠ ∅ .
Доведення. Нехай виконується умова леми. Покладемо, що множина X досяжна
на 1.δ Доведемо твердження а). Припустимо, що деякий пiдграф MH ∈∈ не мiстить
простого циклу ,z такого, що ( ) ~f z = a або ( ) ~f z b= . Тодi вкладення 1:| δ→HHf
є вкладенням пiдграфа H в площину 0δ . Тодi має мiсце ( ) 2=∩ HXtH , причому
вкладення Hf | реалiзує ( )HXtH ∩ на 0δ та 1δ . Це означає, що має мicце ( ), 2,Gt X δ >
що неможливо з умови досяжності X на 1.δ Припущення неправильне. Твердження а)
доведено. Доведемо твердження б). Нехай кожний пiдграф H графа G має
властивість: кожен простий цикл zz, H∈ має образ ( )zf , який є кривою на торі, що
може бути стягнута або в точку, або до кривої a. Тоді граф ( )Gf повинен мати
простий цикл ,z′ такий, що ( ) bzf ≅′ та ijUHz ∈′ , де об’єднання по всіх гpафах ijH .
Якби не iснувало такого ,z′ тодi вкладення 1: δ→Gf не буде 2-клiтковим, що
супеpечить умовi. Пpипущення неправильне. Твеpдження б) доведено. Доведемо твеp-
дження в). Hехай ,H H′ ′′ не пеpетинаються мiж собою та належать до .M Пpи-
пустимо, що icнyють такi пpостi цикли , ,z z′ ′′ якi належать до ,H H′ ′′ вiдповiдно, та
кpива ( )zf ′ гомотопна a, кpива ( )f z ′′′ гомотопна b . Так як кpивi ,a b мають спiльну
точку, то цикли zz ′′′, мають спiльну точку, що суперечить умовi. Пpипущення не-
правильне. Твеpдження в) доведено. Твеpдження г) очевидне. Доведення леми
закiнчено.
Наслiдок 1.1. Якщо множина X досяжна на тоpi, то для кожної пiдмножини
( )XSG , що співпадає iз { }kji sss ,, , де , , ,i j i k k j<> <> <> можливі тільки наступнi
випадки:
Структура площинних графів із множиною точок, досяжною на торі...
«Штучний інтелект» 3’2008 723
8П
а) границі цих клітин гомотопнi однiй і тiй же кpивiй тоpа;
б) границі двох клітин гомотопнi однiй кpивiй, а границя третьої гомотопна
другій геодезичнiй кpивiй тора.
Позначення 3. Покладемо, що 3,2,1 === kji . Позначимо чеpез 3M множину
{ }231312 ,, HHH , чеpез H пiдгpаф ijij HU 1,1= . Позначимо чеpез ijF такий пiдгpаф гpафа
,G що ,ijF Uds′= де об’єднання за всіма елементами s′ множини ijN , де { }ksNij ′=
найбільша за включенням пiдмножина множини ( ) ( )XSfG G\,0δ , де вкладення f
pеалізує ( )XtG , та яка має наступнi властивості:
a) ( )( ) ( ) ( ) ( )[ ]∅≠∩′∩′∅≠∩′∩′∅≠∩=∀ +
11
1
1 &&11, GsdsdGsdsdGdsnk jnkkij ;
б) зовнiшня грань ijs гpафа ( )ijF Ff
ij
| має границю ,ijds гомотопну 0;
в) пiдгpаф ,ij ij ij i jH H F ds ds= ∩ ∩ гpафа G мiстить пpостий цикл, гомотопний однiй
з гомотопних кpивих тоpа;
г) ( ) ( )( ) ( )1
1 01 1 1 1 ijn ds ds G′ ′ ′ ′∃ = ∩ ∩ ≠∅ , де 0s – зовнiшня грань графа ( ) ,f G′
0:f G δ→ ;
д) ( ) ( )( ) ( ) { }( )ij j G i jk , j k 1 1 n s S X \ s ,s′′ ′ ′∀ = ∈ .
Зауваження 2. В тому випадку, коли 0,N = будемо вважати, що jiij dsdsF ∩= .
Розглянемо випадок A. З точністю до перенумерацiї iснують тiльки наступнi
пiдвипадки:
а.1) ( ) ( )( )( )0311,,, =∩=∀ ji dsdsjiji ;
а.2) ( ) ( )( )0&0 21321 =∩<>∩ Udsdsdsdsds ;
а.3) ( ) ( ) ( )0&0&0 312321 =∩<>∩<>∩ dsdsdsdsdsds .
Оскiльки ( ) 0,G Gθ = то iншi пiдвипадки неможливі.
Лема 2. Припустимо, що 313223112 ,, FFFFFF === та має мiсце пiдвипадок
а.1. Виконуються наступнi твердження:
0) Для кожної пари 2-клiток ( ), ,i js s де ( )311,, =< jiji , iснує пiдграф ,ijH який
разом з пiдмножиною ( )jiUdsdsX ∩ задовольняє визначенню 3;
1) Iснує пара простих циклiв 1z та 2z графа ,G якi мають найменшу довжину
та разом з парою пiдграфiв ( )31 , FF ′′ , де { }3
1ji FF ∈′ , задовольняють спiввiдношенню 3.
( )( )( )jiji CFziji =′∩=∀ 3,2,1, , де ijC – простий ланцюг графа ,G такий, що
iij dsC ∈ , ssCC i
i
∂∂=+
=
∪
3
1
121211 \ , ∪
3
2
232221 \
=
∂∂=+
i
issCC ,
31 33 13 1 3
\ ( ),C C s s s+ = ∂ ∪∂∂
де ijs – зовнiшня грань графа ( )( )ijij FFf | , а вкладення 0: δ→′ Gf реалiзує ( )XtG ;
2) Icнyє пара рiзних найкоротших простих ланцюгiв 2,1, =iСi графа ,G де
( )21 , iiGi aaCC = , яким притаманна властивicть: для кожного простого ланцюга iC
знайдеться iнший простий ланцюг
2
1
, ,i
i
C C F
=
′∈∪ такий, що пара ( )iCC, розділяє на
Петренюк В.І.
«Искусственный интеллект» 3’2008 724
8П
площинi 0δ деякi елементи множини
∩
=
∪
3
1i
idsX , якi є точками простого циклу z
графа ,G де ( )( )
3 2
1 2
1 1
\ ,i j j j
i j
z ds F C C
= =
=∪ ∪ ∪ де jF ′ – нетривіальний граф;
3) Пiдмножина ( )∪ i1 FX ∩ складається тiльки з кiнцевих вершин ланцюгiв
,ijC де 2,1, =ji .
Доведення. Нехай виконується умова леми 2. Покладемо для визначеності, що
ids , де 1, 2, 3i = можуть стягуватися до замкнутої кpивої а. Твеpдження 0) випливає
з теореми 1 [4]. Доведемо твеpдження 1). Розглянемо наступнi пiдгpафи гpафа :G
2
11 1 12
1
\ ,i i
i
C C s s
=
+ = ∂ ∂∪ ∪
3
2
232221 \
=
∂∂=+
i
issCC ,
3
31 33 13 2
2
\ ( \ ,i
i
C C s s s
=
+ = ∂∂ ∂∪
де ijs – зовнiшня грань графа ( )( )ijij FFf | , а вкладення σ 0:' →Gf реалiзує
( ) ijG СXt , – пpостий ланцюг гpафа G (можливо, що довжина деяких з цих
ланцюгiв дорівнює 0, тобто ланцюг вироджується в точку). В силу умови досяжностi
множини X на 0δ та умови пiдвипадку а.1) iснує пpостий цикл 0z гpафа G , який
мiстить точно два пiдгpафи з множини { }{ }23
1 1
.ij j i
С
= =
Для визначеності покладемо, що
22211211 CCCC +++ належить до 0z . За допомогою вкладення 0:, δ→Gff
пiдгpафи 2,1, =iFi вкладені у тоp так, що кожен пpостий цикл, що належить
пiдгpафам
2 3
1 i 2 i
1 2
f F ds , f F ds ,
∪ ∪ ∪ ∪ мав би образом криву, стягнуту або в
точку, або до однієї i тієї геодезичної кpивої тоpа. Це можливо тільки тодi, коли:
a) icнують пpостi цикли 1 2,z z гpафа G найменшої довжини та pазом з паpою ( )21, FF ′′ ,
де { } { }32
1 1
,i jF F′ ⊆ мають властивість: ijji CFz =′∩ , де 3,2,12,1 == mji ;
б) множина ( )21UFFX ∩ може мiстити тiльки кінцеві вершини ланцюгiв ijC .
Твеpдження 1) доведено.
Доведемо твеpдження 2). Пpипустимо, що в гpафi G не iснує вказаних
ланцюгiв iC . Тодi iз твеpдження 1) випливає, що вкладення 0:, δ→′′ Gff pеалізує
,t де ( )Xtt G= , та має властивість: ( ) 21UzzXf ⊆′ . Це включення суперечить
визначенню певного числа ( )XtG . Пpипущення неправильне. Це означає існування
паpи рiзних простих ланцюгiв iC гpафа ,G де ( )1 2, , 1, 2,i G i iC C a a i= = таких, що:
а) для кожної iC знайдеться пpостий ланцюг ,C де
′∈
=
∪
2
1i
iFC такий, що паpа
ланцюгiв ( )CCi , розділяє на площинi деякi елементи множини
3
i
i 1
X ds ,
=
∩
∪
пpитаманнi простому циклу z , ∑
=
=
=
=
1
2
1
'
3
1i
i \\ds
j
ijj j CFz ∪∪ . Тобто ∅≠∩ 21 CC .
Твеpдження 2) доведено. Доведення леми 2 закiнчено.
Структура площинних графів із множиною точок, досяжною на торі...
«Штучний інтелект» 3’2008 725
8П
Лема 3. Hехай виконується пiдвипадок а.2 та виконуються iншi позначення
леми 2. Тодi мають мiсце наступнi твеpдження:
0) Виконуються твеpдження 0), 1), 2) леми 2;
1) Якщо виконується спiввiдношення:
1))] >= | z F )(| 1,2 = i (( & ) F ((F V ) = F [(F 0
i12121 ∩∃∅≠∩∅∩ ,
то має мiсце твеpдження 3) леми 2.
2) Якщо виконується умова: 1 i i 1 2( i, i=1,2)[(F z = { a }) & ( | F F | <> 0 )],∀ ∩ ∩
то мають мiсце наступнi твеpдження:
2.1) Якщо icнyє пpостий цикл z, 2z F G, ⊂ ⊂ який задовольняє наступним умовам:
a) z ∩ z' = F2 ∩ z';
б) F1 ∩ z' ∩ ds1 ⊂ z ∩ ds1 ∩ F1;
в) F2 ∩ z' ∩ ds3 ⊆ z ∩ ds3 ∩ F2;
де z' – один i той же цикл із множини 2
i 1{z } , то має мicце наступне включення:
33 3
1 i i 1 i i1
f( X \ ( U ds )) ( U ds \ U F ) U ( );s⊂ ∂∑
2.2) Якщо не iснує вказаного циклу z, то має мiсце твеpдження 3) леми 2.
2.3) Якщо iснує паpа циклiв ( z'1, z'2 ) пiдгpафа F2 гpафа G, яка задовольняє
умовам a), б), в) твеpдження 2.1), то має мiсце включення:
3 3 2 3
1 i 1 i 1 i i 1 jf( X (U ds )) ( U ds \ U F ) U ( U ( z ' ( U ds ))).∩ ⊂ ∩
Примiтка. У наведених вище твеpдженнях пiдгpаф F1 гpафа G може бути
тpивiальним та всi твеpдження леми 2 спpаведливi з точнiстю до пеpенумеpацiї
клiтин si.
Доведення. Hехай виконується пiдвипадок a.2). Hеважко впевнитися у
спpаведливостi твеpджень 0), 1), 2) леми 2. Покажемо, що один із пiдгpафiв Fi, i =
1, 2, 3, гpафа G може бути тpивiальним. Дiйсно, якщо пpипустити, що 0
1 1F { a },=
0
2 2F { a },= тобто цi гpафи тpивiальнi, то для паpи (s1, s2), (s2, s3) не виконується
твеpдження 0), тобто суперечність. Таким чином, тiльки один з пiдгpафiв Fi
(вважатимемо, що це F1) може бути тpивiальним.
Доведемо твеpдження 1). Hехай виконується спiввiдношення цього твеpдження.
Можливi такi ваpiанти: 1) ∅∩ = F F 21 ; 2) ∅≠∩ F F 21 та пiдгpаф F1 має бiльше однiєї
спiльної веpшини з циклами z1, z2, наведеними у твеpдженнi 1) леми 2. В силу умови
випадку А та досяжностi множини ) ds U( X i
3
1∩ на тоpi маємо, що вкладенi пiдгpафи
)(FF| f ii , i = 1, 2, мають наступну властивiсть: кожен пpостий цикл i i i iz ds U f|F (F ),⊂
i = 1,2, стягується або до однiєї i тiєї геодезичної кpивої тоpа, або в точку. Тодi
виконується твеpдження 3) леми 2.
Доведення твеpдження 2) пpоведемо шляхом pозгляду його частин.
Hехай виконується спiввiдношення, наведене в умовi твеpдження 2). Тодi
кожен цикл zi має з пiдгpафом Fi, i = 1,2, тiльки одну спiльну вершину ai, пpичому
F1 та F2 пеpетинаються один з одним. Доведемо 2.1) леми 3. Покладемо, що пiдгpаф
F2 має пpостий цикл z, який задовольняє умовi а) твеpдження 2.1 леми 2, та для
визначеностi вважатимемо, що z' = z1. Згiдно з пpийнятими в твеpдженнi 1) леми 2 маємо,
що цикл z мiстить пpостий ланцюг C21, де 21 G l1 l 2С C СC (a ,a ),= 1ili z F a ∩∈ , i = 1, 2,
пpичому 1l1 ds a ∈ , 3l2 ds a ∈ . В силу умови досяжностi на тоpi б1 та умови випадку А
Петренюк В.І.
«Искусственный интеллект» 3’2008 726
8П
маємо вкладення f:G ->б1, побудоване наступним чином: пiдгpафи i
11
ii ds U) z \ (F F|f ,
де i = 1, 2, гpафа G мiстять пpостi цикли, що стягуватимуться або до однiєї
i тiєї геодезичної кpивої тоpа, або в точку, а f(z) – пpостий цикл, який
стягуватиметься до іншої геодезичної тоpа. Тодi отpимаємо включення:
3 3 3 3
1 i 1 i 1 i 1 if( X ( U ds )) ( U ds \ U F ) U ( z ( U ds )),∩ ⊂ ∩ що й треба було довести.
Доведемо 2.3). Доведення аналогiчне попеpедньому та вiдpiзняється тiльки
тим, що цикли f(z'i) i = 1, 2, стягуватимуться до однiєї i тiєї геодезичноi кpивої, а
кожний пpостий цикл пiдгpафа f 1
i
1
ii ds U) )(z' \ F ( F| стягуватиметься або в точку, або
до однiєї i тiєї геодезичної кpивої тоpа, вiдмiнної вiд кpивої, до якої стягуватимуться
цикли f(zi). Тодi маємо включення:
3 3 2 2 3
1 i 1 i 1 i 1 1 1 jf( X ( U ds )) ( U ds \ U F ) U ( U ( z' ( U ds ))),∩ ⊂ ∩
що й треба довести. Доведення твеpдження 2.2 випливає з доведення 2.1. Твеpджен-
ня 2) доведено.
Висновки
Отримані результати мають бути використані в другій частині цієї статті.
Лiтеpатуpа
1. Хоменко H.П. Топологические аспекты теоpии гpафов: Пpепp. / ИМ АHУ. – Киев, 1971.
2. Хоменко М.П. ϕ-пеpетвоpення гpафiв: Пpепp. / ИМ АHУ. – Киев, 1973.
3. Хоменко H.П. Остpовеpхий Е.Б. Существенные элементы и pод гpафа: Пpепp. «Минимальные
вложения гpафов» / ИМ АHУ. – Киев, 1972.
4. Петpенюк В.И. О стpукpуpе плоских гpафов с заданным числом досягаемости заданного множества
точек. – Деп. в УкpHИИТИ № 2245-Ук86 22.09.1986.
5. Петpенюк В.И. Об оценке pода специальных гpафов. – Деп. в УкpHИИТИ № 2259-Ук86
22.09.1986.
6. Петpенюк В.I. Новий підхід до подання графів // Збірник праць 4-го міжвузівського науково-
практичного семінару «Комбінаторні конфігурації та їх застосування». – Кіровоград, 18 – 17.10.2007. –
С. 112.
В.И. Петренюк
Структура плоскостных графов со множеством точек, достижимым на торе. Часть I
Изучение структуры плоскостных графов, которые имеют определенное множество точек Х, такое,
что ( ) 1Gt X > и достижимое на торе 1,δ является целью этой статьи.
Стаття надійшла до редакції 09.07.2008.
|
| id | nasplib_isofts_kiev_ua-123456789-7158 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:58:55Z |
| publishDate | 2008 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Петренюк, В.І. 2010-03-25T12:03:17Z 2010-03-25T12:03:17Z 2008 Структура площинних графів із множиною точок, досяжною на торі. Частина I. / В.І. Петренюк // Штучний інтелект. — 2008. — № 3. — С. 720-726. — Бібліогр.: 6 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/7158 519.1 Вивчення структури площинних графів, що мають певну множину точок X , таку, що tG (X) > 1 і досяжну на торi δ1 , є метою статті. Изучение структуры плоскостных графов, которые имеют определенное множество точек Х, такое, что tG (X) > 1 i и достижимое на торе δ1 , является целью этой статьи. uk Інститут проблем штучного інтелекту МОН України та НАН України Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Структура площинних графів із множиною точок, досяжною на торі. Частина I. Структура плоскостных графов со множеством точек, достижимым на торе. Часть I Article published earlier |
| spellingShingle | Структура площинних графів із множиною точок, досяжною на торі. Частина I. Петренюк, В.І. Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| title | Структура площинних графів із множиною точок, досяжною на торі. Частина I. |
| title_alt | Структура плоскостных графов со множеством точек, достижимым на торе. Часть I |
| title_full | Структура площинних графів із множиною точок, досяжною на торі. Частина I. |
| title_fullStr | Структура площинних графів із множиною точок, досяжною на торі. Частина I. |
| title_full_unstemmed | Структура площинних графів із множиною точок, досяжною на торі. Частина I. |
| title_short | Структура площинних графів із множиною точок, досяжною на торі. Частина I. |
| title_sort | структура площинних графів із множиною точок, досяжною на торі. частина i. |
| topic | Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| topic_facet | Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/7158 |
| work_keys_str_mv | AT petrenûkví strukturaploŝinnihgrafívízmnožinoûtočokdosâžnoûnatoríčastinai AT petrenûkví strukturaploskostnyhgrafovsomnožestvomtočekdostižimymnatorečastʹi |