Дискретная математика (998286), страница 2
Текст из файла (страница 2)
Представление графов в ЗВМ 7.4.1, Требования к представлению графов... 7.4.2. Матрица смежности 7.4.3. Матрица инциденций 7.4.4. Списки смежности ................. 7.4.5. Массив дуг . 7.4.6. Обходы графов 7.5. Орграфы и бинарные отношения 7.5.1, Графы и отношения 7.5.2. Достижимость и частичное упорядочение 7,5.3. Транзитивное замыкание Комментарии Упражнения ГЛАВА 8. Связность 8.1. Компоненты связности . 8.1.1. Объединение графов и компоненты связности,,......,...,...
8.1.2. Точки сочленения . 8.1.3. Оценка числа ребер через число вершин и число компонент связности 8.2. Вершинная и реберная связность 8.2.1. Мосты и блоки 8.2.2. Меры связности 8.3. Теорема Менгера 8.3.1. Непересекающиеся цепи и разделяющие множества............. 8.3.2. Теорема Мангера в «вершинной форме» 8.3.3. Варианты теоремы Менгера 8.4. Теорема Холла . 8.4.1. Задача о свадьбах 8.4.2. Трансверсаль 8.4.3.
Совершенное паросочетание . 8.4.4. Теорема Холла — формулировка и доказательство............... 8.5. Потоки в сетях . 8.5.1. Определение потока . 8.5.2. Разрезы . 8,5.3. Теорема Форда и Фалкерсона 8.5.4. Алгоритм нахождения максимального потока ...............,... 8.5.5. Связь между теоремой Мангера и теоремой Форда и Фалкерсона... В.Б. Связность в орграфах 8.6.1. Сильная, односторонняя и слабая связность 8.6.2. Компоненты сильной связности 8.6.3, Выделение компонент сильной связности 8.7. Кратчайшие пути 8.7.1. Длина дуг .
8.7.2. Алгоритм Флойда 8.7.3. Алгоритм Дейкстры Комментарии Упражнения ГЛАВА В. Деревья 9.1. Свободные деревья 9.1,1. Определения 199 199 20! 201 201 . 202 . 202 ,203 . 203 .206 . 206 . 206 .207 .208 .209 .210 .2! 0 .210 .211 ,211 .212 .212 .214 .214 .215 .215 . 217 .218 .218 .218 .218 .218 . 220 . 221 .221 .222 .223 .225 .226 .22Б .226 .227 .228 .228 .229 .230 .232 ,232 .234 .234 .234 Содержание ..
235 ..238 ..238 ..240 241 ..242 ..243 ..243 ..244 оченных деревьев ...260 ...260 ...260 ...261 .. 261 ...2БЗ ...263 ...264 ...265 ...2Б5 ...266 ...267 ...268 ...268 ..269 ..269 ..2Б9 ..270 ..270 ........272 множества вершин 272 ..........273 ,,..........274 9.1.2. Основные свойства деревьев .. 9.2.
Ориентированные, упорядоченные и бинарные деревья ...... 9.2.1. Ориентированные деревья . 9.2.2. Эквивалентное определение ордерева . 9.2.3. Упорядоченные деревья 9.2.4. Бинарные деревья . 9,3, Представление деревьев в ЭВМ 9,3,1. Представление свободных, ориентированных и упоряд 9.3.2. Представление бинарных деревьев 9.3.3. Обходы бинарных деревьев 9.3.4.
Алгоритм симметричного обхода бинарного дерева..., 9.4. Деревья сортировки 9.4.1. Ассоциативная память 9.4.2. Способы реализации ассоциативной памяти 9.4,3. Алгоритм бинарного (двоичного) поиска ............. 9.4.4. Алгоритм поиска в дереве сортировки . 9.4.5. Алгоритм вставки в дерево сортировки 9.4.Б. Алгоритм удаления из дерева сортировки 9.4.7. Вспомогательные алгоритмы для дерева сортировки ... 9.4.8. Сравнение представлений ассоциативной памяти 9.4.9. Выровненные деревья 9.4.10. Сбалансированные деревья 9.5. Кратчайший остов 9.5.1.
Определения 9.5.2. Схема алгоритма построения кратчайшего остова 9.5.3. Алгоритм Краскала . Комментарии Упражнения ГЛАВА 10. Циклы 10.1. Фундаментальные циклы и разрезы 10.1.1. Циклы и коциклы 10.1.2. Независимые множества циклов и коциклов 10.1.3. Циклический и коциклический ранг .
10.2. Эйлеровы циклы 10.2.1, Эйлеровы графы 10.2.2. Алгоритм построения зйлерова цикла в зйлеровом графе 10.2.3. Оценка числа эйлеровых графов 10.3. Гамильтоновы шлклы . 10.3.1. Гамильтоновы графы . 10.3.2. Задача коммивояжера Комментарии Уира:кнения ГЛАВА 11.
Независимость и покрытия ! 1.1. Независимые и покрывающие множества 11.1.1. Покрывающие множества вершин и ребер 11.1.2. Независимые множества вершин и ребер . 11,1.3. Связь чисел независимости и покрытий . 11.2. Построение независимых множеств вершин . 11.2.1. Постановка задачи отыскания наибольшего независимого 11.2.2. Поиск с возвратами 11.2.3.
Улучшенный перебор ..246 ..246 ..247 ..248 ..248 ..249 ..250 ..251 ..252 ..253 ..254 ..255 ..256 ..256 ..257 ..259 ..259 одержание Литература Алфавитный указатель 292 11.2.4. Алгоритм построения максимальных независимых множеств вершин 11.3. Доминирующие множества 1! .3.1.
Определения 11.3.2. Доминирование и независимость 11.3.3. Задача о наименьшем покрытии 11.3.4. Эквивалентные формулировки ЗНП 11.3.5. Связь ЗНП с другими задачами Комментарии Упражнения ГЛАВА 12. Раскраска графов 12.1. Хроматическое число 12.2. Планарность ......... 12.2.1. Укладка графов 12.2,2. Эйлерова характеристика . 12.2.3. Теорема о пяти красках 12.3. Алгоритмы раскрашивания 12.3.1. Точный алгоритм раскрашивания 12.3.2.
Приближенный алгоритм последовательного раскрашивания 12.3.3. Улучшенный алгоритм последовательного раскрашивания Комментарии Упршкнения . 276 . 277 .277 . 277 .278 .278 .279 .280 .280 281 . 281 .283 ,283 . 284 . 285 . 286 . 286 .287 .288 .289 .289 Вступительное слово Автор этой книги Ф. А. Новиков имеет большой опыт практического программирования, чтения лекций по дискретной математике и написания книг, посвященных различным вопросам вычислительной техники и ее программного обеспечения. Все это позволило ему создать книгу, наполненную обширным и интересным материалом. Она предназначена для студентов младших курсов, специализирующихся в области программирования, но будет полезна не только им, но и всем тем, кто обучается или стремится повысить квалификацию в направлениях, тесно связанных с программированием, вплоть до аспирантов. Ф.
А Новиков охватывает ряд направлений дискретной математики: теорию множеств и алгебраические структуры, логику и булевы функции, причем затронута даже нетрадиционная проблема автоматического доказательства теорем, комбинаторику и кодирование. Особое внимание уделено общей теории графов — одному из важнейших инструментов программиста, и главным ее приложениям. Вся книга наполнена примерами конкретных алгоритмов от простых до достаточно сложных, особенно во второй половине книге. Это не только полезный учебный материал, но и багаж, который не окажется излишним в будущей практической деятельности учашихся. Книг подобной направленности и с подобным подбором материала в моем поле зрения почти не было.
Книга снабжена списком русскоязычной литературы, из которой читатель сможет извлечь дополнительные сведения по заинтересовавшим его вопросам. Каждый источник из этого списка кратко охарактеризован в конце главы, к которой он относится. Содержание книги во всех ее разделах продуманно и конкретно. Решение автора не включать в книгу такие темы, как теория алгорифмов, надо считать правильным — учебный курс не должен быть перегружен. Книга написана хорошим языком и, можно надеяться, будет благосклонно принята читателем и окажется для него хорошим подспорьем, в частности, при построении математической модели возникшей перед человеком задачи и при выборе подходящего представления данных.
Тому и другому автор уделяет неизменное внимание. Поучительно также краткое, но в большинстве случаев достаточно убедительное, обоснование правильности предлагаемых алгоритмов. Профессор, д.т.н., чл.-корр. РАН С. С Лаеров Введение Назначение и особенности книги Данная книга представляет собой конспективный учебник но дискретной математике, включающий в себя описания важнейших алгоритмов над объектами дискретной математики. Учебник ориентирован на студентов программистских специальностей и практикующих программистов, которым по роду их занятий приходится иметь дело с конструированием и анализом нетривиальных алгоритмов.
В настоящее время имеется масса доступной литературы, покрывающей обе эти темы. С одной стороны, существуют десятки прекрасных книг по дискретной математике, начиная с элементарных учебников для начинающих и кончая исчерпывающими справочниками для специалистов. С другой стороны, большое число монографий, многие из которых стали классическими, посвящены вопросам теории и технологии программирования. Как правило, такие монографии содержат детальное описание и анализ важнейших и известнейших алгоритмов. Однако книги, которые бы рассматривали обе эти темы одновременно и во взаимосвязи, . практически отсутствуют. В качестве редкого исключения можно назвать книгу В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
