Автореферат (Алгоритмы поиска максимальных независимых множеств графа и экспериментальная оценка их эффективности), страница 2

PDF-файл Автореферат (Алгоритмы поиска максимальных независимых множеств графа и экспериментальная оценка их эффективности), страница 2 Физико-математические науки (49898): Диссертация - Аспирантура и докторантураАвтореферат (Алгоритмы поиска максимальных независимых множеств графа и экспериментальная оценка их эффективности) - PDF, страница 2 (49898) - СтудИзб2019-06-29СтудИзба

Описание файла

Файл "Автореферат" внутри архива находится в папке "Алгоритмы поиска максимальных независимых множеств графа и экспериментальная оценка их эффективности". PDF-файл из архива "Алгоритмы поиска максимальных независимых множеств графа и экспериментальная оценка их эффективности", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве СПбГУ. Не смотря на прямую связь этого архива с СПбГУ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.

Просмотр PDF-файла онлайн

Текст 2 страницы из PDF

и 2013 г.), всероссийской конференции, посвященной 80-летию со дня рождения В. И. Зубова «Устойчивость ипроцессы управления» (Санкт-Петербург, 2010 г.), XIII всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2012 г.).Публикации. По теме диссертации опубликовано 8 работ, в том числедве статьи в журнале, входящем в перечень изданий, рекомендованных ВАК.Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, приложения и списка литературы, включающего 72 наименования. Общий объем работы составляет 101 страницу, невключая объем приложения, равный 48 страницам.СОДЕРЖАНИЕ РАБОТЫВо введении обосновывается актуальность темы исследования, степеньее разработанности, научная новизна, теоретическая и практическая значимость результатов, выносимых на защиту, а также приведено краткое содержание диссертационной работы.7В первой главе приведена постановка задачи поиска максимальных независимых множеств неориентированного графа, а также обзор существующих методов ее решения.

Кроме этого в заключительном параграфе главыпредставлена модификация известного алгоритма Робсона, которая была предложена автором, для формирования элементов наибольшего независимогомножества, а не только мощности этого множества, как это было сделано воригинальной работе Робсона.Вторая глава диссертации посвящена разработке нового алгоритма поиска всех МНМ графа – алгоритма AllIS. В первом параграфе даны основныеопределения и базовые конструкции разработанного алгоритма. Объектомисследования является неориентированный n-вершинный граф G = (V, E),заданный матрицей смежности A = ∥ai,j ∥n,n : 1, (i, j) ∈ E,ai,j = 0, (i, j) ∈/ E.Для использования алгоритма AllIS граф G представляется в видеG=[V, SV,A ], где V={1, 2, . . .

, n} — множество вершин графа,SV,A = {(p, q) | (p, q) ∈ V [2] & ap,q = 0} — множество всех несмежных парразличных вершин графа G. Любая пара несмежных вершин (β, γ) ∈ SV,Aназывается узлом и обозначается α = (β, γ). Базовым множеством для некоторого узла α = (β, γ) ∈ SV,A графа G назовем множествоDG [α] = {d ∈ V | (d, β) ∈ SV,A & (d, γ) ∈ SV,A } ∪ {β, γ}.Опорным множеством для этого же узла называется множествоωG [α] = DG [α]\{β, γ}.Независимое множество вершин в графе G обозначается QG , независимоемножество, в котором содержатся две вершины β и γ – QG [α], множествовсех вершин, имеющих ребро с каждой вершиной рассматриваемого графа –∆G [α], множество всех МНМ графа – M (G).8Процесс построения МНМ графа можно представить в виде дерева поиска,в котором каждый k-й уровень отвечает рассмотрению некоторого подграфаGk ⊂ Gk−1 ⊂ .

. . ⊂ G0 ≡ G.Подграф Gk+1 ⊂ Gk будем задавать в следующем виде:Gk+1 = [ω[α∗k ], S[α∗k ]], α∗k+1 ∈ S[α∗k ].Для компактной формализации алгоритма введем узел отрицательного уровня с вершинами, не имеющими ребра ни с одной вершиной графа G, и обозначим его α∗−1 = (β∗−1 , γ∗−1 ): ω[α∗−1 ] ≡ V, S[α∗−1 ] ≡ SV,A .Базовое множество D[αk+1 ] для узла αk+1 = (β k+1 , γ k+1 ) ∈ S[α∗k ] графаGk+1 представим какD[αk+1 ] = {d ∈ ω[α∗k ] | (d, β k+1 ) ∈ S[α∗k ] & (d, γ k+1 ) ∈ S[α∗k ]} ∪ {β k+1 , γ k+1 }.Опорное множество ω[α∗k+1 ] для узла α∗k+1 = (β∗k+1 , γ∗k+1 ) ∈ S[α∗k ] графа Gk+1определяем по правилуω[α∗k+1 ] = D[α∗k+1 ] \ {β∗k+1 , γ∗k+1 }.Множество S[α∗k+1 ] несмежных пар в графе, индуцированном множествомвершин ω[α∗k+1 ] :[2]S[α∗k+1 ] = {(p, q) | (p, q) ∈ ω[α∗k+1 ] & ap,q = 0}.Находим множество ∆[α∗k+1 ] по правилу∆[α∗k+1 ] = ω[α∗k+1 ] \ ∪(p,q)∈S[α∗k+1 ] {p, q}.Множество P [α∗k+1 ], сформированное согласно правилуP [α∗k+1 ] = {Q[α∗k ] ∈ P [α∗k ] | {β∗k+1 , γ∗k+1 } ⊆ Q[α∗k ]}, P [α∗−1 ] = ∅,будем называть окрестностью узла α∗k+1 .9Обсуждение основных моментов работы алгоритма, а также его псевдокод, приведены во втором параграфе.

В третьем параграфе доказываютсятеоремы, обеспечивающие теоретическое обоснование корректности работыалгоритма.Теорема 1. Любое максимальное независимое множество QG [α] содержится в базовом множестве, соответствующем паре α = (β, γ):QG [α] ⊆ DG [α].Теорема 2. Пусть QiG [α] – i-е МНМ графа G, содержащее вершины β иγ, m – количество всех таких множеств. ТогдаiDG [α] \ ∪mi=1 QG [α] = ∅.Согласно теореме 1 и теореме 2, для того чтобы построить максимальныенезависимые множества, содержащие в себе некоторую пару элементовα = (β, γ), необходимо использовать элементы базового множества для указанной пары.На основе следующей группы теорем (теорема 3 и теорема 4) формулируются критерии, по которым узлы рассматриваются как «неперспективные»для продолжения построения максимальных независимых множеств.Теорема3.

Если DG [α]DG [α∗ ], тогда для любого МНМ⊆QG [α] ⊆ DG [α] найдется МНМ QG [α∗ ] ⊆ DG [α∗ ] такое что QG [α∗ ] ≡ QG [α](другими словами, любое МНМ, содержащее вершины β и γ, будет являтьсямножеством, содержащим вершины β ∗ и γ ∗ ).Теорема 4. Если в некотором подграфе Gk ⊂ Gk−1 ⊂ . . . ⊂ G0 длявыбранного узла α∗k = (β∗k , γ∗k ) найдется множество Q ∈ P [α∗k ] :Q \ {β∗0 , γ∗0 , β∗1 , γ∗1 , .

. . , β∗k−1 , γ∗k−1 } ≡ D[α∗k ],тогда независимое множествоJe = {β∗0 , γ∗0 , β∗1 , γ∗1 , . . . , β∗k−1 , γ∗k−1 } ∪ QGk [α∗k ] ≡ Q.10В процессе работы алгоритма на каждом k-м уровне дерева поиска происходит выбор пары вершин α∗k = (β∗k , γ∗k ), используемых в дальнейшем длярасширения независимого множества J. Выбранный узел α∗k должен удовлетворять двум условиям:1) |D[α∗k ]| = maxαk ∈S[α∗k ] |D[αk ]| (для того чтобы как можно больше парвершин можно было исключить из дерева поиска после построения всех Q[α∗k ]);2) не должно существовать множества Q из окрестности P [α∗k ], удовлетворяющего условию теоремы 4 (в противном случае, рассмотрение этого узлаприводит к формированию максимального независимого множества, котороеуже было построено ранее).Подробный пример использования алгоритма AllIS для решения задачио поиске всех МНМ приведен в четвертом параграфе.

Заключительный параграф главы посвящен тестированию программной реализации разработанногоалгоритма. Представлены результаты сравнения алгоритма AllIS c известнымалгоритмом Брона-Кербоша, а также методом полного перебора. Согласнорезультатам исследования время работы алгоритмов AllIS и Брона-Кербошасущественно зависит от плотности ребер графа. На тестируемом наборе матриц при низком значении плотности ребер алгоритм AllIS показал лучшиерезультаты, чем алгоритм Брона-Кербоша (Рисунки 1, 2).В третьей главе предложен новый алгоритм решения задачи о поискенаибольшего независимого множества в произвольном неориентированномграфе – алгоритм MaxIS, псевдокод которого приведен в первом параграфе.Алгоритм M axIS является модификацией алгоритма AllIS, рассмотренного впредыдущей главе.

Обсуждение изменений, проведенных в алгоритмеAllIS, а также доказательства теорем, обеспечивающих правомерность этихизменений, приведены во втором параграфе. Основное изменение в алгоритмеMaxIS – это введение отсечения ветвей дерева поиска, исходя из мощностибазового множества выбранного узла.11Рис. 1: Зависимость времени работы алгоритмов Брона-Кербоша и AllIS от плотностиребер графов при фиксированной размерности.б)а)Рис.

2: Зависимость времени работы алгоритмов Брона-Кербоша и AllIS от размерностиграфов при значении плотности ребер p = 6% (a) и p = 4% (б).Справедлива следующая теорема:Теорема 5. Если в некотором подграфе Gk ⊂ Gk−1 ⊂ . . . ⊂ G0 длябазового множества выбранного узла α∗k = (β∗k , γ∗k ) выполнено условие:|D[α∗k ]| + 2k ≤ |Qmax |,тогда мощность независимого множества, содержащего пару вершин β∗k , γ∗k ,не превзойдет мощности текущего наибольшего независимого множества:|Q[α∗k ]| ≤ |Qmax |.12Второе изменение в алгоритме MaxIS – это отказ от использования окрестностей.

Доказывается, что в отличие от алгоритма AllIS, для нахождениянаибольшего независимого множества использовать окрестность нецелесообразно. И наконец, третье изменение связано с подсчетом количества элементов множества S[α∗k ] после принятия решения о построении ветви деревапоиска, идущей из текущего выбранного узла α∗k . Пусть |ω[α∗k ]| = m.1) Если |S[α∗k ]| =m(m−1),2значит, опорное множество ω[α∗k ] целиком пред-ставляет собой независимое множество.

В этом случае, текущим наибольшимнезависимым множеством будет множествоQmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ ω[α∗k ].2) Условие |S[α∗k ]| =m(m−1)2− 1 говорит о том, что среди элементов опорногомножества ω[α∗k ] только две вершины соединены ребром. В случае выполненияусловия |D[α∗k ]|+2k−1 > |Qmax |, в качестве нового наибольшего независимогомножества будет выступать множествоQmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ (ω[α∗k ] \ {δ}),где вершина δ – одна из пары вершин опорного множества ω[α∗k ], которыесоединены между собой ребром.3) В случае, когда |S[α∗k ]| =m(m−1)2− 2, некоторые вершины опорногомножества ω[α∗k ] соединены ребрами, причем количество ребер однозначноравно двум, а количество вершин, инцидентных этим ребрам, может бытьравно либо трем, либо четырем. В такой ситуации нужно определить сколькоразличных вершин участвует в образовании ребер.Если количество различных вершин равно трем, значит, необходимо проверить условие:|D[α∗k ]| + 2k − 1 > |Qmax |.13В случае его выполненияQmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ (ω[α∗k ] \ {δ}),где вершина δ инцидентна обоим ребрам.Если же количество различных вершин равно четырем, то при выполнении условия |D[α∗k ]| + 2k − 2 > |Qmax | наибольшим независимым множествомбудетQmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ (ω[α∗k ] \ {δ1 , δ2 }),где вершины δ1 и δ2 инцидентны разным ребрам.В третьем параграфе поиск наибольшего независимого множества по алгоритму M axIS проиллюстрирован на примере обработки неориентированного 10-вершинного графа.

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5288
Авторов
на СтудИзбе
417
Средний доход
с одного платного файла
Обучение Подробнее