WWW.LIT.I-DOCX.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - различные публикации
 

«ЧАСТНЫЙ СЛУЧАЙ ЗАДАЧИ РАСПОЗНАВАНИЯ ПОЛНОГО НЕКАНОНИЧЕСКОГО ПРЕДФРАКТАЛЬНОГО ГРАФА Abstract: In the paper the properties of noncanonical prefractal graphs with substitution of the vertexes according ...»

УДК 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 nvertexes 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] .

–  –  –

заблокированными и на последующих этапах не замещаются. В дальнейшем будут замещаться только вершины вновь появляющихся затравок. Заблокированные вершины образуют множество M 1 – множество заблокированных вершин первого уровня (L = 2 ). Все вершины множества M 1 имеют степень n 1. Далее, в каждой из k затравок замещаются такие k вершин, что вершины из M 1 смежны только с новыми заблокированными вершинами (новые заблокированные множества

–  –  –





n k вершин по определению являются заблокированными, и образуют множество M 1 и M 1 = n k. Так как затравка полный граф, то все вершины множества M 1 смежны между собой .

–  –  –

k вершин множества V1 являются вершинами затравок. Согласно построению, шаге). Остальные k затравок имеют вершины степени n 1 и это затравки, присоединенные на последнем только

–  –  –

индуцированный подмножеством смежных с ней вершин и самой этой вершиной, является полным, то помечаем все его вершины и ребра, тем самым выделяя затравку. Стягиваем ее в одну вершину

–  –  –

( i = 2,..., L 1 ). Если граф, индуцированный этими вершинами и самой вершиной v является полным, то помечаем все его вершины и ребра, тем самым, выделяя затравку .

–  –  –

5.3. Среди этих двух множеств подграфов выбираем подграфы, которые являются смежными, то есть соединяют между собой два этих множества в исходном графе G ребром .

–  –  –

являются вершинами) и будут номерами вершин исходного графа в гамильтоновом цикле .

Иллюстративный пример. Пусть граф, изображенный на рис. 1, является неканоническим предфрактальным графом, порожденный полной 3-вершинной затравкой .

–  –  –

“1” и “31” соответственно .

По аналогии с вышеописанным нумеруем остальные подграфы слоя 4 и в результате G4 – “2”, G4 – “3”, G4 – “4”, G4 – “5”, G4 – “6”, G4 – “7”, G4 – “8”, G4 – “9”, G4 – “10”, получим:

G4 – “11”, G4 – “12”, G4 – “13”, G4 – “14”, G4 – “15”, G4 – “16”, G4 – “17”, G4 – “18”, G4 – G4 – “20”, G4 – “21”, G4 – “22”, G4 – “23”, G4 – “24”, G4 – “25”, G4 – “26”, G4 – “27”, “19”, G4 – “28”, G4 – “29”, G4 – “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 11

5. Задача ГАМИЛЬТОНОВ ЦИКЛ на каноническом предфрактальном графе, порожденном nвершинным колесом Теорема Задача гамильтонов цикл полиномиально разрешима на каноническом 3 .

предфрактальном графе, порожденном полным n-вершинным колесом .

Доказательство этой теоремы будет иметь конструктивный характер .

Алгоритм Алгоритм аналогичен алгоритму построения гамильтонового цикла для неканонического предфрактального графа, только разбиение на вложенные подграфы происходит таким образом, K Li является совокупностью, состоящей из n смежных между собой по что каждый граф слоя

–  –  –

Далее, среди всех узлов, смежных с узлом “1”, выбираем один из тех, который принадлежит оболочке. Нумеруем такой узел номером “2” .

Среди всех узлов, смежных с узлом “2”, выбираем один из тех, что принадлежит оболочке и еще не пронумерован. Нумеруем такой узел номером “3” .

–  –  –

Далее идти подобным путем уже не удается. Вершина 3 не имеет смежных с ней вершин, которые находятся на оболочке и не пронумерованы .

В этом случае мы нумеруем уже центр “колеса” .

После этого переходим к нумерации узла, который смежный с первой вершиной и не был пронумерован .

–  –  –

По аналогии с предыдущим слоем, переходя от двух следующих (по метке) подграфов слоя 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 (у редакції) .

–  –  –






Похожие работы:

«Приложение к свидетельству № 66939 Лист № 1 об утверждении типа средств измерений Всего листов 5 ОПИСАНИЕ ТИПА СРЕДСТВА ИЗМЕРЕНИЙ Спектрометр атомно-абсорбционный AI1200 Назначение средства измерений Спектрометр атомно-абсорбционный AI1200 (далее спектрометр), предназначен для измерений содержания различных элементов в водных растворах,...»

«Межрегиональная олимпиада школьников Будущие исследователи – будущее науки Биология 2017г. 7 класс ЗАДАНИЕ СО СВОБОДНЫМ ОТВЕТОМ 1. Подберите на Ваше усмотрение организмы, входящие в биоценоз. Заполните таблицу. Биоце Позвоночные Беспозвоно...»

«Экология животных Юг России: экология, развитие. №4, 2010 Ecology of animals The South of Russia: ecology, development. №4, 2010 ЭКОЛОГИЯ ЖИВОТНЫХ УДК 597.583.1-152.6 (262.81) ЭТОЛОГИЯ МОРСКИХ РЫБ КАСПИЙСКОГО МОРЯ © 2010 Абдурахманов Г.М.,Сокольская Е.А. Дагестанский государственный университет Астраханский государственный университет Выявле...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА Федеральное государственное бюджетное образовательное учреждение высшего образования "Иркутский государственный университет путей сообщения" Сибирский колледж транспорта и строительства МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО СОПРОВОЖДЕНИЮ САМОСТОЯТЕЛЬНОЙ...»

«Код ВПР. Биология. 11 класс. Вариант 16 ВСЕРОССИЙСКАЯ ПРОВЕРОЧНАЯ РАБОТА БИОЛОГИЯ 11 КЛАСС Вариант № 16 Инструкция по выполнению работы Проверочная работа включает в себя 16 заданий. На выполнение работы по биологии отводится 1 час 30 минут (90 минут). Записывайте ответы на задания в отведённом для этого месте в работе. В случа...»

«Исследовательский командный конкурс Геккон.ПЦ Новая школа. www.n-sh.org Предметное Название команды Тема доклада (буква) направление С Исследователи Биология Формулировка темы Вора – бей! В 1958 году в Китае по инициативе Мао Цзэдуна была организована кампания по борьбе с вредителями полей. В...»

«Район/ Муниципий MINISTERUL EDUCAIEI, Место жительства CULTURII I CERCETRII Учебное заведение AL REPUBLICII MOLDOVA AGENIA NAIONAL Фамилия, имя ученика PENTRU CURRICULUM I EVALUARE БИОЛОГИЯ ПРЕДВАРИТЕЛЬНОЕ ТЕСТИРОВАНИЕ ЛИЦЕЙСКИЙ ЦИКЛ Профиль: реальный, спортивный 27 апреля 2018 года Время выполнения:...»







 
2018 www.lit.i-docx.ru - «Бесплатная электронная библиотека - различные публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.