Частный случай задачи распознавания полного неканонического предфрактального графа
В работе исследуются свойства неканонических предфрактальных графов с замещением вершин по определенному принципу. Построены алгоритмы распознавания предфрактальных графов с одной и k замещаемыми вершинами. Решена задача ГАМИЛЬТОНОВ ЦИКЛ для неканонического предфрактального графа, порожденного полно...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2005 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2005
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/58388 |
| 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: | Частный случай задачи распознавания полного неканонического предфрактального графа / Е.В. Бобылева // Мат. машини і системи. — 2005. — № 2. — С. 3-14. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-58388 |
|---|---|
| record_format |
dspace |
| spelling |
Бобылева, Е.В. 2014-03-23T14:24:24Z 2014-03-23T14:24:24Z 2005 Частный случай задачи распознавания полного неканонического предфрактального графа / Е.В. Бобылева // Мат. машини і системи. — 2005. — № 2. — С. 3-14. — Бібліогр.: 3 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/58388 519.8 В работе исследуются свойства неканонических предфрактальных графов с замещением вершин по определенному принципу. Построены алгоритмы распознавания предфрактальных графов с одной и k замещаемыми вершинами. Решена задача ГАМИЛЬТОНОВ ЦИКЛ для неканонического предфрактального графа, порожденного полной n-вершинной затравкой, и для канонического предфрактального графа, порожденного n-вершинной звездой. В роботі досліджуються властивості неканонічних предфрактальних графів із заміщенням вершин за деяким принципом. Побудовані алгоритми розпізнавання предфрактальних графів з однією та k вершинами, що заміщуються. Розв’язана задача ГАМІЛЬТОНІВ ЦИКЛ для неканонічного предфрактального графа, породженого повною n-вершинною затравкою, та для канонічного предфрактального графа, породженого n-вершинною зіркою. In the paper the properties of noncanonical prefractal graphs with substitution of the vertexes according to identified principle are discussed. The algorithm of recordinition of prefractal graphs with one and k substitutable vertexes. The problem HAMILTON CYCLE is solved for noncanonical prefractal graph, gene- rated by complete n- vertexes priming and for canonical prefractal graph, generated by n-vertex star. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Частный случай задачи распознавания полного неканонического предфрактального графа Частковий випадок задачі розпізнавання повного неканонічного предфрактального графа Partial case of the problem of recognition of complete noncanonical prefractal graph 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 |
Бобылева, Е.В. |
| topic |
Обчислювальні системи |
| topic_facet |
Обчислювальні системи |
| publishDate |
2005 |
| language |
Russian |
| container_title |
Математичні машини і системи |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Частковий випадок задачі розпізнавання повного неканонічного предфрактального графа Partial case of the problem of recognition of complete noncanonical prefractal graph |
| description |
В работе исследуются свойства неканонических предфрактальных графов с замещением вершин по определенному принципу. Построены алгоритмы распознавания предфрактальных графов с одной и k замещаемыми вершинами. Решена задача ГАМИЛЬТОНОВ ЦИКЛ для неканонического предфрактального графа, порожденного полной n-вершинной затравкой, и для канонического предфрактального графа, порожденного n-вершинной звездой.
В роботі досліджуються властивості неканонічних предфрактальних графів із заміщенням
вершин за деяким принципом. Побудовані алгоритми розпізнавання предфрактальних графів з однією та k
вершинами, що заміщуються. Розв’язана задача ГАМІЛЬТОНІВ ЦИКЛ для неканонічного предфрактального
графа, породженого повною n-вершинною затравкою, та для канонічного предфрактального графа,
породженого n-вершинною зіркою.
In the paper the properties of noncanonical prefractal graphs with substitution of the vertexes according to identified principle are discussed. The algorithm of recordinition of prefractal graphs with one and k substitutable vertexes. The problem HAMILTON CYCLE is solved for noncanonical prefractal graph, gene- rated by complete n- vertexes priming and for canonical prefractal graph, generated by n-vertex star.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/58388 |
| citation_txt |
Частный случай задачи распознавания полного неканонического предфрактального графа / Е.В. Бобылева // Мат. машини і системи. — 2005. — № 2. — С. 3-14. — Бібліогр.: 3 назв. — рос. |
| work_keys_str_mv |
AT bobylevaev častnyislučaizadačiraspoznavaniâpolnogonekanoničeskogopredfraktalʹnogografa AT bobylevaev častkoviivipadokzadačírozpíznavannâpovnogonekanoníčnogopredfraktalʹnogografa AT bobylevaev partialcaseoftheproblemofrecognitionofcompletenoncanonicalprefractalgraph |
| first_indexed |
2025-11-24T17:44:11Z |
| last_indexed |
2025-11-24T17:44:11Z |
| _version_ |
1850490368098828288 |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
3
УДК 519.8
Е.В. БОБЫЛЕВА
ЧАСТНЫЙ СЛУЧАЙ ЗАДАЧИ РАСПОЗНАВАНИЯ ПОЛНОГО
НЕКАНОНИЧЕСКОГО ПРЕДФРАКТАЛЬНОГО ГРАФА
Abstract: In the paper the properties of noncanonical prefractal graphs with substitution of the vertexes according to
identified principle are discussed.The algorithm of recordinition of prefractal graphs with one and k substitutable
vertexes. The problem HAMILTON CYCLE is solved for noncanonical prefractal graph, gene- rated by complete n-
vertexes priming and for canonical prefractal graph, generated by n-vertex star.
Key words: fractal (prefractal) graph, canonical and noncanonical fractal graphs, homogeneons priming, algorithm of
graph recognition, algorithm substitution.
Анотація: В роботі досліджуються властивості неканонічних предфрактальних графів із заміщенням
вершин за деяким принципом. Побудовані алгоритми розпізнавання предфрактальних графів з однією та k
вершинами, що заміщуються. Розв’язана задача ГАМІЛЬТОНІВ ЦИКЛ для неканонічного предфрактального
графа, породженого повною n-вершинною затравкою, та для канонічного предфрактального графа,
породженого n-вершинною зіркою.
Ключові слова: фрактальний (предфрактальний) граф, канонічний та неканонічний фрактальні графи,
однорідна затравка, алгоритм розпізнавання графів, алгоритм заміщення.
Аннотация: В работе исследуются свойства неканонических предфрактальных графов с замещением
вершин по определенному принципу. Построены алгоритмы распознавания предфрактальных графов с
одной и k замещаемыми вершинами. Решена задача ГАМИЛЬТОНОВ ЦИКЛ для неканонического
предфрактального графа, порожденного полной n-вершинной затравкой, и для канонического
предфрактального графа, порожденного n-вершинной звездой.
Ключевые слова: фрактальный (предфрактальный) граф, канонический и неканонический фрактальные
графы, однородная затравка, алгоритм распознавания графов, алгоритм замещения.
1. Введение
Актуальность проблемы. В последнее время в классе задач оптимизации и в экстремальных
задачах на графах внимание исследователей привлекли задачи распознавания на фрактальных
(предфрактальных) графах. Интерес к этим объектам обусловлен как теоретическими
предпосылками, так и тем, что с помощью их моделируются задачи биологии, медицины,
социологии, физики, экономики.
Анализ исследований и публикаций. Впервые понятие фрактальный (предфрактальный) граф
было введено в работе В.А. Перепелицы, И.В. Сергиенко [1]. Авторы вводят понятия канонического
и неканонического предфрактальных графов, исследуют свойства канонического
предфрактального графа, порожденного однородной затравкой, и приводят алгоритм
распознавания данного графа.
В работах [2, 3] продолжены исследования в данной области. В [2] рассмотрены свойства и
построены алгоритмы распознавания канонических предфрактальных графов, порожденных
полной затравкой, звездой, колесом. В [3] приводятся полиномиальные алгоритмы для некоторых
NP-полных задач на упомянутом выше классе графов.
Постановка задачи. В настоящей работе изучаются свойства неканонических предфрактальных
графов и построены алгоритмы их распознавания.
Неканонический предфрактальный граф – это граф, полученный замещением на каждом
этапе определенного подмножества вершин [1].
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
4
Рассмотрим неканонический предфрактальный граф, полученный замещением на каждом i-
м шаге 1−ik вершин ( ,....2,1;,...2,1 == LLi ).
Алгоритм замещения реализуется следующим образом.
Пусть дана затравка ( )QWH ,= – граф, содержащий циклы, т. е. не являющийся деревом.
Она является предфрактальным графом ранга 1, т.е. графом ( )1G . В ней замещаются
произвольные k вершин ( )nk < . Остальные незамещенные ( )kn − вершин называются
заблокированными и на последующих этапах не замещаются. В дальнейшем будут замещаться
только вершины вновь появляющихся затравок. Заблокированные вершины образуют множество
1M – множество заблокированных вершин первого уровня ( )2=L . Все вершины множества 1M
имеют степень 1−n . Далее, в каждой из k затравок замещаются такие k вершин, что вершины из
множества 1M смежны только с новыми заблокированными вершинами (новые заблокированные
вершины – заблокированные вершины затравок, которые были присоединены на предыдущем
шаге). Данные вершины образуют множество 2M .
Этот процесс продолжается до тех пор, пока не будет построен требуемый граф ( )LG .
Пусть неканонический предфрактальный граф ( )EVG ,= , порожденный произвольной
затравкой ( )QWH ,= , построен. Тогда имеют место следующие равенства:
( ) ;
1
11
1
−
−−+=
−
−
k
k
knnkV
L
L
k–1
k
L-1
–1 , (1)
1
1
−
−=
k
k
qE
L
, (2)
где L – ранг графа G ; k – количество замещаемых вершин ( )nk <<1 : n – количество
вершин затравки H .
При 1=k ( )11 −+= nLV ;
qLE = , (3)
где q – количество ребер затравки ( )QWH ,= .
На каждом шаге L в текущем графе ( )LG распознается 1−ik затравок.
Лемма 1. Множество вершин графа G можно разбить на два непересекающихся
подмножества вершин K и M , где K – множество вершин распознаваемых затравок; M –
множество заблокированных вершин и
1−= LnkK . (4)
Доказательство. Так как граф G неканонический, то на каждом шаге i замещается только
1−ik ( )Li ,...,2= вершин. Остальные вершины являются заблокированными. Следовательно,
множество вершин графа G разбивается на два непересекающихся подмножества, одно из
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
5
которых содержит все вершины затравок, и мощность его равна 1−Lnk , другое – все
заблокированные вершины, что и требовалось доказать.
Лемма 2. Множество заблокированных вершин M неканонического предфрактального
графа G , порожденного полной затравкой H , можно разбить на ( )1−L непересекающихся
подмножеств 1M , 2M , …, 1−LM . Причем
( )i
i knM −= , (при 11 −<< nk );
1−= ikM , (при 1−= nk );
1−= nM (при 1=k ),
где 1,...,1 −= Li и для каждого подмножества iM каждые kn − вершин смежны между
собой.
Доказательство. Пусть множество 1M – множество заблокированных вершин,
образованных на шаге 2. Так как в исходной затравке замещается только k вершин, то остальные
kn − вершин по определению являются заблокированными, и образуют множество 1M и
knM −=1 . Так как затравка полный граф, то все вершины множества 1M смежны между собой.
Множество 2M формируется по следующему принципу: в каждой из затравок, которые
заместили k вершин графа G , замещаются k вершин. Остальные незамещенные ( )kn −
вершин в каждой из этих затравок являются заблокированными и образуют множество 2M .
Очевидно, что так как затравка полный граф, то каждые эти ( )kn − вершины будут смежны между
собой. И так далее, пока не дойдем до заблокированных вершин последнего шага. Из
вышесказанного можно сделать вывод, что множество заблокированных вершин графа G можно
разбить на ( )1−L подмножеств 1M , 2M , …, 1−LM . Причем ( )i
i knM −= , если 11 −<< nk ,
1−= i
i kM при 1−= nk , 1−= nM i при 1−= nk ( )1,...,1 −= Li и для каждого подмножества
iM каждые kn − вершин смежны между собой, что и требовалось доказать.
Лемма 3. Множество вершин V неканонического предфрактального графа ( )EVG ,= ,
порожденного полной n-вершинной затравкой, можно разбить на два подмножества вершин 1V и
2V степени 1−n и n соответственно и nV =1 .
Соответственно множество вершин затравки ( )QWH ,= можно разбить на два
подмножества 1W и 2W степеней 1−n и n соответственно.
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
6
Теорема 1. Пусть ( )EVG ,= неканонический предфрактальный граф, порожденный
полной n-вершинной затравкой ( )QWH ,= и количество замещаемых вершин в каждой затравке
равно k . Тогда только для k затравок 11 =W , для остальных 01 =W .
Доказательство. Согласно лемме 3 количество вершин степени 1−n равно n . Из них
( )kn − вершин принадлежат множеству 1M (множество заблокированных вершин на первом
шаге). Остальные k вершин множества 1V являются вершинами затравок. Согласно построению,
только k затравок имеют вершины степени 1−n и это затравки, присоединенные на последнем
шаге. Следовательно, только для k затравок 11 =W , для остальных 01 =W , что и требовалось
доказать.
2. Алгоритм распознавания неканонического предфрактального графа, порожденного
полной n-вершинной затравкой при 1=k
Пусть неканонический предфрактальный граф ( )EVG ,= порожден полной n-вершинной
затравкой и 1=k . Представим алгоритм распознавания.
1. Проверяем условия (2), (3). Если они не выполняются, то данный граф не является
неканоническим предфрактальным графом.
2. Возьмем произвольную вершину v степени 1−n . Эта вершина либо принадлежит множеству
1M (множеству заблокированных вершин первого уровня), либо является вершиной затравки.
Рассмотрим смежные с ней вершины. Если среди них 2−n вершины имеют степень 1−n , то
записываем их, в том числе и вершину v , во множество 1M . Если все смежные с ней вершины
имеют степень n и граф, индуцированный подмножеством этих вершин и вершиной v полный, то
помечаем все его вершины и ребра, тем самым выделяя затравку, а все вершины, кроме v ,
имеющие степень 1−n , записываем во множество 1M , и таким образом вершины множества 1M
определены. Стягиваем вершины выделенных затравок в одну вершину и переходим к графу
)1( −LG .
3. В графе )1( −LG берем вершину степени 1−n , не принадлежащую множеству 1M . Если граф,
индуцированный подмножеством смежных с ней вершин и самой этой вершиной, является полным,
то помечаем все его вершины и ребра, тем самым выделяя затравку. Стягиваем ее в одну вершину
и переходим к графу )2( −LG .
Процесс, описанный в п. 3, продолжаем до тех пор, пока не получим граф ( )1G .
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
7
3. Алгоритм распознавания неканонического предфрактального графа, порожденного
полной n-вершинной затравкой при 1>k
В этом случае на каждом шаге Li ,...,2= распознается 1−ik затравок.
1. Проверяем условия (1), (2). Если они не выполняются, то данный граф не является
неканоническим предфрактальным графом.
2. Определяем множества 121 ,...,, −LMMM следующим образом. Множество 1M – это ( )kn −
вершин, имеющих степень 1−n , и эти вершины смежны между собой. Множество 2M – это
( )2kn − вершин, если 1−< nk ( k вершин, если 1−= nk ), имеющих степень n , и эти вершины
смежны с вершинами множества 1M (каждая вершина из множества 2M смежна с одной
вершиной множества 1M ),…, 1−LM – это ( ) 1−− Lkn вершин, если 1−< nk ( 2−Lk вершин, если
1−= nk ), имеющих степень n , и эти вершины смежны с вершинами множества 2−LM (каждая
вершина из множества 1−LM смежна с одной вершиной множества 2−LM ).
3. Берем произвольную вершину v , не принадлежащую множеству iM ( 1,...,2 −= Li ), и
рассмотрим 1−n смежных с ней вершин, не принадлежащих ни одному множеству iM
( 1,...,2 −= Li ). Если граф, индуцированный этими вершинами и самой вершиной v является
полным, то помечаем все его вершины и ребра, тем самым, выделяя затравку.
Когда все затравки выделены (а именно 1−Lk ), стягиваем каждую из них в одну вершину и
переходим к графу )1( −LG . Так как для этого графа множества iM ( 2,...,2 −= Li ) определены, то
остается только распознать 2−Lk затравок, т.е. применительно к этому графу выполняем действия,
описанные в п. 3.
Этот процесс продолжается до тех пор, пока не будет получен граф )1(G .
4. Задача ГАМИЛЬТОНОВ ЦИКЛ на неканоническом предфрактальном графе, порожденном
полной n-вершинной затравкой
Теорема 2. Задача ГАМИЛЬТОНОВ ЦИКЛ полиномиально разрешима на неканоническом
предфрактальном графе, порожденном полной n-вершинной затравкой.
Докажем эту теорему путем описания полиномиального алгоритма нахождения
гамильтонового цикла для графа указанного типа.
Пусть количество вершин, замещаемых в каждой затравке, равно k .
Считаем, что множества iM заблокированных вершин известны после действий
алгоритма распознавания.
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
8
Алгоритм
1. По аналогии с алгоритмом построения гамильтонового цикла для канонического
предфрактального графа, порожденного полной затравкой, исходный граф G разбиваем на
множества вложенных подграфов [3]. Всего таких множеств будет L . Назовем каждое такое
множество слоем. Каждый подобный слой является разбиением исходного графа на подграфы.
Разбиение происходит следующим образом:
– к слою LK отнесем все вершины исходного графа G (как отдельные одновершинные
графы): { }Lm
LLLL GGGK ,...,, 21= , где
1
1
)(
1
1
−
−−+=
−
−
k
k
knnkm
L
L
L при )1(1(11 −+=−<< nLmnk L
при 1=k );
– к слою 1−LK отнесем все затравки исходного графа G и вершины множества
)1,1( −= LiM i . Каждый граф из 1−LK будет или затравкой исходного графа, то есть содержит в
себе n вершин (или n графов слоя LK ), смежных между собой: { }1
1
2
1
1
11 ,...,, −
−−−− = Lm
LLLL GGGK
( )
1
1
(
2
2
1 −
−−+=
−
−
− k
k
knnkm
L
L
L при 11 −<< nk ( )( )( 1111 −−+=− nLmL при ))1=k , или
одновершинным графом, если эта вершина входит в состав множества )1,1( −= LiM i ;
– к слою 2−LK отнесем следующие подграфы: каждый граф из 2−LK будет содержать в
себе либо k затравок исходного графа и kn − вершин множества 1−LM , смежных с ними (т.е. n
графов слоя 1−LK ): { }2
2
2
2
1
22 ,...,, −
−−−− = Lm
LLLL GGGK ( )
1
1
(
3
3
2 −
−−+=
−
−
− k
k
knnkm
L
L
L при
11 −<< nk ( )( )( 1212 −−+=− nLmL при ))1=k , или будет являться одновершинным графом, если
эта вершина входит в состав множества 221 ... −∪∪∪ LMMM ;
– { }3
3
2
3
1
33 ,...,, −
−−−− = Lm
LLLL GGGK ( )
1
1
(
4
4
3 −
−−+=
−
−
− k
k
knnkm
L
L
L при 11 −<< nk
( )( )( 1313 −−+=− nLmL при ))1=k , где каждый граф слоя 3−LK является либо совокупностью из n
смежных между собой графов слоя 2−LK , или является одновершинным графом, если эта вершина
входит в состав множества 3321 ... −∪∪∪∪ LMMMM .
– …
– наконец, “верхний” слой },...,,{ 1
2
1
1
11
nGGGK = будет содержать всего n элементов,
каждый из которых содержит в себе или n смежных между собою графов слоя 2K , или будет
одновершинным графом, если эта вершина входит в состав множества 1M .
Описанный процесс осуществим: граф является предфрактальным, порожденным полной
затравкой, то на каждом этапе построения слоев мы будем иметь возможность находить или k
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
9
подграфов, смежных между собой, или одновершинные подграфы, вершины которых входят в
состав множеств ( )1,...,1 −= LiM i .
Далее выполняем действия, аналогичные, как и для алгоритма построения
гамильтонового цикла для канонического предфрактального графа [3].
2. Для первого слоя 1K проставляем произвольную нумерацию меток его подграфов. В
дальнейшем опустим номера подграфов всех слоев, считая их постоянными, введем для каждого
такого графа, наряду с его номером (верхним индексом), понятие пометки – порядковый номер
графа текущего слоя в гамильтоновом цикле, который ми строим. Ниже, под номером графа, будем
иметь в виду именно пометку, а не тот номер, который подграф получил при разбиении.
3. Считаем 2=i .
4. Если Li = , то идем на шаг 7.
5. Для слоя под номером i выполняем следующую последовательность действий
(подэтапов):
5.1. Находим в слое 1−i первый и последний пронумерованные подграфы (номер 1 и
номер 1−im ).
5.2. Находим в слое i подграфы, которые содержатся в подграфах 1
iG и imG1
5.3. Среди этих двух множеств подграфов выбираем подграфы, которые являются
смежными, то есть соединяют между собой два этих множества в исходном графе G ребром.
Обозначаем два данных подграфа как первый и последний в обходе (нумеруем 1
1−iG и 1
1
−
−
im
iG ).
Далее, по такому же правилу, находим смежные подграфы для каждых двух
последовательных графов p
iG 1− и 1
1
+
−
p
iG . Смежные подграфы обозначаем номерами pn
iG и 1+pn
iG .
Остальные подграфы (те, что не являются смежными для подграфов “верхних” слоев) нумеруем в
произвольном порядке в интервале [ ]1,1)1( −+− pnnp для данного рассмотренного графа p
iG .
Ясно, что [ ]imp ,1∈ .
6. Увеличиваем 1: += ii и переходим к шагу 4.
7. Слой LK представляет собой искомый гамильтонов цикл, а пометки его подграфов (они
являются вершинами) и будут номерами вершин исходного графа в гамильтоновом цикле.
Иллюстративный пример. Пусть граф, изображенный на рис. 1, является неканоническим
предфрактальным графом, порожденный полной 3-вершинной затравкой.
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
10
Рис. 1. Граф, порожденный полной 3-вершинной затравкой
Для этого графа 5=L , 2=k , 4=n .
1. Разбиваем исходный граф на множества вложенных подграфов:
:5K { } { } { }( )63,...,2,1 63
5
2
5
1
5 === GGG ;
:4K { } { } { } { } ,...,56,57,19,59,58,18,62,60,17,63,62,16( 4
4
3
4
2
4
1
4 ==== GGGG
{ } { } { } { })1,...,14,15,33,32,31 31
4
18
4
17
4
16
4 ==== GGGG ;
:3K { } { } { }( ,7,8,30,34,35,33,32,31,...,61,60,17,15,16,63,62 9
3
8
3
1
3 === GGG
{ } { })1,...,6 15
3
10
3 == GG ;
:2K { } { }( { } { })1,2,3,...,56,57,19,58,59,18,14,4,61,60,17,15,16,63,62 7
2
6
2
5
2
1
2 ==== GGGG ;
:1K {( 52,53,54,55,20,13,5,2,4,56,57,19,14,18,58,59,60,61,17,15,16,62,631
1 =G
} { })1,...,48,49,23,12,50,22,51,21 3
1 =G .
2. Ставим произвольную нумерацию меток подграфов слоя 1K . Пусть “1” для 1
1G , “2” для
2
1G , “3” для 3
1G .
3. Переходим к слою 2.
На предыдущем слое 1, как видно, первая метка соответствует подграфу 1
1G , последняя –
3
1G . На слое 2 подграфы, которые соответствуют подграфу 1
1G , – это подграфы 3
2
2
2
1
2 ,, GGG ; 3
1G –
это единый подграф 7
2G .
Как видно из структуры исходного графа G, графы “1” и “3” слоя 1 смежны по вершинам 1
и 2, то есть в нашем случае – по подграфам 6
2G и 7
2G . Эти подграфы получают метки “1” и “7”
соответственно.
Находим для графов “1” и “2” предыдущего слоя 1 подграфы слоя 2, по которым они
смежны. Как видно, это подграфы 2
2G и 3
2G . Эти подграфы получают метки “3” и “4”
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
11
соответственно. Так как первый и последний компоненты в обходе для графа 1
1G уже
пронумерованы, то другие подграфы слоя 2, которые соответствуют графу 1
1G , получают
произвольные метки в диапазоне от 2 до 2-х. Далее подобным образом расставляем номера для
других подграфов слоя 2, обозначая в первую очередь те подграфы данного графа, которые
связывают два последовательных подграфа предыдущего слоя.
Пусть, таким образом, все подграфы слоя 2 получили метки, которые уже пронумерованы.
4. Переходим к слою 3.
На предыдущем слое 2, как видно, первая метка соответствует подграфу 6
2G , последняя –
7
2G . На слое 3 подграфы, которые соответствуют подграфу 6
2G – это подграф 2
3G , (или просто
вершина 2), 7
2G – это подграф 15
3G (вершина 1).
Как видно из структуры исходного графа G, графы “1” и “7” слоя 2 смежны по вершинам 7 и
15, то есть в нашем случае – по подграфам 14
3G и 15
3G . Эти подграфы (вершины) получают метки
“1” и “15” соответственно.
По аналогии с предыдущим слоем, переходя от двух следующих (по метке) подграфов слоя
2 (в данном случае затравок), мы ставим метки всем подграфам слоя 3 (вершинам), проставляя в
первую очередь метки для подграфов слоя 2. В результате подграфы слоя 3 получат следующие
метки: 12
3G – “2”, 1
3G – “3”, 2
3G – “4”, 3
3G – “5”, 11
3G – “6”, 4
3G – “7”, 5
3G – “8”, 10
3G – “9”, 6
3G – “10”,
7
3G – “11”, 8
3G – “12”, 9
3G – “13”, 14
3G – “14”.
5. Переходим к слою 4.
На предыдущем слое 3, как видно, первая метка соответствует подграфу 14
3G , последняя –
15
3G . На слое 4 подграфы, которые соответствуют подграфу 14
3G – это подграф 30
4G (или просто
вершина 2), 15
3G – это подграф 31
4G (вершина 1).
Как видно из структуры исходного графа G , графы “1” и “15” слоя 3 смежны по вершинам 1
и 2, то есть в нашем случае – по подграфам 30
4G и 31
4G . Эти подграфы (вершины) получают метки
“1” и “31” соответственно.
По аналогии с вышеописанным нумеруем остальные подграфы слоя 4 и в результате
получим: 28
4G – “2”, 17
4G – “3”, 1
4G – “4”, 2
4G – “5”, 3
4G – “6”, 18
4G – “7”, 4
4G – “8”, 5
4G – “9”, 6
4G – “10”,
17
4G – “11”, 27
4G – “12”, 18
4G – “13”, 7
4G – “14”, 8
4G – “15”, 9
4G – “16”, 10
4G – “17”, 21
4G – “18”, 26
4G –
“19”, 22
4G – “20”, 11
4G – “21”, 12
4G – “22”, 13
4G – “23”, 23
4G – “24”, 14
4G – “25”, 15
4G – “26”, 16
4G – “27”,
24
4G – “28”, 25
4G – “29”, 29
4G – “30”.
В итоге, гамильтонов цикл будет иметь следующий вид: 2, 4, 15, 16, 63, 62, 61, 17, 60, 59,
58, 18, 14, 19, 57, 56, 55, 20, 54, 53, 52, 21, 13, 5, 12, 22, 51, 50, 49, 23, 48, 47, 14, 46, 45, 44, 25, 11, 6,
10, 26, 43, 42, 41, 27, 40, 39, 38, 28, 9, 29, 36, 35, 30, 34, 33, 32, 31, 8, 7, 3, 1, 2.
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
12
5. Задача ГАМИЛЬТОНОВ ЦИКЛ на каноническом предфрактальном графе, порожденном n-
вершинным колесом
Теорема 3. Задача гамильтонов цикл полиномиально разрешима на каноническом
предфрактальном графе, порожденном полным n-вершинным колесом.
Доказательство этой теоремы будет иметь конструктивный характер.
Алгоритм
Алгоритм аналогичен алгоритму построения гамильтонового цикла для неканонического
предфрактального графа, только разбиение на вложенные подграфы происходит таким образом,
что каждый граф слоя iLK − является совокупностью, состоящей из n смежных между собой по
схеме “колесо” графов слоя iLK − )1,...1( −= Li .
Опишем структуру, которую можно считать смежной по схеме “колесо”.
Пусть задана следующая структура: n подграфов, причем 1−n подграф (“оболочка
колеса”) соединен только з тремя этими подграфами (двумя “соседями” и “центром колеса”) и
является единым подграфом (“центр колеса”), который соединен дугами со всеми другими 1−n
подграфами.
Назовем такую структуру подобной колесу – ”колесо”, поскольку в качестве узлов в этой
структуре могут выступать как вершины (тогда мы получим обычное “колесо”), так и подграфы.
Нумерация узлов такой структуры уже не может проходить произвольно, так как это было
представлено для случая полной затравки. Поэтому опишем такой способ нумерации, чтобы мы
могли пройти с первой пронумерованной вершины этой структуры к последней, пометив все узлы
только один раз таким образом, чтобы i-й и i+1-й узлы были смежны между собой.
Пусть первый и последний узлы находятся на оболочке этой структуры. Центр никогда
(кроме начального шага) не будет первым или последним, так как он в исходном графе G
смежный только с вершинами данной структуры, в отличие от вершин оболочки.
Рассмотрим на примере 6-вершинного колеса. Пусть известна только первая и последняя
вершины в нумерации.
Рис. 2. Первый шаг нумерации
Рис. 3. Второй шаг нумерации
Далее, среди всех узлов, смежных с узлом “1”, выбираем один из тех, который
принадлежит оболочке. Нумеруем такой узел номером “2”.
Среди всех узлов, смежных с узлом “2”, выбираем один из тех, что принадлежит оболочке
и еще не пронумерован. Нумеруем такой узел номером “3”.
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
13
Рис. 4. Третий шаг нумерации
Рис. 5. Четвертый шаг нумерации
Далее идти подобным путем уже не удается. Вершина 3 не имеет смежных с ней вершин,
которые находятся на оболочке и не пронумерованы.
В этом случае мы нумеруем уже центр “колеса”.
После этого переходим к нумерации узла, который смежный с первой вершиной и не был
пронумерован.
Рис. 6. s-нумерация
Рис. 7. Граф, порожденный 5-вершинным колесом
После этого продолжаем нумерацию аналогично первым шагам до тех пор, пока не
пронумеруем все узлы (когда дойдем до последнего узла).
Эту нумерацию будем называть s-нумерацией, так как контур обхода структуры
напоминает латинскую букву “S”.
Иллюстративный пример. Пусть граф, изображенный на рис. 7, канонический
предфрактальный граф, порожденный 5-вершинным колесом.
Для этого графа 2=L .
1. Разбиваем на множества вложенных подграфов:
:2K { } { } { }( )25,...,2,1 25
2
2
2
1
2 === GGG ;
:1K { } { } { },10,9,6,4,3,23,22,20,17,16,8,7,5,2,1 3
1
2
1
1
1 === GGG
{ } { }25,24,21,19,18,15,14,13,12,11 5
1
4
1 == GG .
2. Ставим нумерацию меток подграфов слоя 1K . Пусть “2” для 1
1G , “3” для 3
1G , “1” для
4
1G , “5” для 2
1G , “4” для 5
1G .
3. Переходим к слою 2.
На предыдущем слое 1, как видно, первая метка соответствует подграфу 1
1G , последняя –
5
1G . На слое 2 подграфы, которые взяты из подграфа 1
1G , – это подграфы 11
2G , 12
2G , 13
2G , 14
2G , 15
2G .
5
1G – это подграфы 16
2G , 17
2G , 20
2G , 22
2G , 23
2G .
ISSN 1028-9763. Математичні машини і системи, 2005, № 2
14
Как видно из структуры исходного графа G , графы “1” и “5” слоя 1 смежны по вершинам
14 и 17. Эти подграфы (вершины) получают метки “1” и “25” соответственно.
Находим для графов “1” и “2” предыдущего слоя 1 подграфы слоя 2, по которым они
смежны. Как видно, это подграфы 11
2G и 8
2G . Они получают метки “5” и “6” соответственно. Так как
первый и последний компоненты в обходе для графа 4
1G уже пронумерованы, то остальные
подграфы слоя 2, которые соответствуют графу 4
1G , получают метки в диапазоне от 2 до 5 с
помощью s-нумерации, а именно: “2” – 15
2G , “3” – 12
2G , “4” – 13
2G .
По аналогии с предыдущим слоем, переходя от двух следующих (по метке) подграфов
слоя 2 (в данном случае затравок), мы ставим метки всем подграфам слоя 3 (вершинам),
проставляя в первую очередь метки для подграфов слоя 2.
Пусть, таким образом, все подграфы слоя 2 получили метки (уже пронумерованы).
В итоге, гамильтонов цикл будет иметь такой вид:14, 15, 12, 13, 11, …, 23, 22, 16, 20, 17, 14.
6. Выводы
В работе исследованы свойства полного неканонического графа, в котором замещение вершин
подчиняется определенному принципу. На основе этих свойств построены алгоритмы
распознавания данных графов на предфрактальность. Доказана теорема о полиномиальной
разрешимости задачи ГАМИЛЬТОНОВ ЦИКЛ на данном классе графов.
СПИСОК ЛИТЕРАТУРЫ
1. Перепелица В.А., Сергиенко И.В., Кочкаров А.М. К проблеме распознавания фрактальных графов //
Кибернетика и системный анализ. – 1999. – № 4. – С. 72 – 89.
2. Бобылева Е.В. Алгоритмы распознавания графов на предфрактальность // Питання прикладної математики
і математичного моделювання. – 2003. – С. 9 – 15.
3. Бобылева Е.В. О полиномиально разрешимых подклассах NP-полных задач на предфрактальных графах
// Питання прикладної математики і математичного моделювання. – 2004 (у редакції).
|