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