Главная » Все файлы » Просмотр файлов из архивов » Файлы формата DJVU » В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов

В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов, страница 67

DJVU-файл В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов, страница 67 Дискретная математика (2169): Лекции - 2 семестрВ.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов: Дискретная математика - DJVU, страница 67 (2169) - СтудИзба2019-04-28СтудИзба

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

DJVU-файл из архива "В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

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

Распознанный текст из DJVU-файла, 67 - страница

граф С) и граф Т представлены на рис. 77.4. Применение поиска в ширину к графу Т дает путь Р =(х», уь хн уз) из Х в Ун. Заменим (выполнение п. 5) в гРафе Т дуги (хз, у»), (у», х1), (хь у») соответ- ственпо на дуги (у.„, хз), (хп уг), (уы х4). Новый граф Т также изображен на рпс. 77.4. В нем Х„=- (х4, хб), Ти = = (Уз, У4). Снова выполнив поиск в ширину пз Х4о получим Х' = (хм х4, хб), 4"' = (у~). Средя олемептов матрицы И', лежащих на пересече77ин строк с номерами 2, 4, 5 и столбцов с номерами 2, 3, 4, 5, находим минимальный. и 5 5 и а и Иа б б 7 а и' г И 7 б и И б 5 7 Рвс. 77.4 5 5 1 1 5 1 и 5 и И а' г бег а 0 4 5 Рве.

77.5 б 0 И Р И и 5 иа г и 4 и г 1 4 5 5 Рис. 77.6 Получим и = И'44 = 2. Результаты последующего применения к графу 44 операции ((хм х4, хб), (у4), 2) и модифицированный граф Т представлены на рис. 77.5. В этом графе имеется путь Р =(хб, уб, хп у,) из Х44 в гм. «Новый» граф Т, полученный в результате выполнения п. 5, также изображен на рис. 77.5. Поиск в ширину в атом графе из множества Х~ = (х4) дает Х' = (хн х4), Г = (771). Находим а = И144 = (.

Результаты последующего выполнения пп. 8, 9 представлены на рис. 77.6. Поиск в ширину из х4 дает Х' = (хм х4, хб), г' = (у1, уб). 363 Находим и = 1ры = 2. Получаем новые матрицу и граф Т (рпс. 77.7). В графе Т имеется (хь уз)-путь Р = =(хо рь хь уз). Изменив этот граф в соответствия с п. 5, получим новый (рпс. 77.7), в котором Хя =- 1'~ = И. Пять его дуг, ведущих «от Х к 1'з, соответствуют ребрам В и и» а' г в 5 ив и г 7 г и г г г 7 5 и и и1 Ряс. 77.7 совершенного паросочетаппя минимального веса в поход- ном графе 6. Вес этого паросочетания равен О+ О+ 1+ +6+3=10.

5 78. Труднорешаемые задачи Как уже говорилось выше, общепринятой является точка зрения, согласно которой алгоритм считается эффективным, если он имеет полнпомиальпую сложность. Именно таковы все алгоритмы, рассмотренные в предыдущих параграфах. Заметим, однако, что за пределами зтпх рассмотрений осталась ббльшая часть важных задач.

Это, в частности, задачи отыскания в графе наибольшего независимого множества, гамильтопова цикла, й-раскраски и ряд других. Все они характеризовались нами как очень трудпью еще до того, каь мы приступили к обсуждению алгоритмов. Дело в том, что, песмотря на усилия многих специалистов, для решения подобных задач до с~х пор не найдено полиномпальвых алгоритмов. Болео того, имеются веские доводы, позволяющие предположить, что таких алгоритмов не существует. Обсуждению этих доводов и посвящен данный параграф. Начнем с внесения изменений в вычислительную модель. Будем считать, что капская ячейка абстрактной вычислительной машины моягет содержать только О или 1, и целые числа рассматриваются в двоичной системе счисления.

Б соответствия с этим всякое целое число ссчь О, 1 займет )1о8 ~а~ [ ячеек машинной памяти ([х[— наименьшее целое, не меньшее чем х). Рациональное 364 число, не являющееся целым, будем рассматривать в виде несократимой дроби и представлять з машине как упорядоченную пару целых чисел — числитель и зпаменатель этой дробя. Время вьшолпепгш кзж и й элс»гентарпон опорацин примем равным сумме „.шв леонсой ее операндов в двоичной системе счисления.

Далее будем рассматривать каждуа~ задачу в гак называемом распознавательном варианте, когда решение вадачи заключается в получении ответа «да» зли «нет». Всякий алгоритм реп»ения такой задачи, будучи примененным к соответствующему входу, работает какое-то время и затем, сообщив ответ «да» либо «нет», останавливается. Для некоторых задач пх «естественные» постановки уже являются распозназательными. Таковы, например, задачи распознавания изоморфизма, изоморфной вложимости, гамильтоновости, планарностн, эйлоровости графов.

Однако чаще (а на практике — как правило) исходная постановка задачи является оптимизационной. В оптимизационной задаче требуется выбратг пз мпожества допустимых решений Х такое решение х, вес (или стоимость) которого ш(х) минимален. В рассмотронных нами оптимизационных задачах в качестве Х фигурировали множества остовов, путей с заданной начальной вершиной или паросочетаний данного графа. Каждой оптимизационной задаче сопоставим ее распознавательный вариант, который выглядит следующим образом.

По заданным множеству Х, весовой функции и и числу й требуется определить, существует ли элемепт х'и Х такой. что ю(х) < Е Очевидно, что имея полиномпальный алгоритм решения оптимизационной задачи, легко получить полиномиальный алгоритм решения соответствующей ей распознавательпой задачи. Можно показать, что прп довольно пеобременительных предполонсеппях относительно функции ю верно и обратное.

Мы пе бучем пз этом останавливаться, поскольку для дальнейгяего нам «остаточно только знать, что оптимизационная задача «не проще» соответствующей распознавательпой. Итак, далее рассматриваются только распознавательные задачи. Определим Р кат класс распоэпавагельп»лх задач, каждая из которых»гоягет быть регпепа некоторым алгоритмом за полиномиальное время. Мы у»гге знаем, что в этот класс входят задачи о минимальных остовах, кратчайших путях 0 папболыпих паросочетанпях (имеются в виду распозпавательпые постановки этих задач, как было условлено). В то же время было названо не- вем сколько задач, прнпадлежвость которых н классу Р не установлена н считается сомнительной.

Топерь сделаем следующее важное наблюдение. Все задачи, с которыми мы сталкивались до сих пор, независимо от того, установлена их принадлен«ность классу Р или пег, обладают одним общим свойством: если вход задачи таков, что имеет место ответ «да», то существует полиномнальпый алгоритм, доказывающий этот факт. Поясним сказанное на примере.

Пусть вадача состоит в выяспении, является ли граф гамильтоновым, и пусть поступающий на вход граф С гамильтопов, т. е. в графе С имеется гамильтонов цикл С. Тогда доказательство гамильтоновости графа С заключалось бы в проверке включения Сщ С. Если, например, граф С задан матрицей смежности, то эту проверну мо»нно выполнить с помощью очевидного алгоритма, затратив 0(п) операций. Подчеркнем, что речь идет лппгь о существовании полиномиального доказательства — чтобы иметь это доказательство в своем распорян«енин, надо знать цикл С.

Положение иное, если граф С не является гамильтоновым. В атом случае нельзя утверждать даже, что полиномиальное доказательство этого факта существует. Можно, конечно, перебрать все (!С! — 1)! простых циклов длины !С! полного графа, проверяя наждый раз, содержится лп цикл в графе С. Однако подобное доказательство требует времени по крайней мере О((!С! — 1)!), и, следовательно, не является полнномнальным.

Теперь мы хотим определить еще один класс распознавательных задач, включив в него все задачи, обладающие тем свойством, что если вход задачи имеет ответ «да», то сугцествует полиномнальный алгоритм, проверяющий (доказывающий) этот факт. С этой целью дополним мнон«естес обычных операторов, из которых мы составляли алгоритмы, одним особым. Пусть л~ = А о А», ..., А — последовательность, элементами которой служат обычные операторы и один особый, запись которого имеет вид В((ь»»), (ь !»~И, 2, ..., т).

Пусть, далее, 0= д,, дь ..., о„— такой список, что о, = (~ либо д~=1» (1=1, р). После того как .Ф н 0 заданы, действие особого оператора В((п !»)' определим так: в результате Й-го (Й< р) выполнения этого оператора управление передается оператору А~, если д» = 1„и Л», если д, = Ц, а при Й) р вычисления прекращаются. Итак, последовательности операторов,Ф и списку 0 ста- 388 вится в соответствии обычный (детерминированный) алгоритм.

Этот алгоритм будем обозначать через М«, чтобы подчеркнуть наличие двух компонент ч» и (). Список () будем прп этом называть угадывающей последовательностью, а последовательность 4 — недегерминированным алгори«мои. Подчеркнем особо, что недеторминироьапный алгоритм пе является алгоритмом, а представляет собой чисто абстрактную конструкцию. Будем говорить, что педетерминированпый алгоритм ,Ф решает риспознавательную вида«у за полиномиальное время, если найдется такой полипом р(п), что выполняется следующее условие: каждый вход длины и этой задачи имеет ответ «да» тогда и только тогда, когда для него существует такая угадывающая последовательность Ч, что алгоритм Ф«, будучи примененным к этому входу, останавливается, сообщив ответ «да», и время его работы не превосходит р(п). Заметим, что согласно этому определению каждому входу с ответом «да» должен ставиться в соответствие свой алгоритм э«:«.

От этого алгоритма пе требуется ничего иного, кроме правильной реакции на свой вход. Поведение алгоритма на всех других входах для пас безразлично. Задача недетерминированно разрешила за полине»»иальное время, если существует недетермипированный алгоритм, решающий ее за это время.

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