Кирсанов М.Н. Графы в Maple: задачи, алгоритмы, программы

Опубликовал: pvi777 в категорию Материалы по Maplesoft Maple - Дата добавления: 21.09.2020, 00:30


Теория графов – один из разделов современной математики, имеющий большое прикладное значение. Проблемы оптимизации тепловых, газовых и электрических сетей, вопросы совершенствования алгоритмов и создание новых химических соединений связаны с фундаментальными свойствами таких абстрактных математических объектов, как графы. Долгое время задачи теории графов решались вручную, с появлением компьютеров появилась возможность написания специальных программ на алгоритмических языках. Позднее появились пакеты аналитических вычислений Mathematica, MATLAB, Mathcad и Maple, позволяющие выполнять аналитические символьные пре¬образования. Для решения задач, объектами которых являются графы, эти пакеты просто незаменимы. В системе Maple есть еще и специализированная библиотека networks, составленная из операторов для работы с графами. Таких операторов немного – всего 66, и число это в Maple не меняется от версии к версии. Появилась проблема – описать пакет networks и дать примеры решения задач с его помощью. Решению этой проблемы и посвящена данная книга.

В первой части книги даны сведения из теории и решения некоторых основных задач теории графов. Во второй части содержатся готовые программы, разработанные автором как с привлечением операторов и команд пакета networks, так и решенные независимым образом на языке Maple. В книге описаны почти все команды и процедуры пакета теории графов networks. Исключение составляют только вероятностные задачи на графах. Кроме того, добавлены некоторые новые собственные процедуры. В частности, введена процедура рисования орграфа. При выборе стиля программирования автор добивался ясности изложения алгоритма, иногда даже в ущерб краткости и скорости работы программы. Совершенствование программ предлагается читателям, тем более, что данная книга – учебник, а учиться лучше всего, программируя самому и убеждаясь, что «моя программа лучше!». Желаем читателям успехов в этом!

СОДЕРЖАНИЕ

Предисловие

Глава 1. Неориентированные графы
1.1. Радиус и диаметр графа. Эйлерова цепь
1.2. Реберный граф
1.3. Хроматический полином
1.4. Ранг-полином графа
1.5. Циклы

Глава 2. Ориентированные графы
2.1. Маршруты в орграфе
2.2. Транзитивное замыкание
2.3. Компоненты сильной связности графа

Глава 3. Деревья
3.1. Центроид дерева
3.2. Десятичная кодировка
3.3. Кодировка Прюфера
3.4. Распаковка кода Прюфера
3.5. Кодировка Гапта
3.6. Распаковка кода Гапта

Глава 4. Алгоритмы
4.1. Кратчайший путь в орграфе
4.2. Поток в сети
4.3. Топологическая сортировка сети
4.4. Паросочетание в двудольном графе
4.5. Задача о назначениях
4.6. Остов наименьшего веса
4.7. Гамильтоновы циклы
4.8. Задача коммивояжера

Глава 5. Maple-программы
5.1. Радиус и диаметр графа
5.2. Реберный граф
5.3. Хроматический полином
5.4. Ранг-полином графа
5.5. Циклы в неографе
5.6. Матрица инцидентности
5.7. Транзитивное замыкание
5.8. Компоненты сильной связности графа
5.9. Пути в орграфе
5.10. Изображение орграфа
5.11. Кратчайший путь в орграфе
5.12. Центроид дерева
5.13. Десятичная кодировка
5.14. Распаковка десятичного кода
5.15. Кодировка Прюфера
5.16. Распаковка кода Прюфера
5.17. Код Гапта
5.18. Распаковка кода Гапта
5.19. Поток в сети
5.20. Топологическая сортировка сети
5.21. Паросочетание
5.22. Задача о назначениях
5.23. Остов наименьшего веса
5.24. Фундаментальные циклы
5.25. Гамильтоновы циклы
5.26. Муравьиный алгоритм
5.27. Алгоритм отжига
5.28. Основные функции пакета networks

Список литературы
Предметный и именной указатель


Скачать:


  • Теги:

Комментарии:


Оставить комментарий

Вход на сайт

Информация о проекте

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

Контакты