В.Н. Нефедов, В.А. Осипова - Курс дискретной математики, страница 55

с. обгцсс число циютов составляет 3 С.(! — !)!)( — !)!. К первому классу относятся следующие рассмотренные нами задачи: отыскание сстовного дерева грьфа; выделение компонен. ты связности графа и снзьной связисстн орграфа; нахожденае минимального пути в оргрзфе (или минимального маршрута в графе); иахогкдение эйлероваго цикла.

Дли рсшевпя этих задач построены алгорптчы, имеющие сложность 0(п-(-т). Второй иласс в настоящее время включает в себя такие за. дачи: нахождение матрицы сяязнасти (приведенный в раэд. 40 ф алгоритм Уоршела имеет сложность 0(л')); нахождение цвкловогп базиса (сложность алгоритма 0(лщ)); нахождение минимального пути в нагруженном графе методом Форда — Беллмаиа [сложиость алгоритма 0(л')). нахождение минимального осговного дерева в нагруженгюм графе (сложность алгоритма 0(ю')). Получение оценок сложно«тн алгоритмов выходит за рамки ханной книги.

Со спослбамн вычисления зтит оценок, а также с алгоритмамн, позволяющимн улучшить ик, можно ознаномнться в специальных монографиях, например в[9) Третий илвес содергкит следующие задачи: о существовании в графе гамильтонова пиила (задача коммивояжера); об опре- зар делении изоморфизма данного графа 01 какому-нибудь подгра. фу графа О», ие относящуюся непосредственно к теории графов, но фундаментальную задачу о выполнимости формулы логики выскааываиий, находящейся в КНФ, н многие другие задачи. Для решения зтих задач ме существует полиномнальных алто.

ритмов, хотя не кажетсв безусловным, что их решение возможно лишь с помощью зкспоненниальных алгоритмов. Для многих за. дач етого класса справедлива следующее свойство своднмссти: сущеспюванне полнномиальною алгоритма для решения одной из них дало бы полиномиальный алгоритм для решения другой. В современной дискретной математике третий нласс задач являееся праамегом приствльаого изучения. ЛИТЕРАТУРА 1. Бэжмоф Г Барта Г.

Совремпвпш иришмднзя влюбра. — Мл Мвр, 1976. 2. Гавр с Г. П., Сшюжсню А. А. Сборник задач по днскрешой математике. — М.: Наука, !977. б. Гери М„Дс озим Д. Вичнс итеньние мош «и а «руднорешае ме за. . — Мс Мвр, 1999 Л Косшюкяч А. И. Восдсмие а алюбру. — М.с Наука, М77. В Комбноаюрямй анализ! задача н унрзжнеинИНод обш. рен К А. Риб.

виюне. — Иш Науке, 1999 б. К 4 шс А. Введенае в врв«полную вомбонамрику. — Мс Наука, 1976. 7. Ллодоз И. А., Мшипмоеп Л. Л. Задача во жорки мномсша, зт валютнойй поппе в тсорно ыгорвт юи — РМ Наука, 1М4. 9. Мсндсшсоя Э. Ввсдсвне е петена*иче кую лосину. — Мс Наука, !976. 9. Иоез о П. С Влеменпс матсматачсской лосякн. — М.: Науке, 1979. !9, РН и и И„И а ясе ь бу., Дю И. Комбююторвие элсорвтмм: т и.

рня и нрактяка. — М с Мар, 1919. Н Иблонсвпй С, В. Вве;няню в лнсвретвую иатемаюпсу, — Мс Нзука, 1979. ОГЛАВЛВНК(В 12млэмие в Кеммню 01. Н ч и е тня ю рнн мнем 02. 0 и и И я н фу ыя 0.3. Семы 0 нарам а» л 04 Л пебрамымм спермы Гл 1.Фее эю ммюыал «н 11. Лэ юсиа ы на 12 бу ев фуюш н 13 Ныысюмм спэ в В 14.Л:я * и е веню !фин и 13 Бфф нмс еэ сп Г 23 ебр э юсру ур ЭЛ Грую 22 Клюв м а 233 ара«влр в гэюиквю рве 31. Кюб па р ме *е 32 Рывы юи прю ю эным Нюе Г вв4.К!иенс рнфынм» 41. (М мм е ня я а рЮммыы 42.

Эщы ся юр руюв ( уыа! РВФе ( р рефю 43. Лю и п н лы 44 ануэрюяа и м у м н ювн рнФнэ 43 Туеве с(м нп 460 . ю н юсрв Усн еуюур Б Э ю ю 20 162 Юи Нб Юэ 130 130 144 461 161 1Ю 216 И( Юр юг 231 Учебное ввланне Нмредов Виктор Николаевич Оспом Вн торин Ар ад юв КУРС ДНСКРЕТНОН МАТЕМАТИКЕ Редактор Р. М. Бсжесроео Худажествеяимб релмпср Б. Б. Чслномю Текинчжкиа редактор М. Д Жамме Корректор В. сА Л и оооо Обложка хулажвнка 37. П. Елкина ИЕ №!6 Сдано в набор 31.10.90. Поднисаио в печать 01.04.92. Формат ббжрОФ~ Бум.

тип. 79 1 Гарнитура Лижратурвав. Печать вмоскве. Уел. печ. л. 16,6. 3". ~.. ЫБЕ Тщ 29 000 Знквв !й 1629. СЗ. Ивлатель«тао МАИ 12!671. 74оснве, Волоколамское шоссе, 4. Арендное предлрммне Московскан гапон«афин № 8 !07078, Мосина, Кадаичевскнб туп., д 376. УВАЖАЕМЫИ ЧИТАТЕЛЫ В ИЗДАТЕЛЬСТВЕ МАИ В БЛИЖАИШЕЕ ВРЕМЯ ВЫХОДЯТ СЛЕДУЮЩИЕ КИИГИт 1. КУРС НАЧЕРТАТЕЛЫ!Ой ГЕОМЕТРИИ С АЛГОРИТМАМИ ДЛЯ ЭВМ: Учебник для ннж:техн.

вузов/А М. Тевлик, Л. Г. Нартова, В, С Полозов, В. И. Якукиж Под ред. А. М. Тевлнн» н Л. Г. Нэртовой.— М.: Изд-во МАИ, 1992.— 1б л. 2. МЕТОДИЧЕСКОЕ ПОСОБИЕ ПО МАТЕМАТИКЕ ДЛЯ ПОСТУПАЮЩИХ В ВУЗЫ)В. А. Василогва, 1. Д. Кудрина, Р. Н. Молодазскикова) Под ред. Р. Н. Молодожниковой.— М.: Изд-во МАИ, 1992.— З) л. 3.

СБОРНИК ЗАДАЧ ПО МАТЕМАТИКЕ ДЛЯ ПОСТУПАЮ!КИХ В ВУЗЫ: Учеб. пособие/А. С. Бортаковокид, В. М. Закажокин, В. Вб Ссрогид А. М. Скуркдик; Под род. Р. Н. Молодожпиковой.— Мо Изд-во МАИ, !992.— 21 л. 4, Поляков Д. Б., Круглов М Ю. ПРОГРАММИРОВАНИЕ В СРЕДЕ ТУРБО ПАСКАЛЬ (версия 5.5): Справ.-метод чособне.— Мо Изд-во МАИ, 1992.— 45 л. Занзки направлять по адресут 125971, Мосява, Волоколамское шоссе, 4. Издательство МАИ.

Справки по телебонут 155 4б.52. .