Теория графов - основные понятия и определения
Теория графов в задачах и упражнениях применяется достаточно часто, особенно в сложных системах. Узлы здесь отражают отдельные комбинаторные компоненты, а с помощью определенного количества ребер связи между элементами схемы. Моделирование транспортных сетей и массового обслуживания подразумевает использование взвешенных графов.
Потоковая задача
Это достаточно любопытная задача, условие которой следующее: имеется система труб для водопровода.
Ее представляют в виде графов. Каждая дуга отображена в виде трубы. Числа над ними называются весами и обозначают способность пропускать жидкость. Вода протекает в единственном направлении. Требуется сделать максимальным объем вытекающей от источника к истоку воды.
Идея состоит в поиске максимального потока по шагам при условии, что в начале работы он равняется нулю. Далее, он растет с поиском дополняющего пути, куда поступает новый поток. Пока будут существовать дополнительные пути, алгоритм повторяется. Задача применяется в распределенных системах (коммуникации, снабжение, железные дороги).
Планирование сетевого вида
Находит применение теория графов в программировании. Планирование сложных процессов на основе множества параллельно и последовательно выполняемых работ делается через взвешенные графы сети информатики ПЕРТ.
Это ориентированный вариант с ацикличностью и взвешенностью, где каждая дуга является работой, а под весом дуги понимают время исполнения. Каждая вершина является тем моментом времени, к которому требуется завершить все передаваемые дугами работы. В таком случае одна вершина без предшествующих определяет момент старта работ. А та, у которой нет последователей, идет в соответствии со временем окончания комплекса работ.
Максимальная длина между вершинами считается критическим путем. Уменьшение времени исполнения полного комплекса работ лежит в таком ключе: отыскать работы на критическом пути, а затем сократить их длительность.
Добиться этого можно с помощью привлечения новых технологий или дополнительных специалистов.
Алгоритмы решения
Каждый граф может быть решен с помощью алгоритма. Этому посвящен отдельный раздел математики и темы с соответствующими заданиями. Это могут быть алгоритмы Дейкстры, Беллмана и Краскала.
Первыми стоит рассмотреть логические алгоритмы Дейкстры. Они имеют следующие свойства:
- Можно использовать для решения задачи в случае l>0.
- Основаны на приписках вершинам временных меток вида d (vi).
- Метка у оснований дает верхнюю границу длины пути к ней.
- Метки по величине регулярно уменьшаются. Каждая итерация характеризуется тем, что одна из нерегулярных меток становится постоянной. Следовательно, она дает точную величину кратчайшего пути к вершине.
Если требуется решить задачу для различных по знаку и значениям длин, то стоит воспользоваться алгоритмом Беллмана. Здесь необходимо действовать в таком ключе: найти d^<1 (vi) при i=1,2,…, n и продолжать до тех пор, пока не будут выявлены все кратчайшие пути, максимальное число дуг равняется k.
Еще один алгоритм носит имя Краскала.
Решать следующим способом можно, следуя таким шагам структуры:
- На первом шаге нужно упорядочить ребра по возрастанию весов.
- В дерево включают ребро, у которого наличествует минимальный вес.
- Для прочих ребер действует правило: если некоторое ребро не создает цикла с уже включенными, то нужно его либо подключить в дерево, либо исключить.
Заканчивается работа по алгоритму в том случае, когда будут выбраны n-1 ребер. Здесь минимальное оставшееся дерево имеет наименьший вес.
Графы, без сомнения, являются интересной частью дискретной математики. Кажущиеся поначалу сложными, при дальнейшем углублении они сильно помогают решить сложные задачи. Особенно хорошо их применять в тех случаях, когда может потребоваться построить сложную систему электроснабжения или нарисовать электрическую цепь.
Поэтому примеры решения дают возможность не только изучить в реальности и онлайн-классах необходимую информацию, но и позволяют глубже раскрыть математику и овладеть необходимыми навыками построения.
Это касается как программирования, так и гуманитарных наук, где порой требуется применить математический аппарат для упрощения исследований.
