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

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

Наоборот, предположим, что  — выполнимое вырал«ение. Пусть переменным присвоены зпачеппя «нстина» илн «ложь» так, что выражение В получило значение «истина». Тогда кая«дая элементарная дпзъюнкция С, долл«на содержать литерал и;,, имениций значение «истина». Ясно, что при этом и; чь и;,. Следовательно, и вершин оп и»,, ° ., о и попарно емельяны в графе 6, т. е.

образуют клику размера л». Таким образом, выражение В выполнимо тогда и только тогда, когда в графе С имеется клика размера й= ш. Легко видеть, что построение графа С по выраженшо В можно выполнить за время 0(р(п)), где р(п) — полипом, а и — длина записи выражения В (длина входа задачи ВЫПОЛНИМОСТЬ). Имеется ряд задач, входящих в г«Р, для решения которых до сих пор не найдено полиномиальных алгорит- 372 мов и относительяо которых неизвестно, являются ли они тУР-гголными.

Наиболее заметной графовой задачей среди нпх является задача об изоморфизме графов. С другой стороны, болыпппство встречающихся на практике задач не являются распозпакательными и, следовательно, не принадлежат классу 1уР. В то же время ко многим из них удается свести некоторые )«Р-полные задачи.

В этой ситуации полезным оказывается следующее определение. Задача называется ХР-трудной, если к ней сводится некоторая МР-полная задача. Новый термин позволяет, например, избежать громоздких конструкций типа «распознавательпый аналог задачи'А является )«Р-полной задачей» и дает возможность говорить просто, что «задача А )«Р-трудна». Теория )«Р-полноты, помимо теоретического, представляет и чисто практический интерес. Доказав, что задача 1УР-трудна, разработчик алгоритмов получает достаточные основания, чтобы отказаться от поиска эффективного и точного алгоритма.

Дальнейшие его усилия могут быть направлены, например, на получение приближенного рептенпя, либо на получение решения в типичном случае (в большинстве случаев). УПРЛЖНЕНИЯ 1. Пусть (ао а;) — любая пара следующих представлений графа: (а~) — матрица смежности, (ае) — список ребер, (аз) — список смежности. Полая~иге, что от а; к а; можно перейти аа время ОНас) + +!«е)), где )аь) — длина продставлспня а» 1Ь = 1, 3), 2. Пока««гите, как с помощью поиска в ширину распознать, являетсл лп граф двудольным. 3. Сввзпый граф, садернгащий в точности один цикл, называется У-деревом.

Постройте эффективный алгоритм для отыскания во взвешонном графе остовпого 1-дерева минимального веса. 4. Пусть граф С вЂ” дерево. Постройте алгоритмы сложности 01)01) для отыскания в графе С е) центра, б) диаметра. 5. Выяспнте сложность алгоритма Флери для построения вйлерова цикла (см. гл. УП, 3 43). 6. Разработайте алгоритм сложности СНЕС)) для построения зйлерова цикла в зйлеровом графе С.

Т. Постройтс алгоритм сложности СНЕС)) для отыскания простого цикла в графе С. 8. Пусть С вЂ” связный граф. Постройте полиномиальный алгоритм для отыскания гамильтонова цикла в графе С'. ЗТЗ 9 Пусть С вЂ” гамильтонов граф. Разработайте алгоритм слож- ности О((С() для построения гамильтонова цикла в графе й(С), при условии, что гамильтонов цикл графа С задан. 10.

Постройтс алгоритм сложности 0()С)) для раскраски вер- шин плапарного графа С в шесть цветов. И. Пусть взвешеняый ориентированный граф С не содержит контуров. Постройте алгоритм сложности 0((ЕС() для поиска крат- чайшего (г, г)-пути, при условии, что хотя бы один такой путь в графе имеется. (2. Разработайте алгоритм сложности 0()ЕС)) для отыскания в графе С а) максимального паросочетания, Ь) максимального независимого множества, с) минимального доминирующего множества. (3.

Пусть А, бь ..., И„ — графическая последовательность. Раз- работайте алгоритм сложности 0 ~ Н~ для построения реалист=г зации атой последовательности, Список литературы ОСНОВНАЯ 1. Берж К. Теория графов и ее применения.— Мл ИЛ, 1962.— 3!9 с. 2. Зы к о в А. А. Основы теории графов.— Мл Наука, 1987.— 381 с. 3. Оре О. Теория графов.— Мл Наука, 1980.— 336 с. 4. Свами М., Тхулас праман К. Графы, сети и алгоритмы.— Мл Мир, !984.— 454 с. 5.

Т ат т У. Творил графов.— Мл Мир, 1988. 6. Уилсон Р. Введение в теорию графов.— Мл Мир, 1977.— 207 с. 7. Х а р а р и Ф. Теория графов.— Мц Мир, 1973 — 300 с. ДОПОЛНИТЕЛЬНАЯ 8. Ай г не р М. Комбинаторпая теория.— Мл Мир, 1982.— 556 с. 9. А хо Х., Хопкрофт Дж., Ульман Дяь Построение и анализ вычислительных алгоритмов.— Мл Мир, 1979.— 536 с. 10. Бас акер Р., Саати Т. Конечные графы и сети.— Мл Наука, 1974.— 368 с.

!1. В слов В. В., Воробьев Е. М., Ш атал о в В. Е. Теория графов.— Мл Высшая школа, 1976.— 392 с. 12. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике.— Мл Наука, 1977.— 368 с. 13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи,— Мл Мир, 1982.— 416 с. 14. Д о н е ц Г. А., Ш о р Н. 3.

Алгебраичесгий подход к проблеме раскраски плоских графов.— Киев: Наукова думка, 1982.— 143 с. 15. Евстигнеев В. А. Применение теории графов в программировании.— Мл Наука, 1985.— 352 с. 16. Евстигнеев В. А., М е льни к о в Л. С. Задачи и упраязнения по теории графов и комбинаторике.— Новосибирск, Издво НГУ, 1981.— 88 с. 17. Е мел и чев В, А., Ковалев М, М., Кравцов М. К.

Многогранникц графы, оптимизация.— Мл 11аука, 1981.— 341 с. 18. 3 е м л я ч е н к о В. Н., К о р н е е н к о Н, Мт Тышкевич Р. И. Проблема изоморфизма графов у' Теория сложности вычислений, !. Записки научных семинаров ЛОМИ.— 1982.— Т. 118.— С. 83 — 158. 19. Зыков А, А. Теория конечных графов,— Новосибирск, Наука, 1969.— 543 с. 375 20. 3 ык о в А, А.

Гиперграфы >У УМН.— 1974.— Т, 29, вып, 6.— С. 89 — 154 21. Коршунов А. Д. Основные свойства случайных графов с больши>> *шелом вершин и ребер» УМН.— 1985.— Т. 40, вып. 1.— С. 107 — 173. 22. К р н с т о ф н д е с Н. Теорпп графов. Алгоритмический подход.— Мл Мир, 1978.— 432 с. "3 Маркус К.. Мнвк Х.

Обзор по теории матриц и матричных неравенств.— Мл Наука, 1972.— 232 с. 24. Пападпмптрну Х., Стайглпц К. Комбпнаторнан оптимизация. Алгоритмы и сложность.— Ы.: 1985.— 510 с. 25. Рейнгольд Э., Н н а ергел ьт 10т Дев Н. Комбинаторпые алгоритмы. Теория н практика.— Мл Мнр, 1980.— 476 с. 26.

Ринг ель Г. Теорема о раскраске карт.— М.: Мир, 1977.— 256 с. 27. Сергиенко И. В. Мате>штпческис модели и методы решения задач дискретной оптимизации.— Кпсв: Наукова думка, 1985.— 381 с. 28. Теория графов: Сборник переводов/Под ред. В. Б. Аленсеева, Г. П, Гаврилова, А. А. Сапожонке.— Мл Мир, 1974.— 223 с. 29. Харари й>., Палмер Э. Перечисление графов.— Мл Мир, 1977.— 324 с. 30. Холл М.

Комбинаторика.— Мл Ыир, 1970.— 424 с. 31. Цветнович Д., Дуб М., Захе Х. Спектры графов, Творил и орикс>кения.— Киев: Наукова думка, 1984.— 381 с. 32. Яблонский С. В Введение в дискретную математику,— Мл Наука, 1986.— 384 с. Предметный указатель Автоморфизы графа 42 Авсиоиы баз 64 — независимости 66 — ранга 67 — циклов 67 Алгоритм детерминированный 367 — Дгзйкстры 343 — жадный 93 — Краснала 60 — линейный 322 — недетерминированный 367 — отыскании кратчайших путей 350 — поиска в глубину 325, 332 — — — ширину 348 — полиномиальпый 322 — построении минимального остова 337, 340 — — наибольшего паросочетания 357 — — совершенного паросочетания Зэ9 — Прима 61 — уклални графа на плоскости !73 — Флери 195 База матроида 64 — орграфа 293 Базис коциклов матроида 81 — разрезов графа 84 — диклсв графа 84 — — матроида 81 Валентность вершияы 20 Вершина впснчая 26 — доминирующая 26 — изолнрованнан 26 — концевая 26 — периферийная 35 — центральная 36 Вес подграфа 38 — ребра 30 Вхол задачи 321 Гиперграф 298 — абсолютный 307 — бихроматнческий 309 — двойственный 299 — Л-однородный 299 Л-увиформвый 299 Гиперграф Л-раскрашиваемый 308 — Л-хроматический 306 — Л-цветной 306 — связный 301 —, удовлетворнющий условию Хеппи 311 313 Гипотеза Берже 272 — Келли — Улама !8 — Рамачандрана 286 — реконструируемости вершинной 18 — — реберной !8 — Хадвигера 264 — Харари 18 — четырех красок 255 Грани карты смежные 255 Граница грани плоского графа !53 Грань плоского графа !53 — — — внешняя 153 — — — внутренняя 153 Граф 9 — абстрактный 14 — ацикличесвий 53 — бнхроматический 237 — взвешенный 36 — внешнеплапарный 189 — — максимальный 189 — выпунлый прямолинейный !63 — гамильтонов !96 — гамильтоновс свявный 207 — двойственный абстрактно 172 — — геометрически 169 — двудольный 11 — додекаэдра 11 — дополнительный !5 — икосавдра 1! — алик 112 — конечный 9 — куба !! — кубический ЗЗ вЂ” веориентирсванвый 9 — непомеченный 14 — обыкновенный 17 — одноролный 32 — октаэдра 11 — ориентированный 16 — пересечений 38 — Петерсена 11 — планарный 150 — плоский 150 — — максимальный !58 полный 1Π— помеченный 14 — пороговый 224 — простой 17 пустой !О 377 Граф раскрашиваемый реберно 248 — расщепляемый 222 — реберный ЭВ, 31! — регулярный 33 — реконструируемый 18 — решетки 207 — самодополнительный 15 — сбалансированный 15 — связный 2Э вЂ” смешанный !  — совершенный 268 — тетраздра 11 — тороидальный 184 — триангулированный 272 — зйлеров 192 — Л-дельный 11 — Л-раскрашиваемый 2Э5 — Л-связный 136 — Л-хроматический 238 Графы изоморфкые 1Э вЂ” коспектральные 29 — платоновых тел 11 Группа автоморфизмав графа 43 Дерево 53 — остовное 57 — е корнем ориентированное 324 — 1Птейнера 62 Дефицит двудольного графа !28 Диаметр 35 Длина входа вадачи 32! — маршрута 22 — списка 3!9 дикость графа шеннопозсвая 109 Задание графа списками смежности 320 — — списком ребер 319 Занача коммивояжера 208 — аб остове минимального веса 60 — о восьми фервях 102 — — выполнимости 371 — — гаремах 90 — — кбнигсбергских мостах 191 — — вратчайшем остове 60 — — — пути 342 — — назначениях 124 — — пересечении матроидов 100 — — пяти ферзях 109 — — свадьбах 87 — — трех домах и трех колодцах !52 — проектирования коробки скоростей 237 — размещения минимаксная 36 — распознавательная 365 — распределенил оборудования 2Э6 — составления расписаний 236 — Штейнера евклидова 62 — — на графах 82 — — прямоугольная 62 — Пгр-полная 370 — 27Р-трудная 373 Замыкание транвитивное 297 Звевда 11 Знак Магомета 192 Игра «Кругосветное путешествие» !96 Ивоморфизм графов 13 — матроидов 73 Индекс хроматичесяий 248 Искаженность графа 187 Каркас 55 Карта 255 — й-раскрашиваемая 255 Класс цветной 238, 248 Клика 111 — максимальная 111 — наиболыпая 111 Кобаза 88 Колесо 11 Колода графа 18 Компонента 24, 301 — базовая 293 — связная 24, 301 — сильная 282 — сильно свявная 282 — В-сзявная !36 Конденсация 282 Контур гамильтояов 286 Коостов 72 Кодивл 69 Критерий Гавела — Хакими 211 — Зрдзша — Галлаи 213 Куб п-мерный 20 Лемма о рукопожатипх 26 Лес 53 Л !4! Маршрут 22 — ориентированный 280 — остовный 28! Матрица весов 319 — инцидентности 31 — Кирхгофа 30 — клин 115 — смежности 27 — — приведенная 30 Матроид 64 — бинарный 79 — векторный 70, 74 — графичесний 74 — двойственный 69 — дискретный 70 — матричный 21 — однородный 100 — представимый 75 — разбиении 92 — разрезов графа 72 — свободный 70 — трансверсальный 92 — тривиальный 70 — циклов графа 72 Множество внутренне устойчивое 102 — графа степенное 232 — доминирующее 109 — — минимальное 109 — — наименьшее 109 — независимое 102, 304 — — максимальное 102 — — наибольшее !02, 304 Множество ребер графа независимое !22 — трансверсальное гиперграфа 303 — элементов матроида вависвмое 67 — — — козависимае 69 — — — вонезависнмое 69 — — — независимое 66 Мост 134 Ыультиграф !5 — ориентированный !6 Набор независимых мне>веста матроида 65 Неплотность графа !03 Область связности 24, 301 Обхват 22 Объединение графов 19 — — дизъюнктное 19 — матроидов 95 Окружение 10, 125 Оператор 3!8 — аконец» 319 — присваивания 3!9 Операция влементарная 318 Опора 111 Орграф 16 — гамильтонов 286 — односторонне свявный 280 — односторонвий 280 — реберный 297 — сильно связный 280 — слабо связный 281 — транзитивиый 291 — зйлеров 280 Ориентация графа 32 Основание графа 283 Остов 55 Отец вершины ордерева 327 Отождествление вершин графа Очередь 323 Пара векторов графичеснан 284 Паросочетание 122, 303 — максимальное !22 — наибольшее !22, 303 — совершенное ! 23 Петля 16 Плотность 111 Подграф 17 — индуцированный 17 — остовный 17 — порожденный 17 Поддерево с корнем 327 Подразбиение ребра 160 Подцепь 22 Поиск в глубину 323 — — ширину 37 Покрытие вершинное 111 — — минимальное 111 — — наименьшее 111 — реберное !22 — — минимальное 122 — — наименьшее 122 Полипом графа характеристический 29 — — хроматический 247 Полуконтур 280 Полумаршрут 280 Полупуть 280 Полустепевь захода вершины 283 — исхода вершины 283 Полуцепь 280 Порядок гиперграфа 298 — графа 9 — матроида 05 Последовательность графа степевная 26 — графическая 209 — правильная 209 — производная 212 — расщеплнемая 223 — угадывающая 367 — униграфическая 2!1 Потомок вершины ордерева 327 Предок вершины ордерева 327 Представление гиперграфа кенигозо 300 — матроида 75 — списка последовательное 319 Проблема изоморфизма графов 1!5 — изоморфного подграфа 115 — нзоморфной вложимостн 115 — Кзпига 47 — клики 115 Проивведеиие графов 20 — — модульное 1!6 Пространство коциклов матроида 81 — разрезов графа 84 — циклов графа 84 — — матроида 81 Псевдограф 16 Путь в орграфе 280 Радиус графа 35 Разложение матроидное !20 — множества вершин полярное 2*'2 — пороговое 228 Размер входа вадачи 321 Ранг графа 28 — коциклический 60 — матроида 65 — подмножества злемеитов матроида 67 — циклический 56, 803 Раскрасив вершинйая 235, 306 — минимальная 236 — последовательная 238 — правильная 235, 306 — реберная 248 Расстояние между вершинами 34 Расщепление вершины 22 Реаливация гиперграфа 310 — — строган 314 Реконструкция 18 Род графа 184 Сабли Магомета 192 Сепаратор 145 Система равличных представителей 87 Слияние вершин 2! Сложность алгоритма 321 Спектр графа 29 Список 319 Стек 322 Степень вершины 26, 299 379 Ядро 294 Центр графа 36 Цепь 22, 300 Степень графа 34 — — Регулярного 32 — — сильная 108 — Ребра 299 СтРуктура данных 377 Стягивавие ребра 21 Сын вершины ордерева 327 Толщина графа 186 Точка сочленения 134 — Штейнера 62 Трансверсаль 87 — независимая 88 — частичная 87 Триангуляция плоская 157 Трудоемкость алгоритма 32! Турнир 283 Тета-граф 197 Укладка графа 15! 5'лиграф 2!1 Фактор 17 Функция матроица коранговая 69 — — рангоеая 67 Цепь диаметральная 35 — простая 22 Цикл 22 — газгкльтонов !98 — матропда 67 — простой 22 — адлеров 192 Часть графа 17 '1исло клиновое 111 — матроидное 120 — независимости !03, 304 — паросочетання 122, 303 — покрытия вершинного 1!1 — — кликоэого 112 — — реберного 122 — пороговое 228 — сеязпости 133, !34 — скрещиааннв — Хадзигера 21 Эксцентриситет вершины 35 5-компонента 196 1-процедура 212 я-последовательность 209 Оглавление Предисловие Введение 53 53 57 60 63 Глава 1.