URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях
Id: 17930
 
1799 руб.

Алгоритмы и программы решения задач на графах и сетях

1990. 520 с. Твердый переплет. ISBN 5-02-028614-1. Букинист. Состояние: 4+. .

 Аннотация

В монографии систематически изложены программно реализованные алгоритмы задач теории графов. Рассмотрены задачи упаковки, покрытия, раскраски, связности и изоморфизма графов, их приложения, в частности, задачи связности случайных графов и изоморфного вложения графов. Алгоритмы оформлены в виде текстов 140 подпрограмм на языках ПЛ-1 и Фортран. Для многих подпрограмм приведены оценки сложности. Обширная терминология теории графов упорядочена в терминологическом словаре. Описан широкий спектр операций над графами, с помощью которых расширен класс решаемых классических и прикладных задач. Показаны варианты сведения этих задач к описанным программам.

Издание предназначено для специалистов, использующих методы теории графов в своей работе, аспирантов и студентов соответствующих специальностей.


 ОГЛАВЛЕНИЕ

От редактора...........................

Предисловие........................

Список обозначений.........................

лава 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........................

 
© URSS 2016.

Информация о Продавце