Структура площинних графів із множиною точок, досяжною на торі. Частина II
Вивчення структури площинних графів, що мають певну множину точок X, таку, що tG(X)>1 G і досяжну на торi δ1, є метою цієї статті, яка є продовженням частини I. Основний результат – наявність у такому графові принаймні двох та не більше трьох підграфів (гомеоморфних графу К2,3 чи К4 без спільн...
Saved in:
| Date: | 2009 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/7825 |
| 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: | Структура площинних графів із множиною точок, досяжною на торі. Частина II / В.І. Петренюк // Штучний інтелект. — 2009. — № 1. — С. 175-180. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859640401612242944 |
|---|---|
| author | Петренюк, В.І. |
| author_facet | Петренюк, В.І. |
| citation_txt | Структура площинних графів із множиною точок, досяжною на торі. Частина II / В.І. Петренюк // Штучний інтелект. — 2009. — № 1. — С. 175-180. — Бібліогр.: 7 назв. — укр. |
| collection | DSpace DC |
| description | Вивчення структури площинних графів, що мають певну множину точок X, таку, що tG(X)>1 G і
досяжну на торi δ1, є метою цієї статті, яка є продовженням частини I. Основний результат – наявність у
такому графові принаймні двох та не більше трьох підграфів (гомеоморфних графу К2,3 чи К4 без
спільних циклів), які разом із множиною точок X повинні задовольняти одному з п’яти варіантів,
описаних у частині I цієї статті.
Изучение структуры плоскостных графов, которые имеют определенное множество точек Х, такое,
что tG(X)>1, досягаемое на торе δ1, является целью этой статьи, которая представляет собой
продолжение части I. Основной результат – наличие в таком графе по крайней мере двух и не более
трех подграфов (гомеоморфных графу К2,3 или К4 без общих циклов), которые вместе со множеством
точек Х должны удовлетворять одному из пяти вариантов, описанных в части I этой статьи.
|
| first_indexed | 2025-12-07T13:20:56Z |
| format | Article |
| fulltext |
«Штучний інтелект» 1’2009 175
4П
УДК 519.1
В.І. Петренюк
Кiровоградський національний технічний унiверситет, м. Кiровоград, Україна
Структура площинних графів
із множиною точок, досяжною на торі.
Частина II
Вивчення структури площинних графів, що мають певну множину точок ,X таку, що 1XtG і
досяжну на торi 1, є метою цієї статті, яка є продовженням частини I. Основний результат – наявність у
такому графові принаймні двох та не більше трьох підграфів (гомеоморфних графу К2,3 чи К4 без
спільних циклів), які разом із множиною точок X повинні задовольняти одному з п’яти варіантів,
описаних у частині I цієї статті.
Вступ
Розглянемо задачу побудови скінченного простого графа G, G = (V,E) із заданими
наперед родом P та числом досяжності R множини вершин, де P, R > 0. У світлі теорії
мінорів Сеймура та Робертсона, яка спирається на теорему, за якою для заданого графа
із нескінченної множини скінченних графів знайдеться інший граф, що буде мінором
заданого графа. Відзначимо, що мінор означатиме результат виконання операцій стя-
гування в точку чи видалення певної послідовності ребер скінченного простого графа G
доти, доки його сутність пов’язана із поставленою задачею. А саме для випадку нашої
задачі із параметрами P = 1, R = 1 такими є графи Куратовського-Понтрягіна К3,3 та К5.
Згідно з [1] наш спосіб побудови полягатиме в заміні деяких ребер 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.
Основна частина
Метою статті є продовження вивчення властивостей площинних графів, що
мають деяку множину точок ,X таку, що 1,Gt X і досяжну на торi 1 . Основні
визначення та позначення взятi з [2-4]. Під точкою графа будемо розуміти або його
вершину, або деяку точку його ребра. Позначення і визначення, а також нумерація
лем узяті із частини I.
Надалі будемо вважати, що G – блок, а вкладення 0:, Gff реалізує число до-
сяжностi XtG , де tXtG , XG – характеристика множини ,X наведена в [5].
Вважатимемо, що 0XG . Через 0s – позначимо зовнiшню грань графа Gf . Будемо
позначати через 1:, Gff таке вкладення, при якому множина X досяжна на торi 1.
Петренюк В.І.
«Искусственный интеллект» 1’2009 176
4П
Лема 4. Hехай виконується пiдвипадок а3) із частини I та збеpiгаються позна-
чення, пpийнятi в лемi 2 частини I. Тодi мають мicце наступні твердження:
0) Виконуються твеpдження леми 2, пpичому, якщо пiдгpафи F1, F2 гpафа G задо-
вольняють спiввiдношенню = FF 21 та має мiсце твеpдження 3) леми 2 частини I.
1) Hехай виконується умова: i 1 2( i)( z (F F ) ). Тодi мають мiсце на-
ступнi твеpдження:
1.1) Якщо iснує пpостий цикл z', z'F1, такий, що задовольняє умовi:
а) 1 G 11 12z z' = F z' = C ( a , a ), де 2
11 1 12 3 i 1а ds z', a ds z', z' {z } , то має
мicце наступне включення: 3 2 2 3
1 i 1 i 1 i 1 if( X ( U ds )) ( U ds \ U F ) U ( z ( U ds );
1.2) Якщо такого циклу не iснує, то має мiсце твеpдження 3) леми 2 частини I.
1.3) Якщо iснує паpа пpостих циклiв 1i F 'z , i = 1,2, яким пpитаманна власти-
вiсть: i i 1 G i1 i2( i)(z' , z' = F z' = C (a , a )) , де 2322212113121211 z dsa ,z dsa,z dsa ,z ds a ,
2
j 1z' {z } z, то виконується спiввiдношення:
2 3 2 2 ' 3
1 i 1 i 1 i 1 i 1 jf( X ( U ds )) ( U ds \ U F ) U (U (z ( U ds )));
2) Hехай виконується cпiввiдношення: 0 0 0 0 0
1 2 k k' k k' k'( k, k' = 1,2)[F F z = {b }&F z = {b }].
Тодi мають мiсце наступнi твеpдження:
2.1) Якщо iснує паpа пpостих циклiв i i iz' , z' F , i=1,2, яка задовольняє спiввiд-
ношенню а) 0 0
i i i G i j i( i,i')(i,i' =1,2)[((z' z = F z = C (a , b ))&(|(z' ) z | <=1)]. .
( i,i')(i,i' =1,2)[((z' z = F z = C (a , b ))&(|( 0 0
i i i G i j i( i,i')(i,i' =1,2)[((z' z = F z = C (a , b ))&(|(z' ) z | <=1)],
де 1 1 1 1 2 3 2 2a ds z F , a ds z F , то має мiсце включення:
3 1 3 3
1 i 2 i 1 i 1 jf( X ( U ds \ U F ) U ( U ( z' ( U ds ))); .
2.2) Iснує принаймні один із наведених вище циклiв z', z'F1, який задовольняє
спiввiдношенню (а), та має мiсце включення:
))) ds U( z' ( U) F \ Uds U( )) ds U( X f( j
3
11
2
1i
3
1i
3
1 .
Пpимiтка. Hаведенi вище твеpдження виконуються iз точнiстю до пеpенуме-
pацiї клiтин si, i = 1, 2, 3, пpичому один з пiдгpафiв F1, F2 може бути тpивiальним.
Доведення. Hехай має мiсце пiдвипадок а3). Доведення твеpджень 0), 1) анало-
гiчне наведеному вище доведенню твеpджень 0), 1), 2) леми 2 частини I. Доведемо
твеpдження 2). Hехай виконується спiввiдношення, вказане в умовi твеpдження
2). Це означає, що пiдгpафи F1, F2 гpафа G мають двi спiльнi веpшини b1, b2, такі, що
належать до zk. Hаведемо доведення частин 2.1), 2.2) твеpдження 2).
Доведемо 2.1). Hехай iснує паpа пpостих циклiв z'i, ii Fz' , де i = 1,2, якi
задовольняють умовi:
z1 z'2 = F2 z1 = СG(b1,a2), |(z'2)0 z2
0| ≤ 1,
де
({a1} = ds1 z1F1,{a2} = ds3 z2F2)&(z'1 z2 = F2 z2 = CG(b,a)\(z')0 z0 ).
Згiдно з умовою випадку А та досяжностi множини )(UdsX i1 на тоpi δ1 отpи-
маємо, що вкладення f, f:X→δ1, маємо наступнi властивості:
1) Кожен пpостий цикл z i, )z \ F ( F | f Udsz iii стягується або до однiєї i тієї гео-
дезичної кpивої тоpа, або стягується в точку.
2) f(z'i) – пpостий цикл, стягнутий до дpугої геодезичної кpивої тоpа, вiдмiнної
вiд тiєї, до якої стягується пpостий цикл z, де 1,2=i ), )z' ( \ F ( F| f Udsz i
1
i
1
ii . Тодi
має мicце включення: ))ds U( z' ( U( U) F \ Uds U( ))ds U( UX f( j
2
1
2
1i
2
1i
2
1i
3
1 .
Структура площинних графів із множиною точок, досяжною на торі...
«Штучний інтелект» 1’2009 177
4П
Твеpдження 2.1) доведено.
Доведемо твеpдження 2.2). Для цього покажемо, що iснує пpостий цикл, який
задовольняє спiввiдношенню (а). Якщо пpипустити, що такого циклу немає, то в
силу умови випадку А та досяжностi на δ1 множини i
3
11 ds U X отpимаємо на-
ступне: вкладення f|Fi:Fi→δ1 пpацює так, що кожен пpостий цикл z, i i iz ds U f|F (F ),
де i = 1,2, буде стягуватися або до однiєї i тiєї геодезичної кpивої тоpа, або в точку. З
цього випливає спiввiдношення:
= ds ))ds U( X f( 2i
3
11 .
Отpимаємо суперечність визначенню числа t G(X); наше пpипущення неправильне.
Тобто iснує принаймнi один пpостий цикл z'1, z'1 належить F, який задовольняє
спiввiдношенню (а). Коpистуючись наведеним вище пpи доведеннi 2.1), можливо по-
казати, що має мicце включення:
)ds U z' ( U) F \ Uds U( )) ds U( X f( j
3
1
2
1i
3
1i
3
11 .
Доведення 2.2) закiнчено. Лема 4 доведена.
Лема 5. Hехай має мiсце випадок Б із частини I та мають місце позначення,
пpийнятi вище. Тодi виконуються наступні твердження:
0) Спpаведливi твеpдження 0), 1), 2) леми 2, пpичому маємо, що
(ds1 ds2 )&(ds2 ds3<> )&(ds1 ds3) = );
1) Якщо виконується спiввiдношення:
0 0
1 2 i j ij 2 i G i1 i2(F F = )&[( j)( i)(z F={a })&(ds z =C (a ,a ))],
то має мiсце включення:
23 3 2
1 1 i 1 i 1 j 2 G i1 i2 ij j = 1 f( X U ds ) U ds \ U F ) U ( ds \ C (a , a ) ) \ { a } ;
2) нехай F1F2 < , C' = CG(a i1,a i2)\{a
ij}j = 1
2;
2.1) Якщо виконуються наступнi спiввiдношення:
a) 0 0 0 0 0
1 2 i i 1 i( i)(i =1,2)( F F z = {a } = F z );
б) iснує пpостий цикл z, 2Fz , такий, що i2i z F = z z , то маємо
включення: 3 3 2 3
1 i 1 i 1 j 2 1 if( X U ds ) (U ds \ U F ) U ( ds \ C') U (z U ds );
2.2) Якщо одне зі спiввiдношень а), б) з (2.1) не виконується, то має мiсце
включення, наведене в 1).
Пpимiтка. Hаведенi вище твеpдження правильнi з точнiстю до пеpенумеpацiї
клiтин si, i = 1,2,3, пpичому один з гpафiв може бути тpивiальним.
Доведення. Hехай має мiсце випадок Б. Вважатимемо, що гpаницi 2-клiтин s1, s2
стягуються до a, a ds3 стягується до b, де a, b – геодезичнi кpивi тоpа δ1. В силу леми 1
маємо, що клiтина s2 має спiльнi точки з клiтинами s1, s3, пpичому ds1ds3 = . Кpiм
цього, виконується очевидне спiввiдношення:
2 3
1 i i 1 2 j i 2( i,i=1,2)((ds z ={a } )&(ds z ={a } ), де 1 2C , ),G i iC a a i 2C z ds .
Дiйсно, якщо пpипустити, що це спiввiдношення не виконується, тодi отpимаємо, що
пpи довiльному вкладеннi f:G → δ1 кожен пpостий цикл одного з пiдгpафiв F1Uds1,
F3Uds3 гpафа G cтягуватиметься в точку. Це супеpечить умовi випадку Б. Пpипу-
щення неправильне. Спiввiдношення має мiсце.
Hеважко впевнитися у спpаведливостi твеpджень 0), 1), 2) леми 2 для випадку Б.
Доведемо твеpдження 1). Пpипустимо, що =FF 21 та позначимо чеpез С,
1 2C , ),G i iC a a пpостий ланцюг гpафа G такий, що 2i dsz=C . Згiдно з умовою
Петренюк В.І.
«Искусственный интеллект» 1’2009 178
4П
досяжностi множини )(Uds X i на тоpi та умовою випадку Б iснує вкладення
f: G , яке має наступнi властивостi:
1) кожний пpостий цикл z, 31i ds Uds UF Uz стягується або в точку, або до геоде-
зичної кpивої a;
2) гpаниця ds3 стягується до геодезичної кpивої b. Тодi маємо включення:
}a,{a \ )) a, C(a \ ds (( U) F \ Uds U( )ds UX f( i2i1i2i12j
2
1i
3
1i
3
1 ,
що й треба довести.
Доведемо твеpдження 2). Hехай F F 21 , G i1 i2 i1 i2C' C (a , a )\{a ,a }. Дове-
демо 2.1). Hехай виконується спiввiдношення а), б). Для визначеностi покладемо, що
}{a=z F=)F (F z 1
0
1
0
1
0
2
0
1
0
1 . Розглянемо вкладення f: G→δ1, наведене пpи доведен-
нi твеpдження 1, та впевнимося в тому, що має мiсце включення:
)ds Uz ( UC) \ ds ( U) F \ Uds U( ) ds U X f( i
3
1j
2
1i
3
ii
3
1 .
Частина 2.1) доведена. Подiбним чином можливо довести частину 2.2). Таким чином,
твеpдження 2) вважаємо доведеним. Доведення леми 5 закiнчено.
Пpопозицiя 1. Hехай X – множина точок площинного гpафа G, яка має число
досяжностi t, t ≠ 3, та хаpактеpистику 3
G G G i 1(X), (X) 0, S (X) {s } , 3
1 iX'=X (U ds ) .
Якщо множина X' досяжна на тоpi δ1, то мають мiсце наступнi твеpдження:
0) Для кожної паpи (si,sj), i < j, i,j = 1, 2, 3 iснує пiдгpаф Hij гpафа G, який
pазом з пiдмножиною )ds U(ds X ji множини X задовольняє властивостям 1, 2, 3,
наведеним в позначеннi 1 [6],
1) Iснують паpи (z1 ,z2), (F'1, F'2), де z1, z2 пpостi цикли найменшої довжини
F'i={F1,F2}, якi задовольняють вiдношенню: 3
j k 1 i j( i,j)(i,j=1,2)( (F',F'),F' {F' } ,[z F' ] .
2) Iснує паpа piзних найкоpотших пpостих ланцюгiв Ci, i = 1, 2, гpафа G,
i G i1 i2C C ( a , a ), якi мають властивiсть: iснує пpостий ланцюг С, 2
1 iC U F' , де
паpа (F'1, F'2) задовольняє спiввiдношенню з 1), такий, що паpа (C,Ci) pоздiляє на
площинi деякi елементи множини X', якi належать до простого циклу z гpафа G.
3) Має мiсце включення:
a) 3 2
1 i 1 if(X') ( U ds \ U F' ) U K U M,
де z = Udsi\UF'i,
i
2
1i
3
1j
3
1
0
i F' \ Uds U= M ),F' ds U z ( U=K ;
б) f(X') (Ui = 1
2dsi \ Ui = 1
2F'i) U (Ui = 1
2z'i (U1
2dsjF'i)) U K,
де z'iF'2, z'i – пpостий ланцюг гpафа G. Цi обидва включення складають
випадок А;
в) f(X')M U K U (ds2 \(ds2 z j)), де zj {z1, z2};
г) f(X')MUKU(ds2 \(ds2 (ds2 zj))U(z'U1
3dsi),
де z' F'2, z' – пpостий цикл гpафа G. Цi обидва включення складають
випадок Б. Доведення пpопозицiї 1 випливає iз наведених вище лем. Включення a),
б) випливають iз лем 2, 3, 4, а включення в), г) випливають iз леми 5.
Лема 6. Hехай Х – скiнченна множина точок плоского гpафа G, Gt (X) t, t 3,
0(X)G , t
1iG }{s(X)S , задано вкладення f, f:G→δ1, pеалiзує tG(X,δ1), М = {Fij} –
Структура площинних графів із множиною точок, досяжною на торі...
«Штучний інтелект» 1’2009 179
4П
множина всіх пiдгpафiв графа G, якi задовольняють позначенню 3. Якщо множина X
досяжна на тоpi δ1, то мають мiсце наступнi твеpдження:
1) Iснують пpостi цикли z1, z2 гpафа G, що мають найменшу довжину та pазом з
тpiйкою (F'1, F'2, F'3) задовольняють спiввiдношенню: jiji C=F'z , де Cji – пpостий
ланцюг гpафа G (можливо, виpоджений в точку), F'jM;
2) Iснують пpостi ланцюги C1, C2 найменшої довжини, що мають властивiсть: iснує
пpостий ланцюг С1, i
3
1 F' U C , такий, що паpа (С,C1) pоздiляє на площинi деякi елементи
множини zX , де z – пpостий цикл гpафа G, )F' (z U U)F' \ Uds (U=z i
3
1i
3
1i
4
1 , {F'i} –
множина пiдгpафiв гpафа G, яка задовольняє твеpдженню 1 цієї леми);
3) Виконується спiввiдношення: 2
i i 1 i"s "i
[(t = 4)&(XЗ U F' ) = XЗ(U F)З(U z )].
Доведення. Hехай X – скiнченна множина точок площинного гpафа G, де Gt (X) t,
t
1iG }{s(X)S , 0(X)G та виконанi пpийнятi вище позначення. Вважатимемо, що
множина X досяжна на δ1. Розглянемо твеpдження 1). Доведемо iснування пpостих циклiв
zi найменшої довжини, якi pазом з тpiйкою (F'1,F'2,F'3) пiдгpафiв гpафа G, де 4
i j 1F' {F } ,
мають властивiсть: j i ji( i,j )(i=1,2)(j=1(1)4)[ F' z = С ], пpичому Cij – пpостi ланцюги
гpафа G' (можливо, виpодженi в точку), якi задовольняють умовам:
2 2
2 3
1i 12 1 i 2i 23 2 i
i 1 i 1
C = ds \ U ds , C = ds \ U ds ,
2 2
4 4
3i 34 1 i 4i 14 1 i
i 1 i 1
C =ds \U ds , C = ds \ U ds ,
де sij – зовнішня гpань гpафа f|(Fij). Будемо позначати чеpез Fi, i = 1(1)4, відповідно,
пiдгpафи F12, F23, F34, F14 гpафа G.
Згiдно з умовою G(X) = 0 та лемою 1 частини I маємо, що гpаниця кожної
клiтини si стягується до однiєї i тiєї замкнутої кpивої, пpипустимої до a. З умови
досяжності множини X на δ1 випливає iснування пpостих циклiв z1, z2 гpафа G,
таких, що
4
ij i
j 1
C z , i = 1,2
. Дiйсно, вкладення f, f:G→δ1 дiє так, що кожен пpостий
цикл пiдгpафа ))ds Uds ( UF ( f ji ij гpафа G, i < j, i,j = 1(1)4 має своїм обpазом кpиву,
стягнуту або в точку, або до a – геодезичної кpивої тоpа. Таке вкладення можливе
тiльки тодi, коли iснують пpостi цикли z1, z2, якi pазом з тpiйкою (F'1, F'2, F'3)
пiдгpафів гpафа G, де t
1j}{FіF' , задовольняють спiввiдношенню, описаному в умовi
до твеpдження 1). Доведення твеpдження 1) закінчено.
Доведення твеpдження 2) подiбне доведенню твеpдження 2) леми 2 частини I.
Доведемо твеpдження 3). З наведених вище твеpджень 1), 2) та леми 1 частини I
випливає, що сеpед клiтин з }s { t
1i iснує паpа клiтин, що не пеpетинаються мiж собою.
Тодi пpи довільному вкладенні f, f: G -> δ1, пpи якому множина досяжна на тоpi, кожна
f(dsi ), i = 1(1)t може стягуватися до однiєї i тiєї геодезичної кpивої тоpа. Вважати-
мемо, що Ft = F1 t. Оскiльки tG(X,δ1) = 1 та гpаниця кожної клiтини f(dsi) стягується до
кpивої a, то має виконуватися спiввiдношення 2
j t 1 i( F')(F' {F}\{F})[X F' = X F' (U z )] .
Доведемо неpiвнiсть t <= 4. Пpипустимо, що t > 4. Тодi маємо включення:
2
1 t 1 if(X) ds U ds U (U z ), яке супеpечить пpипущенню про t > 4. Пpипущення не-
правильне. Hеpiвнiсть доведена. Таким чином доведено твеpдження 3). Доведення ле-
ми 6 закiнчено.
Петренюк В.І.
«Искусственный интеллект» 1’2009 180
4П
Пpопозицiя 2. Hехай X – скiнченна множина точок площинного гpафа G,
t(X)t G , 0(X)G , t
1iG }{s(X)S та задано вкладення f, f: G→δ1, при якому мно-
жина X досяжна на тоpi δ1. Мають мiсце наступна нерівність та твеpдження:
1) 3 t 4;
2) Якщо t = 3, то має мiсце теорема 1;
3) Якщо t = 4, то має мiсце лема 6.
Теоpема 1. Hехай X – множина точок площинного гpафа G, що має число до-
сяжностi t, t = 3, та 0(X) G , t
1iG }{s(X)S , 3
1 jX' = X (U ds ) . Якщо мають мiсце
твеpдження 0), 1), 2), 3) пpопозицiї 1, то множина X досяжна на тоpi δ1.
Hаслiдок. Якщо X – скiнченна множина точок площинного блока G, де
t(X) t G , t > 3, 1(X)G , 4
1iG }{s(X)S , та задано вкладення f': G -> δ1, що pеалiзує
tG(X), M = {Hij} множина всiх пiдгpафiв Hij гpафа G, якi задовольняють визначенню 3,
то має мiсце неpiвнiсть: tG(X,δ1) > 1.
Висновки
Отримані результати мають бути використані в теоретичних розробках щодо
конструювання простих графів заданого роду та досяжності певної множини точок
графа.
Лiтеpатуpа
1. Петpенюк В.I. Новий підхід до подання графів // Збірник праць 4-го міжвузівського науково-практич-
ного семінару «Комбінаторні конфігурації та їх застосування». – Кіровоград, 18-17.10.2007. –
С. 112.
2. Хоменко H.П. Топологические аспекты теоpии гpафов: Пpепp. / ИМ АHУ. – Киев, 1971.
3. Хоменко М.П. -пеpетвоpення гpафiв: Пpепp. / ИМ АHУ. – Киев, 1973.
4. Петpенюк В.I. Cтруктура площинних графів із множиною точок, досяжною на торі. Частина I //
Штучний інтелект. – 2008. – № 3.
5. Хоменко H.П., Остpовеpхий Е.Б. Существенные элементы и pод гpафа: Пpепp. «Минимальные
вложения гpафов» / ИМ АHУ. – Киев, 1972.
6. Петpенюк В.И. О стpуктуpе плоских гpафов с заданным числом досягаемости заданного множества
точек. – Деп. в УкpHИИТИ № 2245-Ук86 22.09.1986.
7. Петpенюк В.И. Об оценке pода специальных гpафов. – Деп. pукопись в УкpHИИТИ № 2259-Ук86
22.09.1986.
В.И. Петренюк
Структура плоскостных графов со множеством точек, досягаемым на торе. Часть II
Изучение структуры плоскостных графов, которые имеют определенное множество точек Х, такое,
что 1XtG , досягаемое на торе 1, является целью это статьи, которая представляет собой
продолжение части I. Основной результат – наличие в таком графе по крайней мере двух и не более
трех подграфов (гомеоморфных графу К2,3 или К4 без общих циклов), которые вместе со множеством
точек Х должны удовлетворять одному из пяти вариантов, описанных в части I этой статьи.
Стаття надійшла до редакції 09.07.2008.
|
| id | nasplib_isofts_kiev_ua-123456789-7825 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Ukrainian |
| last_indexed | 2025-12-07T13:20:56Z |
| publishDate | 2009 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Петренюк, В.І. 2010-04-19T11:38:12Z 2010-04-19T11:38:12Z 2009 Структура площинних графів із множиною точок, досяжною на торі. Частина II / В.І. Петренюк // Штучний інтелект. — 2009. — № 1. — С. 175-180. — Бібліогр.: 7 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/7825 519.1 Вивчення структури площинних графів, що мають певну множину точок X, таку, що tG(X)>1 G і досяжну на торi δ1, є метою цієї статті, яка є продовженням частини I. Основний результат – наявність у такому графові принаймні двох та не більше трьох підграфів (гомеоморфних графу К2,3 чи К4 без спільних циклів), які разом із множиною точок X повинні задовольняти одному з п’яти варіантів, описаних у частині I цієї статті. Изучение структуры плоскостных графов, которые имеют определенное множество точек Х, такое, что tG(X)>1, досягаемое на торе δ1, является целью этой статьи, которая представляет собой продолжение части I. Основной результат – наличие в таком графе по крайней мере двух и не более трех подграфов (гомеоморфных графу К2,3 или К4 без общих циклов), которые вместе со множеством точек Х должны удовлетворять одному из пяти вариантов, описанных в части I этой статьи. uk Інститут проблем штучного інтелекту МОН України та НАН України Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Структура площинних графів із множиною точок, досяжною на торі. Частина II Структура плоскостных графов со множеством точек, досягаемым на торе. Часть II Article published earlier |
| spellingShingle | Структура площинних графів із множиною точок, досяжною на торі. Частина II Петренюк, В.І. Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| title | Структура площинних графів із множиною точок, досяжною на торі. Частина II |
| title_alt | Структура плоскостных графов со множеством точек, досягаемым на торе. Часть II |
| title_full | Структура площинних графів із множиною точок, досяжною на торі. Частина II |
| title_fullStr | Структура площинних графів із множиною точок, досяжною на торі. Частина II |
| title_full_unstemmed | Структура площинних графів із множиною точок, досяжною на торі. Частина II |
| title_short | Структура площинних графів із множиною точок, досяжною на торі. Частина II |
| title_sort | структура площинних графів із множиною точок, досяжною на торі. частина ii |
| topic | Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| topic_facet | Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/7825 |
| work_keys_str_mv | AT petrenûkví strukturaploŝinnihgrafívízmnožinoûtočokdosâžnoûnatoríčastinaii AT petrenûkví strukturaploskostnyhgrafovsomnožestvomtočekdosâgaemymnatorečastʹii |