Властивості 2-незведених простих графів
Запропоновано спосіб побудови 2-незведених простих графів шляхом приклеювання кількох пар
 ребер до 3-мінімального площинного графа. Предложен способ построения 2-несводимых простых графов приклеиванием нескольких пар ребер к
 3-минимальному плоскостному графу....
Saved in:
| Date: | 2008 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/6708 |
| 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: | Властивості 2-незведених простих графів / В.І. Петренюк // Штучний інтелект. — 2008. — № 2. — С. 34-40. — Бібліогр.: 3 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860139989876080640 |
|---|---|
| author | Петренюк, В.І. |
| author_facet | Петренюк, В.І. |
| citation_txt | Властивості 2-незведених простих графів / В.І. Петренюк // Штучний інтелект. — 2008. — № 2. — С. 34-40. — Бібліогр.: 3 назв. — укр. |
| collection | DSpace DC |
| description | Запропоновано спосіб побудови 2-незведених простих графів шляхом приклеювання кількох пар
ребер до 3-мінімального площинного графа.
Предложен способ построения 2-несводимых простых графов приклеиванием нескольких пар ребер к
3-минимальному плоскостному графу.
|
| first_indexed | 2025-12-07T17:48:58Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 2’2008 34
2П
УДК 519.1
В.І. Петренюк
Кiровоградський національний технiчний унiверситет, м. Кіровоград, Україна
pz@kdtu.kr.ua
Властивості 2-незведених простих графів
Запропоновано спосіб побудови 2-незведених простих графів шляхом приклеювання кількох пар
ребер до 3-мінімального площинного графа.
Вступ
Нехай G – простий скінчений граф із множиною вершин 0G та множиною
ребер 1G , вкладений 2-клітинно в орієнтований 2-багатовид nу роду nn =σγ )( .
Основні поняття та позначення взяті із [1]. Згідно з [2], [3] будемо називати граф G
n-незведеним, якщо кожен його власний підграф H має рід nH =γ )( , а сам
1)( +=γ nG ; причому 2-незведений граф назвемо нетороїдальним.
Розглянемо задачу вивчення структурних властивостей 2-незведених графів без
1-підрозділених ребер їх деякими внутрішніми точками.
Для цього використаємо метод φ-перетворень та поглянемо на 2-незведений
граф без 1-підрозділених ребер як на такий граф роду 2 із мінімальною кількістю
ребер, який, з одного боку, є φ-образом деякого графа G1 та зірки )( 0gStn при φ-пе-
ретворенні, визначеному на кінцевих вершинах зірки та множині точок М1 графа 1G ,
яка має число досяжності t, 1t > , та характеристику θ, 0и ≥ ; а із іншого боку, є φ-
образом деякого графа 2G та графа ∑
=
m
і
і
1
u із k-штук окремих ребер, тобто графа
mK2, при φ-перетворенні, визначеному на кінцевих точках ребер та множині точок
M2 графа G2, яка має число досяжності t, та характеристикою и , 1t ≥ , 0и ≥ .
Основні результати
Лема 0. Для k-незведеного графа G маємо наступні твердження:
1. Існує щонайбільше 2k непустих підмножин Ni )( 1G0GiN ∪⊂ множини
точок графа G, таких, що для довільного i існує j, i≠j, i, j=1(1)k та виконується
рівність 2)jNi(NuGt =∪− , де 1Gu∈ , jNiNU ∪⊂∂ .
2. Видалення довільного ребра u, 1Gu∈ , або «звільняє» одну із k ручок
2-багатовида σk, або «виконує» рівність 1)jNi(NuGt =∪− , за умови, що
))jNu()i(Nu( ∅=∩∂∨∅=∩∂ , тобто руйнує підграф
∪ jNiNG .
Властивості 2-незведених простих графів
«Штучний інтелект» 2’2008 35
2П
3. Якщо має місце рівність 2)jNi(NGt =∪ для
1G0GjH,iH ∪⊂
, то
існує найменший за включенням підграф )jNiH(NijH ∪= графа G, який має рід
1k)ijг(H −≤ та містить частинний підграф, гомеоморфний K4 чи K2,3, чи K4
(1), чи
K4
*, чи K4
*(1).
Рисунок 1 – Графи K4
(1), K4
*, K4
*(1)
Лема 1. Нехай G – t-мінімальний площинний граф, m
1}{x=X i , GGX 10 ∪⊆ ,
t (X)tG = , 2=γ , 0t > , 0и ≥ та задано φ-перетворення наступним чином:
).}{,()}{}{,( 111
1
kk
i
k
iii
k
i
i xYuxuG →∂++ϕ =∑
=
Якщо Y – 2-незведений, то мають місце наступні твердження:
1. }).4,3{(})3,2{( ∈∧∈ tk
2. Якщо 2k = , то для підмножин точок 2
11 }{ == iixN та 4
32 }{ == iixN маємо наступні
співвідношення:
a) 3)(
2
1
=
= iiG NUt та 2,1,2)(( == iNt iG ;
b) видалення чи стягування довільного ребра u, 1Gu∈ , приведе до
рівності 1)(1 =iG Nt хоча б для деякого i;
c) φ-образи ребер u1, u2 своїми парами кінцевих вершин ii uu }{∂ϕ
розділяють одне одного на площині 2-клітини ∆ та належать межі
однієї 2-клітини ∆, f)(G,1σ∈∆ , де f – вкладення G в 1σ , яке
реалізує )(иG X , причому ))(())(( 10 ∆∂⊄∧∆∂⊂ GfGf .
3) Якщо k = 3, то для кожного i, i = 1,2,3, }x,x{N 2i1ii = , маємо:
a) )3)NU(t()2)N(t( i
3
1iGiG =∧=
=
;
b) видалення чи стягування довільного ребра 1Gu∈ дає рівність
1)N(t iG1 = , де }Gu,u\G{G1 ∈ , хоча б для деякого i, i=1,2,3;
c) φ-образи ребер ui, i=1,2,3, мають ту властивість, що пари кінцевих
вершин розділяють на площині 2-клітини ∆ одна одну та належать
межі ∆∂ , )f,G(G1∈∆ , де f реалізує )X(иG .
Лема 2. Нехай задано ϕ-перетворення графа ∑
=
+
k
1i iuG в Y, визначене на
множині вершин графа kK2 та множині точок 3-мінімального графа G.
Петренюк В.І.
«Искусственный интеллект» 2’2008 36
2П
1. Якщо довільне 2-клітинне вкладення графа G в σ1, яке реалізує t, t = 3, та
и)0(GGи = , }{ 1,0и∈ , має таку 2-клітину s, f)(G,1уs∈ , що s)1G0f(G ∂⊆∪ та
існує підграф H графа Y, який містить iu
k
i
∂
=1
U , гомеоморфний K3,3, то 2г(Y)1 ≤≤ .
2. Якщо при довільному 2-клітинному вкладенні графа G в σ1, яке реалізує
tG(G0), 3)0(GGt = , та характеристику (x)Gи , але не існує 2-клітини s, такої, що
s)1G0f(G ∂⊆∪ , та кожне ребро uj, j = 1,2, однією зі своїх вершин до різних під-
множин Ni, Nj, таких, що 2)jNi(NGt =∪ , то 2г(Y)1 ≤≤ .
Лема 3. Нехай визначено ϕ-перетворення графа ∑
=
+
k
1i iuG на графі Y, яке
задане так, як у лемі 1.1, на множині вершин графа kK2 та деякій множині X, складе-
ній з точок xi, { }2k
1ixX = , )1G0(GX ∪⊆ , де G – 3-мінімальний площинний граф.
Для k = 2 мають місце наступні твердження:
1. Якщо 3(X)Gt = та 1(X)Gи =∂ , то 1г(Y) = .
2. Якщо 1)(Gt =X , и(X)Gи ∂=∂ , t > 3, то маємо нерівність 1иtг(Y) −∂−≤ .
3. Якщо 4(X)Gt = , 0(X)Gи =∂ , 0(x)Gи = , то маємо 2г(Y)1 ≤≤ .
4. Якщо tG(x) = 4 та існує принаймні 4 копії різних підграфів Hi, i = 1(1)4,
гомеоморфних K2,3 чи K4 і таких, що не мають спільних простих циклів, причому
кожна пара точок (xi, xj) така, що xi≠xj, належить різним Hi, Hj, то тоді 4г(Y) = , де k = 2.
Твердження 1. Нехай G – t-мінімальний площинний граф, в якому
( ) ( ) θθ == 00 , GtGt GG , та задано N – множину всіх різних підграфів, гомеоморфних
K4 чи К2,3 та таких, що не мають спільних точок.
Якщо в G існує множина N і |N| = n, виконується φ-перетворення
( ) ( ) { }( ) ||,,, 0
1
0 GMagagStG
Ljj
Mi
j
jjion ≤⋅⋅ℑ→
++
=
=
∑ϕ
та виконується співвідношення )2,1()()( 21 =∧=∧+= inNNNN ji , то тоді
nnn =+≤ℑγ 21)( .
Доведення. Ідея доведення полягає в тому, що кожна H1, H2 пара різних
елементів n множини Ni, і = 1,2, матиме ϕ -образ, гомеоморфний 1-зв’язному графу
KKH ′′+′= , де },K ,{K, 42,3∈′′′ KK рід якого дорівнює 1. Дійсно, це так, оскільки
( ) ∑
=
− +=ϕ
k
i
in HgStH
1
0
1 )( .
Твердження 2. Нехай G – t-мінімальний площинний граф, такий, що
,0)(,)( 00 == GQtGt GG N1 – множина всіх різних Hij, i = 1,...,k, j=1(1)ki, підграфів
графа G, які гомеоморфні К4 чи К2,3 та утворюють максимальний за включенням
1-зв’язний підграф графа G,
∀ ijij
HUG , де kinN ii )1(1, == .
Властивості 2-незведених простих графів
«Штучний інтелект» 2’2008 37
2П
Якщо має місце наступне ϕ -перетворення графа )( ion gStG
i
+ на граф ϕ , визначенe
формулою ( ) ( ) { }
=
ℑ→
++ϕ
== =
•∑∑ }{ 1 1
,,
11 1
1
1
1
ij
k
i
ki
j
gagStG g
k
j
kj
j
ijjioni
, то має місце нерів-
ність ( ) ∑
=
+≤ℑ
k
j
jkG
1
.
2
)( γγ
Доведення. Нехай виконуються умови твердження 2, якщо до пари графів Н1,
Н2, таких, що гомеоморфні або К4, або К2,3 та мають спільну вершину, то ( )21 HH ∪ϕ
буде 2-зв’язним графом роду 1. Тобто кожна пара перенумерованих підграфів
додаватиме 1 до 0)(),( /=GG γγ , а таких пар буде
2
jk
. Тому ( ) ∑
=
+γ≤ℑγ
k
j
jkG
1
. .
2
)( .
g02
Рисунок 2 – Ілюстрація до твердження 2
На рис. 2 наведена ілюстрація до твердження 2, де множина N1 складена із «за-
штрихованих» підграфів К2,3, множина N2 – із незаштрихованих К2,3. Ребро (g01, g02)
треба стягнути в точку, тобто 2)( =ℑγ .
Рисунок 3 – Ілюстрація до твердження 2, де N1 – заштрихований однозв’язний
підграф графа ℑ роду =ℑ)(γ 3 – 1 – 1 = 1
Петренюк В.І.
«Искусственный интеллект» 2’2008 38
2П
Теорема 1. Нехай G – площинний граф, 10VGGX ≤ – множина точок,
2211
2
16 },}{}{{,2)( mKXgggXXt iiijj === – граф із m копій графа 2K , що має одне
ребро. Якщо кожне ребро графа Υ суттєве відносно роду ),(Υγ ,2)( =Υγ при
операціях видалення чи стягування в точку цього ребра, то існує ϕ -перетворення
графа 2mKG + , визначене наступним чином: )}{,())(,( 1
*
2
1 1
2 0
m
iiij
j
m
i
gYggmKG →++ϕ ∑∑
= =
,
де 2)(,}{,}}{{)( 2
1
2
11
0
2 === == XtgXgmK G
m
ij
m
iij , де }3,2{∈m .
Доведення. Розглянемо ϕ -перетворення площинного графа G та графа 23K ,
),}{,}),({( 3K 3
1
3
1212 === iiiii Uaa де },,{ 21 iii aau =∂ визначене наступною формулою:
)}}{,())(,3( 2
1
3
1
2
1
3
1
2 ==
= =
→++ϕ ∑∑ jiijijij
j i
gYagKG . Якщо ,2)( =KG Xt де 2
1}}{ === jKiijK gX ,
то, як відомо, 1)()( += GY γγ для кожного 3,2,1=k . Будемо вважати, що граф Y не
містить ребер, несуттєвих відносно )(Yγ . Якщо 2)( 21 =UXXtG , то 1)()( +γ≤γ GY , то
можливо побудувати таке вкладення графа Y в 1δ , при якому ребра )()( 21 uUu ϕϕ
розміщені на ручці h , ),( 21 iihh = , де −−δ⊂ 2),,(},{ 021 ffGii вкладення графа G в
1δ , при якому iii
UUXXf δγ⊂
=
2
121 ))( . Розміщення на ручці h ϕ -образів ребер 21,uu
даватиме один із двох наступних варіантів розміщення ребер:
1) )(),( 21 uu ϕϕ розділяють одне одного своїми кінцевими вершинами, розмі-
щеними на ),( 21 iihδ , де 2121 ),( δδ=δ Uiiih (тобто перехрещені);
2) )(),( 21 uu ϕϕ не розділяють парами своїх кінцевих вершин одне одного,
тобто не перехрещуються.
В цьому варіанті на ручці можливо розмістити ще одне ребро )( 3uϕ , яке не по-
винно перехрещуватися з жодним із ребер )( 2uϕ , .2,1=i
Графічно ці варіанти матимуть вигляд:
)( 2uϕ )( 1uϕ
)( 2uϕ
)( 1uϕ
Варіант 1 Варіант 2
Рисунок 4
Розглянемо варіант 1. Доведемо, що 2)( 3 =+γ uGY та 2)( 21 −= iihh – ручка до
до 2-клітин ., 21 ii Дійсно, якщо приклеїти до 2-клітин 21,ii ще одну ручку h , так, щоб
не дотикатися до регулярних 2-клітин iiuii iii δ⊂, , то на цій ручці має розта-
шовуватися )( 3uϕ . Дійсно, це так, оскільки ребра )(),( 21 uu ϕϕ , вкладені на ),( 21 iih ,
розділяють множини кінцевих вершин одне одного і вкладення ребра )( 3uϕ в h не
можливе. Таким чином 2)( ≤γ Y . Якщо припустити, що 1)( =γ Y , то це означатиме,
що існує інше подання графа Y як ϕ -образу площини 1G при
Властивості 2-незведених простих графів
«Штучний інтелект» 2’2008 39
2П
)}}{{())(,( 11
*
121
a
j
i
iijijij gYagmKG ==→++ϕ ∑∑ , де 3<m . Згідно з нашим припу-
щенням матимемо, що для довільного вкладення 1
1: δ→Yf маємо принаймні для
деякого ребра співвідношення: що ),()( 21 iihuf ⊂ ∧ ))()(( 1
5
1
3.3 KuKu ∈∨∈ .
Тоді множина точок Х має число досяжності 1, оскільки ),( 0
11UGGX ⊂ бо має
місце включення ∅=∩δ XuuUf ii ),(( . Маємо суперечність умові.
Розглянемо підвипадок 11. Припустимо, що виконано умову випадку 1 та
1)( 1 =γ G , тоді будь-яке мінімальне вкладення f графа Y в 1δ повинно мати власти-
вість ),()( 21
1
2
1 iihmKf ⊂ , причому всі ці m ребер не будуть перехрещуватися, тобто
розділяти одне одного своїми кінцевими вершинами, ні між собою, ні з іншими
ребрами. У такому разі можливо стягнути в точку кожне з двох ребер 21,ee , які нале-
жать різним числам межі δ h ручки ),( 21 iihh = , які суміжні двом ребрам з umK2 .
Якщо граф Y немає зайвих ребер, то отримаємо, що ребра 21,ee можливо стягнути в
точку 2t , отримати із двох ребер, що належать множині )( 1
2mKf , одне кратне ребро,
розміщене на ручці. Це означатиме, що граф Y має принаймні два ребра, не суттєвих
відносно роду при операціях стягування, та одне ребро з множини )(
21
1
ЄЄY−ϕ можли-
во видалити. Все це містить протиріччя умові мінімальності графа Y відносно ряду
припущення. Підвипадок 11 неможливий.
Розглянемо підвипадок 12. Припустимо виконування умови випадку 0)( 1 =γ G .
Оскільки 1)( 1 =γ Y , то на єдиній ручці )( 21iih розміщуються всі ребра з множини
)(),( 1
11 GY ϕϕ та не допускаються їх перехрещення. Те саме, як у підвипадку 11, мож-
ливо виявити зайві ребра графа Y відносно )(Yγ . Це буде суперечити умові, тобто
підвипадок 12 неможливий.
Розглянемо варіант 2. В цьому випадку існують ребра, аналогічні тим 21,ЄЄ , які
наведені у підвипадку 12 та є не суттєвими відносно роду )(Yγ при стягуванні саме
цих ребер в точку. Цей факт суперечить умові, що наш граф Y має всі ребра сут-
тєвими відносно роду при операціях видалення ребра чи стягуванні їх в точку. Ця
суперечність означатиме неможливість випадку 2.
Таким чином наше припущення щодо виконання нерівності 2)( <γ Y суперечить
умові суттєвості відносно роду γ )(Y всіх ребер графа Y при видаленні чи стягуванні
в точку кожного ребра. Тобто нерівність неможлива, звідси випливає виконання
рівності ,2)( =γ Y то 2)( ≤γ Y . Доведення теореми закінчено.
Рисунок 5 – Ілюстрація до теореми 1, де m = 3
Петренюк В.І.
«Искусственный интеллект» 2’2008 40
2П
Рисунок 6 – Ілюстрація укладання ϕ -образу графа G на подвійному торі
Рисунок 7 – Ілюстрація до результату для m = 3
Висновки
Запропонований спосіб побудови 2-незведених простих графів шляхом при-
клеювання кількох пар ребер до 3-мінімального площинного графа дозволяє
побудувати поліноміальний алгоритм.
Література
1. Хоменко М.П. ϕ-пеpетвоpення гpафiв. Пpепpинт ИМ АHУ. – Київ, 1973.
2. Петpенюк В.И. О стpуктуpе плоских графов с заданным числом достижимости некоторого
множества точек. – Деп. pукопись в УкpHИИТИ N 814 19.08.1985.
3. Петpенюк В.I. Оцінка роду переплетених графів. Частина І // Искусственный интеллект. – 2006. –
№ 3. –С. 214-226.
В.И. Петренюк
Свойства 2-несводимых простых графов
Предложен способ построения 2-несводимых простых графов приклеиванием нескольких пар ребер к
3-минимальному плоскостному графу.
Стаття надійшла до редакції 25.02.2008.
|
| id | nasplib_isofts_kiev_ua-123456789-6708 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:48:58Z |
| publishDate | 2008 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Петренюк, В.І. 2010-03-15T13:35:31Z 2010-03-15T13:35:31Z 2008 Властивості 2-незведених простих графів / В.І. Петренюк // Штучний інтелект. — 2008. — № 2. — С. 34-40. — Бібліогр.: 3 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/6708 519.1 Запропоновано спосіб побудови 2-незведених простих графів шляхом приклеювання кількох пар
 ребер до 3-мінімального площинного графа. Предложен способ построения 2-несводимых простых графов приклеиванием нескольких пар ребер к
 3-минимальному плоскостному графу. uk Інститут проблем штучного інтелекту МОН України та НАН України Моделирование объектов и процессов Властивості 2-незведених простих графів Свойства 2-несводимых простых графов Article published earlier |
| spellingShingle | Властивості 2-незведених простих графів Петренюк, В.І. Моделирование объектов и процессов |
| title | Властивості 2-незведених простих графів |
| title_alt | Свойства 2-несводимых простых графов |
| title_full | Властивості 2-незведених простих графів |
| title_fullStr | Властивості 2-незведених простих графів |
| title_full_unstemmed | Властивості 2-незведених простих графів |
| title_short | Властивості 2-незведених простих графів |
| title_sort | властивості 2-незведених простих графів |
| topic | Моделирование объектов и процессов |
| topic_facet | Моделирование объектов и процессов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6708 |
| work_keys_str_mv | AT petrenûkví vlastivostí2nezvedenihprostihgrafív AT petrenûkví svoistva2nesvodimyhprostyhgrafov |