Теория графов - основные понятия и определения

С ее помощью можно решить ряд сложных практических и теоретических заданий, а также выстроить грамотную математическую модель.

Основы и определения

Теория графов основные понятия и определения начала формулировать в XVIII веке. Именно тогда великий математик Леонард Эйлер сумел решить первую в историю задачу о кенигсбергских мостах. Теория систематически и последовательно ведет изучение свойств графов. Они имеют в составе множество точек и линий.

Основы теории графов всегда начинают с рассмотрения математических определений. Первое из них говорит о том, что они есть система вершин и ребер, которые соединяют объекты.

Во втором рассматривается случай, где V есть множество вершин, а v — вершины.

Граф типа G=G (V) с множеством вершин представляет собой некоторое семейство пар e=(a, b).

Указанные точки являются свидетельством того, какие из вершин считают соединенными. Каждая из пар является графовым ребром.

Далее, необходимо рассмотреть основные определения согласно представлениям дискретной математики:

• Смежными называют те вершины, которые имеют соединение в виде ребер.
• Соединяемые этим способом вершины являются инцидентными по отношению к ребру.
• Число инцидентных ребер указывает на вершинную степень.
• В простом графе двойное число ребер равняется степенной сумме.
• Для простого элемента странный парадокс: четное количество вершин равно нечетной степени.

В последние десятилетия развитию теории способствуют новые интенсивные математические разработки. Также появились новые степени приложения графов, включая биологию и программирование.

Типы графов

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

1. Через перечисление вершин с ребрами.
2. Изображение графическим методом.
3. Матрицы, смежные для вершин по таблицам.
4. Инцидентные матрицы.

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

Также существует следующая классификация:

• Пустой, где каждая вершина имеет нулевую степень.
• Тривиальный состоит из одной вершины.
• Полным считают такой элемент, в котором смежны каждые две вершины.
• Если все основания имеют одинаковую степень r, то граф называют регулярный, у которого степень r. При степени, равной 3, он становится кубическим.
• Когда много вершин грани можно делить на два подмножества, которые не будут пустыми и пересекающимися так, чтобы каждое ребро присоединяло вершины из разных подмножеств, то это двудольный граф.
• Полным двудольным является тот граф, который позволяет соединить между собой вершины у каждого подмножества.
• Граф считается звездой, когда мощность одного из подмножеств составляет единицу.

Также существуют такие разновидности, как дерево и лес. Первая представляет собой связный граф без циклов, а вторая является графом без циклов и связей.

Практические задачи

Теория графов в задачах и упражнениях применяется достаточно часто, особенно в сложных системах. Узлы здесь отражают отдельные комбинаторные компоненты, а с помощью определенного количества ребер связи между элементами схемы. Моделирование транспортных сетей и массового обслуживания подразумевает использование взвешенных графов.

Потоковая задача

Это достаточно любопытная задача, условие которой следующее: имеется система труб для водопровода.

Ее представляют в виде графов. Каждая дуга отображена в виде трубы. Числа над ними называются весами и обозначают способность пропускать жидкость. Вода протекает в единственном направлении. Требуется сделать максимальным объем вытекающей от источника к истоку воды.

Идея состоит в поиске максимального потока по шагам при условии, что в начале работы он равняется нулю. Далее, он растет с поиском дополняющего пути, куда поступает новый поток. Пока будут существовать дополнительные пути, алгоритм повторяется. Задача применяется в распределенных системах (коммуникации, снабжение, железные дороги).

Планирование сетевого вида

Находит применение теория графов в программировании. Планирование сложных процессов на основе множества параллельно и последовательно выполняемых работ делается через взвешенные графы сети информатики ПЕРТ.

Это ориентированный вариант с ацикличностью и взвешенностью, где каждая дуга является работой, а под весом дуги понимают время исполнения. Каждая вершина является тем моментом времени, к которому требуется завершить все передаваемые дугами работы. В таком случае одна вершина без предшествующих определяет момент старта работ. А та, у которой нет последователей, идет в соответствии со временем окончания комплекса работ.

Максимальная длина между вершинами считается критическим путем. Уменьшение времени исполнения полного комплекса работ лежит в таком ключе: отыскать работы на критическом пути, а затем сократить их длительность.

Добиться этого можно с помощью привлечения новых технологий или дополнительных специалистов.

Алгоритмы решения

Каждый граф может быть решен с помощью алгоритма. Этому посвящен отдельный раздел математики и темы с соответствующими заданиями. Это могут быть алгоритмы Дейкстры, Беллмана и Краскала.

Первыми стоит рассмотреть логические алгоритмы Дейкстры. Они имеют следующие свойства:

• Можно использовать для решения задачи в случае l>0.
• Основаны на приписках вершинам временных меток вида d (vi).
• Метка у оснований дает верхнюю границу длины пути к ней.
• Метки по величине регулярно уменьшаются. Каждая итерация характеризуется тем, что одна из нерегулярных меток становится постоянной. Следовательно, она дает точную величину кратчайшего пути к вершине.

Если требуется решить задачу для различных по знаку и значениям длин, то стоит воспользоваться алгоритмом Беллмана. Здесь необходимо действовать в таком ключе: найти d^<1 (vi) при i=1,2,…, n и продолжать до тех пор, пока не будут выявлены все кратчайшие пути, максимальное число дуг равняется k.

Еще один алгоритм носит имя Краскала.

Решать следующим способом можно, следуя таким шагам структуры:

1. На первом шаге нужно упорядочить ребра по возрастанию весов.
2. В дерево включают ребро, у которого наличествует минимальный вес.
3. Для прочих ребер действует правило: если некоторое ребро не создает цикла с уже включенными, то нужно его либо подключить в дерево, либо исключить.

Заканчивается работа по алгоритму в том случае, когда будут выбраны n-1 ребер. Здесь минимальное оставшееся дерево имеет наименьший вес.

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

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

Это касается как программирования, так и гуманитарных наук, где порой требуется применить математический аппарат для упрощения исследований.