- •Изоморфизм
- •Матричное задание графа
- •Свойства матрицы смежности
- •Операции над графами
- •Достижимость и связность
- •Матрицы достижимости и контрдостижимости
- •Нахождение сильных компонент
- •Конденсация графа
- •Базы и антибазы
- •Построение компонент связности в неориентированном графе
- •Построение компонент связности в ориентированном графе
- •Система независимых циклов
- •Дерево. Остов граф
- •Процесс восстановления дерева по набору
- •Алгоритм построения произвольного остова
- •Определение минимального остова
- •Алгоритм построения системы независимых циклов графа
- •Модификация Форда
- •Алгоритмы поиска всех кратчайших путей
- •Алгоритм Флойда
- •Алгоритм Флойда
- •Алгоритм Данцига
- •Алгоритм Данцига
- •Раскраска
- •Метод построения функции Гранди на графе
- •Гамильтоновы пути, контуры и задача Коммивояжера
- •Метод Роберта и Флореса (перебор-метод для орграфов)
- •Алгоритм поиска увеличивающего пути
- •Алгоритм поиска максимального потока
- •Алгоритм Форда и Фалкерсона
- •Модификация алгоритма поиска максимального потока при нескольких источниках и стоках
- •Алгоритм поиска потока минимальной стоимости
- •Алгоритм поиска потока минимальной стоимости
- •Алгоритмы построения покрывающих деревьев
Графы. Основные понятия и определения.
Граф - первичное понятие. Граф задается двумя множествами: множеством вершин и множеством рёбер. Пример задания графа: G=G(X,A).
Если ребра графа ориентированы, то и сам граф ориентированный. Ребра-дуги. Если же ребра не ориентированы, то и сам граф является неориентированным.
В случае, когда мы имеем ориентированный граф, но пренебрегаем ориентацией его дуг, то мы называем его ориентированным дубликатом G=G(X,Ā)
Второй тип задания графа - задание множества вершин Х и отображение множества во множество Х. G=G(X, Г)
Если граф не ориентированный, и мы хотим представить его 2-м способом, то необходимо каждое ребро заменить 2 дугами, противоположно направленными .
Две вершины xi и xj называются граничными дуги, если xi – начало, а xj – конец. Эти вершины называются смежными.
Две дуги аi и аj – смежные, если они различны, но имеют общую граничную точку.
Вершина изолирована, если она не соединена с другими вершинами графа.
Говорят, что дуга аi исходит из вершины xi , если xi начало, а не конец, и дуга заходит в вершину хi , если хi является концом дуги аі, но не является началом
Общее число дуг, инцидентных вершине xi, является степенью вершины и обозначается .
Вершины, степень которых больше 2, называются узлами.
Полустепень захода обозначает количество дуг, заходящих в вершину xi, и обозначается .
Полустепень исхода обозначает количество дуг, исходящих из вершины xi и обозначается .
Вершина xi называется входом, если , а .
Последовательность линий на графе.
Путем в графе называется такая последовательность дуг , в которой конец предыдущей дуги является началом последующей. Путь может быть конечным и бесконечным. Путь простой, если в нем ни одна дуга не встречается дважды. Путь составной, если в нем какая-либо из дуг встречается более одного раза.
Путь, проходящий через все вершины только 1 раз, называется Гамильтоновым.
Путь, содержащий все дуги графа по одному разу, называется Эйлеровым.
Длина пути – это число дуг последовательности
Ветвь – это путь, в котором начальная и конечная вершины являются узлами.
Дуга называется замыкающей, если ее удаление из графа не приведет к аннулированию пути
Контур- это конечный путь, начинающийся и заканчивающийся одной и той же вершиной.
Контур единичной длины называется петлей.
На контур распространяются все определения, введенные для пути.
Все раннее приведенные понятия, рассмотрены на примере ориентированных графов.
В случае неориентированных графов, существуют аналогичные понятие, которые имеют другие названия.
Ориентированный граф |
Неориентированный граф |
Дуга |
Ребро |
Путь |
Цепь |
Контур |
Цикл |
Виды графов
G=G(X, A) - нуль-граф, если он состоит только из изолированных вершин. Если степень всех вершин графа одинакова, то этот граф однородный.
Граф G(X,A), в котором любые две смежные вершины соединены двумя противоположно ориентированными дугами, называется симметрическим
Граф G(X, A) без петель, в котором каждая пара вершин соединена одинаковым количеством дуг, называется полным. Так как каждая вершина полного графа соединена дугой с остальными вершинами, то степени всех вершин полного графа получаются одинаковыми. Обратное этому утверждение не верно. Кол-во его дуг m=0.5nr n-кол-во В. r – степень В
В полном графе всегда имеется Гамильтонов путь.
Если хотя бы 2 вершины соединены более чем 1 дугой (ребром), то это мультиграф. Наибольшее количество дуг (ребер), соединяющих смежные вершины в мультиграфе, называется его кратностью.
Мультиграф Р-граф, Р-кратность.
Изоморфизм
Два графа G1 и G2 – изоморфные, если существует взаимнооднозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые 2 вершины в графе G1 , равно числу ребер соединяющих соответствующие вершины в графе G2
Для ориентированных графов еще необходимо выполнение условия .
Граф, который можно изобразить на плоскости так, чтобы 2 ребра не пересекались в точках, отличных от вершин, называется плоским графом.
Грань плоского графа - область плоскости, ограниченная ребрами и не содержащая в себе ни вершин, ни ребер. Число граней находится по формуле , где m-число ребер, а n-число вершин графа.
Неограниченная область плоскости, лежащая за пределами графа, называется бесконечной гранью. Все остальные грани - конечные.
Две грани смежные, если их края имеют хотя бы одно общее ребро. Грани, которые соприкасаются в отдельных вершинах - не смежные.
Для плоского графа можно построить двойственный ему граф G*, используя 3 правила:
Определить число граней исходного графа с учетом внешней грани.
В каждой грани графа G ставится вершина графа G*. Петля исходного графа рассматривается как грань.
Вершина графа G* соединяется ребрами в том случае, если они лежат на гранях, имеющих общее ребро, причем ребро, соединяющее эти 2 вершины двойственного графа, должно обязательно проходить через общее ребро исходного графа. Если у 2 граней, на которых лежат вершины графа G* , имеется несколько общих ребер, то эти вершины соединяются столькими ребрами, сколько общих ребер имеет грань. Это справедливо как для внешних, так и для внутренних граней. Висячему ребру исходного графа соответствует петля в графе G*, которая проведена из вершины внешней грани двойственного графа таким образом, чтобы висячая вершина оказалась внутри этой петли Подмножество графов
Подграфом графа G(X,Г) называется граф G(B, ГВ), определяемый следующим образом:
Множество вершин В подграфа являются некоторым подмножеством вершин графа G(X, Г), .
Отображением каждой вершины подграфа является пересечение отображения той же вершины графа G(X,Г) со всем подмножеством вершин В, .
В этом примере мы изобразим схему построения подграфа G(B,ГВ) для заданного графа G(X,Г)
Задание: «Построить подграф ». Иллюстрация этой задачи приведена выше.
Частичным графом для графа G(X, Г) называется граф G(X, F), в котором содержатся все вершины исходного графа и некоторое подмножество дуг исходного графа . То есть, от исходного графа сохраняются вершины и некоторые дуги.
Частичным подграфом графа G(X, Г) называется граф G(B, Г), в котором вершины В являются подмножеством вершин Х, а отображение F меньше пересечения отображений исходного графа со всеми вершинами частичного подграфа G(B, F), то есть:
Фактором графа G(X,Г) называется частичный граф, в котором каждая вершина обладает полустепенями захода и исхода равными 1.
Базисным графом называется ориентированный частичный граф, образованный из исходного удалением петель и замыкающих дуг