От редактора........................... Предисловие........................ Список обозначений......................... лава 1. Графы, их применение и сложность решения задач 1.1. Термины и определения..................... 1.2. Сложность алгоритмов..................... 1.2.1. Основные понятия (16). 1.2.2. Максимальный поток в сети (17). 1.2.3. Максимальное паросочетание (18). 1.2.4. Минимальное остовное дерево (19). 1.2.5. Кратчайший путь (20). 1.2.6. Изоморфизм графов (21). 1.2.7. Топологические свойства графов (24)... 1.3. Теоретико-графовые модели систем............... 1.3.1. Задача о кратчайшей цепи и ее приложения (25). 1.3.2. Задача о максимальном потоке и ее приложения (27). 1.3.3. Задачи об упакоз-ках ипокрытинх и их приложения (31). 1.3.4. Раскраска в графах (33). 1.3.5. Связность графов и сетей (34). 1.3.6. Изоморфизм графов и сетей (36). 1.3.7. Изоморфное вхождение и пересечение графов (40). 1.3.8. Автоморфизм графов (42). Глава 2. Операции над графами 2.1. Представление графов..................... 2.1.1. Базовые представления (45). 2.1.2. Преобразование базовых представлений (46). 2.1.3. Структура входных и выходных данных в подсистеме анализа изоморфизма графов и сетей (47). 2.2. Генерация графов...................... 2.2.1. Генерация изоморфных графов (50). 2.2.2. Систематическая генерация графов (53). 2.2.3. Генерация случайных графов (55). 2.3. Преобразование графов.................... 2.3.1. Теоретико-множественные операции (56). 2.3.2. Алгебраические операции над графами (57). 2.3.3. Специальные теоретико-графовые операции (58). Глава 3. Сети и задачи оптимизации 3.1. Метрика и пути в графах................... 3.1.1. Кратчайшие цепи и расстояния (64). 3.1.2. Кратчайшие пути с дополнительными условиями и ограничениями (671. 3.1.3. Задачи размещения и метрические характеристики графов (70). 3.2. Потоки в сетях........................ 3.2.1. Поиск максимальных потоков в сетях (74). 3.2.2. Потоки и их стоимость (78). лава 4. Части графов с заданными свойствами 4.1. Упаковки и покрытия..................... 4.1.1. Классификация задач упаковок и покрытий в графах и сетях (82). 4.1.2. Задачи покрытия в обыкновенных графах (85). 4.1.3. Задачи покрытия во взвешенных графах (87). 4.1.4. Задачи упаковки в обыкновенных графах (89). 4.1.5. Наибольшая упаковка во взвешенных графах (90).......... 4.2. Раскраски........................... 4.2.1. Точная раскраска вершин графа (92). 4.2.2. Приближенная раскраска (93). 4.2.3. Реберная раскраска (95). 4.2.4. Оценки хроматического числа (95). 4.2.5. Специальная раскраска (96). 4.2.6. Раскраска специальных графов (96)...
Глава 5. Связность
5.1. Достижимость, соединимость и отделимость..........
5.1.1. Достижимость (98). 5.1.2. Отделимость (102). 5.1.3. Соединимость (107). 5.1.4. Реберная соединимость (110).
5.2. Случайные графы.......................
5.2.1. Анализ случайных графов (113). 5.2.2. Вычисление вероятности связности (114). 5.2.3. Характеристики связности случайного графа (118). 5.2.4. Оптимальные случайные графы (121).
Глава 6. Изоморфизм, изоморфное вложение и пересечение
6.1. Изоморфизм графов и сетей..................
6.1.1. Два подхода к разработке алгоритмов (123). 6.1.2. Распознавание изоморфизма непереборным методом (137). 6.1.3. Распознавание изоморфизма методом направленного перебора (141).
6.2. Изоморфное вложение....................
6.2.1. Задачи распознавания изоморфного вложения (144).
6.2.2. Алгоритм распознавания изоморфного вложения (145).
6.2.3. Модули для распознавания изоморфного вложения (149).
6.3. Изоморфное пересечение...................
6.3.1. Задачи определения изоморфного пересечения (151).
6.3.2. Алгоритмы определения максимального изоморфного пересечения (152). 6.3.3. Модули для определения максимального изоморфного пересечения (156).
Глава 7. Симметрия
7.1. Алгебраические задачи в теории графов.............
7.1.1. Прикладные задачи (158). 7.1.2. Задачи построения характери-зации и исследования групп автоморфизмов (160).
7.1.3. Задачи перечисления (165). 7.1.4. Задачи классификации графов на основе свойств регулярности и симметрии (168)
7.1.5. Задачи построения графов и генерации семейств (172).
7.1.6. Задачи различения графов на основе инвариантов (176).
7.2. Сокращение перебора на основе симметрии при решении NP-полных задач на графах..........................
7.2.1. Методы поиска, использующпе дерево решений (181).
7.2.2. Задачи определения V- и Е-соединимости (184).
Список литературы.........................
Словарь терминов и определений...................
Приложение............................
Программы к главе 2........................
Программы к главе 3........................
Программы к главе 4........................
Программы к главе 5.........................
Программы к главе 6.........................
Программы к главе 7........................
|
2023. 720 с. Твердый переплет. 16.9 EUR
Книга «Зияющие высоты» – первый, главный, социологический роман, созданный интеллектуальной легендой нашего времени – Александром Александровичем Зиновьевым (1922-2006), единственным российским лауреатом Премии Алексиса де Токвиля, членом многочисленных международных академий, автором десятков логических... (Подробнее) URSS. 2024. 800 с. Мягкая обложка. 37.9 EUR
ВЕРСАЛЬ: ЖЕЛАННЫЙ МИР ИЛИ ПЛАН БУДУЩЕЙ ВОЙНЫ?. 224 стр. (ТВЁРДЫЙ ПЕРЕПЛЁТ) 11 ноября 1918 года в старом вагоне неподалеку от Компьеня было подписано перемирие, которое означало окончание Первой мировой войны. Через полгода, 28 июня 1919 года, был подписан Версальский договор — вердикт, возлагавший... (Подробнее) 2023. 696 с. Твердый переплет в суперобложке. 119.9 EUR
Опираясь на новейшие исследования, историк Кристофер Кларк предлагает свежий взгляд на Первую мировую войну, сосредотачивая внимание не на полях сражений и кровопролитии, а на сложных событиях и отношениях, которые привели группу благонамеренных лидеров к жестокому конфликту. Кларк прослеживает... (Подробнее) URSS. 2024. 704 с. Твердый переплет. 26.9 EUR
В новой книге профессора В.Н.Лексина подведены итоги многолетних исследований одной из фундаментальных проблем бытия — дихотомии естественной неминуемости и широчайшего присутствия смерти в пространстве жизни и инстинктивного неприятия всего связанного со смертью в обыденном сознании. Впервые... (Подробнее) URSS. 2024. 344 с. Мягкая обложка. 18.9 EUR
Мы очень часто сталкиваемся с чудом самоорганизации. Оно воспринимается как само собой разумеющееся, не требующее внимания, радости и удивления. Из случайно брошенного замечания на семинаре странным образом возникает новая задача. Размышления над ней вовлекают коллег, появляются новые идеи, надежды,... (Подробнее) URSS. 2023. 272 с. Мягкая обложка. 15.9 EUR
Настоящая книга посвящена рассмотрению базовых понятий и техник психологического консультирования. В ней детально представлены структура процесса консультирования, описаны основные его этапы, содержание деятельности психолога и приемы, которые могут быть использованы на каждом из них. В книге... (Подробнее) URSS. 2024. 576 с. Мягкая обложка. 23.9 EUR
Эта книга — самоучитель по военной стратегии. Прочитав её, вы получите представление о принципах военной стратегии и сможете применять их на практике — в стратегических компьютерных играх и реальном мире. Книга состоит из пяти частей. Первая вводит читателя в мир игр: что в играх... (Подробнее) URSS. 2024. 248 с. Мягкая обложка. 14.9 EUR
В книге изложены вопросы новой области современной медицины — «Anti-Ageing Medicine» (Медицина антистарения, или Антивозрастная медицина), которая совмещает глубокие фундаментальные исследования в биомедицине и широкие профилактические возможности практической медицины, а также современные общеоздоровительные... (Подробнее) URSS. 2024. 240 с. Твердый переплет. 23.9 EUR
Предлагаемая вниманию читателей книга, написанная крупным биологом и государственным деятелем Н.Н.Воронцовым, посвящена жизни и творчеству выдающегося ученого-математика, обогатившего советскую науку в области теории множеств, кибернетики и программирования — Алексея Андреевича Ляпунова. Книга написана... (Подробнее) 2023. 416 с. Твердый переплет. 19.9 EUR
Вам кажется, что экономика — это очень скучно? Тогда мы идем к вам! Вам даже не понадобится «стоп-слово», чтобы разобраться в заумных формулах — их в книге нет! Все проще, чем кажется. Автор подаст вам экономику под таким дерзким соусом, что вы проглотите ее не жуя! Вы получите необходимые... (Подробнее) |