Теория графов
Основные термины теории графов
Многие объекты, возникающие в жизни человека, могут быть смоделированы (представлены в памяти компьютера) при помощи графов. Например, транспортные схемы (схема движения троллейбусов и т. д.) изображают в виде станций, соединенных линиями. В терминах графов станции называются вершинами графа, а линии – ребра.
Графом называется конечное множество вершин и множество ребер. Каждому ребру сопоставлены две вершины – концы ребра.
Бывают различные варианты определения графа. В данном определении концы у каждого ребра – равноправны. В этом случае нет разницы где начало, а где – конец у ребра. Но, например, в транспортных сетях бывают случаи одностороннего движения по ребру, тогда говорят об ориентированном графе – графе, у ребер которого одна вершина считается начальной, а другая – конечной.
Если некоторое ребро u соединяет две вершины A и B графа, то говорят, что ребро u инцидентно вершинам A и B, а вершины в свою очередь инцидентны ребру u. Вершины, соединенные ребром, называются смежными.
Ребра называются кратными, если они соединяют одну и ту же пару вершин (а в случае ориентированного графа – если у них совпадают начала и концы). Ребро называется петлей, если у него совпадают начало и конец. Во многих задачах кратные ребра и петли не представляют интереса, поэтому могут рассматриваться только графы без петель и кратных ребер. Такие графы называю простыми.
Степенью вершины в неориентированном графе называется число инцидентных данной вершине ребер (при этом петля считается два раза, то есть степень - это количество «концов» ребер, входящих в вершину). Довольно очевидно, что сумма степеней всех вершин равна удвоенному числу ребер в графе. Отсюда можно посчитать максимальное число ребер в простом графе - если у графа n вершин, то степень каждой из них равна n−1, а, значит, число ребер есть n(n−1)/2. Граф, в котором любые две вершины соединены одним ребром, называется полным графом.
|
|
Также легко заметить следующий факт – в любом графе число вершин нечетной степени – четно. Этот факт называется «леммой о рукопожатиях» – в любой компании число людей, сделавших нечетное число рукопожатий всегда четно.
Пути, циклы, компоненты связности
Путем на графе называется последовательность ребер u1, u2, …, uk, в которой конец одного ребра является началом следующего ребра. Начало первого ребра называется началом пути, конец последнего ребра - концом пути. Если начало и конец пути совпадают, то такой путь называется циклом.
Путь, который проходит через каждую вершину не более одного раза называется простым путем. Аналогично определяется простой цикл.
Граф называется связным, если между любыми двумя его вершинами есть путь. Если граф несвязный, то его можно разбить на несколько частей (подграфов), каждая из которых будет связной. Такие части называются компонентами связности. Возможно, что некоторые компоненты связности будут состоять всего лишь из одной вершины.
Понятно, что в графе из n вершин может быть от 1 до n компонент связности.
Способы представления графов в памяти
Граф может быть представлен (сохранен) несколькими способами:
· матрица смежности;
· матрица инцидентности;
· список смежности (инцидентности);
|
|
· список ребер.
Использование двух первых методов предполагает хранение графа в виде двумерного массива (матрицы). Размер массива зависит от количества вершин и/или ребер в конкретном графе.
Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.
Число строк матрицы смежности равно числу столбцов и соответствует количеству вершин графа.
· 0 – соответствует отсутствию ребра,
· 1 – соответствует наличию ребра.
Когда из одной вершины в другую проход свободен (имеется ребро), в ячейку заносится 1, иначе – 0. Все элементы на главной диагонали равны 0 если граф не имеет петель.
Матрица инцидентности (инциденции) графа — это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер. В ней указываются связи между инцидентными элементами графа (ребро(дуга) и вершина).
В неориентированном графе если вершина инцидентна ребру то соответствующий элемент равен 1, в противном случае элемент равен 0.
В ориентированном графе если ребро выходит из вершины, то соответствующий элемент равен 1, если ребро входит в вершину, то соответствующий элемент равен -1, если ребро отсутствует, то элемент равен 0.
Матрица инцидентности для своего представления требует нумерации рёбер, что не всегда удобно.
Список смежности (инцидентности)
Если количество ребер графа по сравнению с количеством вершин невелико, то значения большинства элементов матрицы смежности будут равны 0. При этом использование данного метода нецелесообразно. Для подобных графов имеются более оптимальные способы их представления.
|
|
По отношению к памяти списки смежности менее требовательны, чем матрицы смежности. Такой список можно представить в виде таблицы, столбцов в которой – 2, а строк — не больше, чем вершин в графе.
В каждой строке в первом столбце указана вершина выхода, а во втором столбце – список вершин, в которые входят ребра из текущей вершины. 
Преимущества списка смежности:
· Рациональное использование памяти.
· Позволяет быстро перебирать соседей вершины.
· Позволяет проверять наличие ребра и удалять его.
Недостатки списка смежности:
· При работе с насыщенными графами (с большим количеством рёбер) скорости может не хватать.
· Нет быстрого способа проверить, существует ли ребро между двумя вершинами.
· Количество вершин графа должно быть известно заранее.
· Для взвешенных графов приходится хранить список, элементы которого должны содержать два значащих поля, что усложняет код:
o номер вершины, с которой соединяется текущая;
o вес ребра.
Список рёбер
В списке рёбер в каждой строке записываются две смежные вершины и вес соединяющего их ребра (для взвешенного графа).
Количество строк в списке ребер всегда должно быть равно величине, получающейся в результате сложения ориентированных рёбер с удвоенным количеством неориентированных рёбер.
Какой способ представления графа лучше? Ответ зависит от отношения между числом вершин и числом рёбер. Число ребер может быть довольно малым (такого же порядка, как и количество вершин) или довольно большим (если граф является полным). Графы с большим числом рёбер называют плотными, с малым — разреженными. Плотные графы удобнее хранить в виде матрицы смежности, разреженные — в виде списка смежности.
Алгоритмы обхода графов
Основными алгоритмами обхода графов являются
· Поиск в ширину
· Поиск в глубину
Поиск в ширину подразумевает поуровневое исследование графа:
· вначале посещается корень – произвольно выбранный узел,
· затем – все потомки данного узла,
· после этого посещаются потомки потомков и т.д.
Вершины просматриваются в порядке возрастания их расстояния от корня.
Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения требуемого условия (например, найти кратчайший путь из вершины 1 в вершину 6).
Каждая вершина может находиться в одном из 3 состояний:
· 0 — оранжевый – необнаруженная вершина;
· 1 — зеленый – обнаруженная, но не посещенная вершина;
· 2 — серый – обработанная вершина.
Фиолетовый – рассматриваемая вершина.
Применения алгоритма поиска в ширину
· Поиск кратчайшего пути в невзвешенном графе (ориентированном или неориентированном).
· Поиск компонент связности.
· Нахождения решения какой-либо задачи (игры) с наименьшим числом ходов.
· Найти все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин.
· Найти все вершины, лежащие на каком-либо кратчайшем пути между заданной парой вершин.
Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах.
Для реализации алгоритма удобно использовать очередь.