Теория графов

Размещено на http://www.allbest.ru/

Содержание

1. Теория графов

1.1 История создания теории

1.2 Планарные, уникурсальные графы

1.3 Способы описания графов

1.4 Маршруты, деревья

1.5 Оптимальный маршрут на графе

1.6 Остовный граф минимального веса

1. Теория графов

1.1 История создания теории

Первые разрозненные сведения о графах как о схемах в виде наборов точек, соединенных между собой какими-либо линиями, появились в XVIII веке. Одной из первых работ по теории графов можно считать работу всемирно известного математика и механика Леонардо Эйлера (1736), относящуюся к решению головоломок и математических развлекательных задач. граф химический кибернетика

Первые глубокие результаты были получены в 1-й половине 20 в. в связи с решением задач построения электрических цепей и подсчёта химических веществ с различными типами молекулярных соединений. Большая советская энциклопедия: В 30 т. - М.: «Советская энциклопедия», 1969-1978. Но в конце XIX века в связи с развитием топологии значительно возрос интерес к теории графов. В то время она рассматривалась как одна из глав топологии. И широкое развитие теория графов получила лишь с 50-х гг. в связи со становлением кибернетики и развитием вычислительной техники, когда теория существенно обогатилась и новым материалом, и новыми подходами и когда началось систематическое изучение графов с разных точек зрения (структурной, информационной и т. д.). Именно в это время формулировались проблематика и методы теории графов. Дискретная математика. Ч. 2: Теория конечных автоматов. Комбинаторика. Теория графов (для автоматизированной технологии обучения «Символ»): Учебное пособие. Томск: Том. гос. ун-т систем упр. и радиоэлектроники, 2003. -- 130 с.

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

1.2 Планарные, уникурсальные графы

В общем случае граф - это множество V точек, определенным образом соединенных между собой линиями, необязательно прямыми. Точки множества V называются вершинами графа, а соединяющие их линии - ребрами. Вершины графа обычно нумеруют десятичными числами, но можно использовать и любые другие знаки. Если вершины пронумерованы, то ребра обозначают неупорядоченными парами номеров вершин. Каждую пару образуют номера тех вершин, которые соединены ребром Дискретная математика. Ч. 2: Теория конечных автоматов. Комбинаторика. Теория графов (для автоматизированной технологии обучения «Символ»): Учебное пособие. -- Томск: Том. гос. ун-т систем упр. и радиоэлектроники, 2003. -- 130 с.. Вместо отрезков в качестве ребер графов рассматриваются также кривые линии на плоскости (рис. 26, б).

Рис 1. Рёбра графов

Примерами графов могут служить схемы метрополитена, железных и шоссейных дорог, планы выставок и т.д.

Исторически сложилось так, что теория графов зародилась в ходе решения головоломок двести с лишним лет назад. Одной из таких задач-головоломок была задача о кенигсбергских мостах, которая привлекла к себе внимание Леонарда Эйлера (1707-1783), долгое время жившего и работавшего в России (с 1727 по 1741 год и с 1766 до конца жизни).

Задача. В г. Кёнигсберге (ныне Калининград) было семь мостов через реку Прегель (рис. 27, где Л - левый берег, П - правый берег, А и Б - острова). Задача заключалась в следующем: можно ли, прогуливаясь по городу, пройти через каждый мост ровно один раз?

Рис 2. Река Прегель и уникурсальный граф

Эта задача связана с другими головоломками, суть которых заключалась в том, чтобы обвести контур некоторой фигуры, не отрывая карандаша от бумаги и не обводя ни одной линии контура дважды, т.е. «нарисовать одним росчерком». Такие контуры образуют так называемые уникурсальные графы.

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

Теорема. Для уникурсального графа число вершин нечетного индекса равно нулю или двум.

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

Приступим теперь к решению задачи. Определим четность вершин графа на рисунке 28. Вершина А имеет индекс 5, Б - 3, П - 3 и Л - 3. Таким образом, мы имеем четыре вершины нечетного индекса, и, следовательно, данный граф не является уникурсальным. Отсюда получаем, что во время прогулки по городу нельзя пройти по каждому из семи мостов только один раз. Смирнова И.М., Смирнов В.А. Комбинаторные задачи по геометрии.

http://ru.convdocs.org/docs/index-5307.html#71451

Планарный граф - граф, который может быть изображен на плоскости без пересечения ребер. Иначе говоря, граф, для которого существует реализация в виде плоского геометрического графа, называется планарным, и непланарным, если такой реализации не существует. Тюкачёв Н. А. Алгоритм определения принадлежности точки многоугольнику общего вида или многограннику с треугольными гранями / Н.А.Тюкачев // Вестник ТГТУ. т. 15, №3, 2009, с. 638-652. Кафедра «Программирование и информационные технологии», ГОУ ВПО «Воронежский государственный университет»

1.3 Способы описания графов

v Задание графов соответствием

Описание графов состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Соответствием Г называется отображение множества Х в Х, а граф в этом случае обозначается парой G = (X, Г). Отображением вершины хi -- Г(хi) является множество вершин, в которые существуют дуги из вершины хi, т. е. Г(xi) = {xj : (xi, xj) ? A}. Так для орграфа на рис. 1 описание заданием множества вершин и соответствия выглядит следующим образом:

G4=(X, Г), где X = {хi}, I = 1, 2, ..., 4 - множество вершин, Г(х1) = { х2 }, Г(х2) = { х3, х4 }, Г(х3) = { х3 }, Г(х4) = { х1, х2 } - отображения.

Для неориентированного или смешанного графов предполагается, что соответствие Г задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Например, для графа на рис. .2, б Г(х2) = { х1, х3, х5 }, Г(х4) ={ х3, х5} и т. д.

Рис. 1. Рис.2.

v Матричное представление графов.

Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инциденций.

Матрица смежности - это квадратная матрица размерностью n x n, (где n - число вершин графа ), однозначно представляющая его структуру. A = {aij}, i, j = 1, 2, ..., n, а каждый элемент матрицы определяется следующим образом:

aij = 1, если дуга (хi, хj),

aij = 0, если нет дуги (хi, хj).

Если элемент на диагонали (i=j) равен единице, значит, вершина i имеет петлю.

Матрица инциденций представляет собой прямоугольную матрицу размером n x m, где n - количество вершин графа, а m - количество дуг графа. Обозначается матрица инциденций B = {bij}, i = 1, 2, ..., n, j = 1, 2, ..., m. Каждый элемент матрицы определяется следующим образом:

bij = 1, если хi является начальной вершиной дуги aj,

bij = -1, если хi является конечной вершиной дуги aj,

bij = 0, если хi не является концевой вершиной дуги aj или если aj является петлей.

Таким образом, нулевой столбец j в матрице инциденций свидетельствует о том, что дуга aj яляется петлей.

На рис. 3, а, б приведен граф и его матрица смежности, по которой можно найти характеристики вершин. Так сумма элементов i-ой строки матрицы дает полустепень исхода вершины хi, а сумма элементов i-го столбца дает полустепень захода вершины хi. По матрице смежности можно найти прямые и обратные отображения. Рассмотрим i-ю строку матрицы. Если элемент aij=1, то элемент графа хj входит в отображение Г(хi). Например, во 2-й строке матрицы А ( рис. 3,б) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х2) = { х2, х5}.

Рис. 3. Орграф и его матричное представление: а - орграф; б - матрица смежности; в - матрица инциденций

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

Для неориентированного графа, матрица инциденций определяется так же, за исключением того, что все элементы, равные -1, заменяются на 1. Князьков В.С., Волченская Т.В. Введение в теорию графов. Учебный курс. - Интуит. Национальный открытый университет.

1.4 Маршруты, деревья

Пусть граф G содержит множество V вершин и множество Е ребер. Маршрутом длины n называется непустая последовательность n ребер вида

v1, e1, v2, e2, v3, e3, …, vn , en , vn+1, (1)

где ребро ej (j = 1, 2, …, n) соединяет вершины vj и vj+1 Нефедов В.Н. Курс дискретной математики / В.Н. Нефедов, В.А. Осипова.- М.: Изд-во МАИ, 1992. - 264 с.. Очевидно, что в последовательности (1) одни и те же вершины могут повторяться. (Иногда вместо термина «маршрут» используется слово «путь» Фудзисава Т. Математика для радиоинженеров: Теория дискретных структур / Т. Фудзисава, Т. Касами. - М.: Радио и связь, 1984. - 240 с.).

Рис. 1. Пример маршрута

Рассмотрим рисунок 1:

v 1 е1 2 е4 3 е6 3 е2 2 е1 1;

v 2 е2 3 е3 2 е4 3 е7 4;

v 4 е8 1 е5 3 е6 3 е7 4 е7 3 и т. д.

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

Термин «дерево» для особой разновидности графов ввел в 1857 г. английский математик Артур Кэли (1821-1895), с 1870 г. иностранный член-корреспондент Петербургской академии наук. Советский энциклопедический словарь. - М.: Сов. энциклопедия, 1985. - 1600 с.

Связный граф, не содержащий циклов, называется деревом Уилсон Р. Введение в теорию графов. - М.: Мир, 1977. - 207 с.. На рис. 2 приведен трехкомпонентный лес. Первую компоненту образует дерево с вершинами 1,2,3,4, вторую - 5,6,7,8,9, третью - 10,11.

Рис. 2. Трёхкомпонентный лес

Свойства деревьев:

1. Любая пара вершин соединена единственным маршрутом.

2. Количество ребер меньше на одну чем вершин.

3. Удаление хотя бы одного ребра не нарушает его структуру.

4. Если в дерево добавить хотя бы одно ребро то появится цикл.

Дерево называется деревом с корнем, если одна вершина выделена и расположена выше остальных.

Вершины, расположенные под одной вершиной, называется ее сыновьями, а сама вершина отцом.

Вершины, не имеющие сыновей, называются листьями.

Вершины отличные от корня и листьев называют внутренними.

Дерево, корнем которого является одна из вершин данного дерева, называется поддеревом.

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

1.5 Оптимальный маршрут на графе

Принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса. Тюкачёв Н. А. Алгоритм определения принадлежности точки многоугольнику общего вида или многограннику с треугольными гранями / Н.А.Тюкачев // Вестник ТГТУ. т. 15, №3, 2009, с. 638-652. Кафедра «Программирование и информационные технологии», ГОУ ВПО «Воронежский государственный университет»

Для примера возьмем такой ориентированный граф G:

Этот граф мы можем представить в виде матрицы С:

Возьмем в качестве источника вершину 1. Это значит, что мы будем искать кратчайшие маршруты из вершины 1 в вершины 2, 3, 4 и 5.Данный алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины. Рассмотрим этот алгоритм на примере.

Присвоим 1-й вершине метку равную 0, потому как эта вершина -- источник. Остальным вершинам присвоим метки равные бесконечности.

Далее выберем такую вершину W, которая имеет минимальную метку (сейчас это вершина 1) и рассмотрим все вершины в которые из вершины W есть путь, не содержащий вершин посредников. Каждой из рассмотренных вершин назначим метку равную сумме метки W и длинны пути из W в рассматриваемую вершину, но только в том случае, если полученная сумма будет меньше предыдущего значения метки. Если же сумма не будет меньше, то оставляем предыдущую метку без изменений.

После того как мы рассмотрели все вершины, в которые есть прямой путь из W, вершину W мы отмечаем как посещённую, и выбираем из ещё не посещенных такую, которая имеет минимальное значение метки, она и будет следующей вершиной W. В данном случае это вершина 2 или 5. Если есть несколько вершин с одинаковыми метками, то не имеет значения какую из них мы выберем как W.

Мы выберем вершину 2. Но из нее нет ни одного исходящего пути, поэтому мы сразу отмечаем эту вершину как посещенную и переходим к следующей вершине с минимальной меткой. На этот раз только вершина 5 имеет минимальную метку. Рассмотрим все вершины в которые есть прямые пути из 5, но которые ещё не помечены как посещенные. Снова находим сумму метки вершины W и веса ребра из W в текущую вершину, и если эта сумма будет меньше предыдущей метки, то заменяем значение метки на полученную сумму.

Исходя из картинки мы можем увидеть, что метки 3-ей и 4-ой вершин стали меньше, тоесть был найден более короткий маршрут в эти вершины из вершины источника. Далее отмечаем 5-ю вершину как посещенную и выбираем следующую вершину, которая имеет минимальную метку. Повторяем все перечисленные выше действия до тех пор, пока есть непосещенные вершины. Выполнив все действия получим такой результат:

Также есть вектор Р, исходя из которого можно построить кратчайшие маршруты. По количеству элементов этот вектор равен количеству вершин в графе, Каждый элемент содержит последнюю промежуточную вершину на кратчайшем пути между вершиной-источником и конечной вершиной. В начале алгоритма все элементы вектора Р равны вершине источнику (в нашем случае Р = {1, 1, 1, 1, 1}). Далее на этапе пересчета значения метки для рассматриваемой вершины, в случае если метка рассматриваемой вершины меняется на меньшую, в массив Р мы записываем значение текущей вершины W. Например: у 3-ей вершины была метка со значением «30», при W=1. Далее при W=5, метка 3-ей вершины изменилась на «20», следовательно мы запишем значение в вектор Р -- Р[3]=5. Также при W=5 изменилось значение метки у 4-й вершины (было «50», стало «40»), значит нужно присвоить 4-му элементу вектора Р значение W -- P[4]=5. В результате получим вектор Р = {1, 1, 5, 5, 1}.

Зная что в каждом элементе вектора Р записана последняя промежуточная вершина на пути между источником и конечной вершиной, мы можем получить и сам кратчайший маршрут.

1.6 Остовный граф минимального веса

Для лучшего понимания материала сначала рассмотрим задачу на построение остовного графа минимального веса (или минимального остовного дерева). В конце главы представлен общий алгоритм нахождения данного вида графа, а для наглядной демонстрации - алгоритм Борувки. Санкт-Петербургский университет Информационных технологий, Механики и Оптики. Факультет информационных технологий и программирования. Кафедра компьютерных технологий. Дискретная математика: Алгоритмы.

Computer Algorithm Tutor. http://rain.ifmo.ru/cat/view.php/

Постановка задачи

Итак, имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна? Также эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют города, рёбра -- это пары городов, между которыми можно проложить прямую дорогу, а вес ребра равен стоимости строительства соответствующей дороги.

В общем случае, задачу можно сформулировать так. Пусть дан связный, неориентированный граф с весами на ребрах G(V, E), в котором V -- множество вершин (контактов), а E -- множество их возможных попарных соединений (ребер). Пусть для каждого ребра (u,v) однозначно определено некоторое вещественное число w (u,v) -- его вес (длина или стоимость соединения). w(u,v) называется весовой функцией. Задача состоит в нахождении такого связного подграфа T ? G, содержащего все вершины, что суммарный вес его ребер будет минимален.

Так как T связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом (spanning tree). Остовное дерево T, у которого суммарный вес его ребер w(T) = ?(u,v) ? T w(u,v) минимален, называется минимальным остовным или минимальным покрывающим деревом (minimum spanning tree).

Рис.1 Минимальное остовное дерево. Суммарный вес дерева равен 37. Это минимальное остовное дерево не уникально: удалением ребра (c,d) и добавлением ребра (a,b) получается новое минимальное остовное дерево.

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

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

Рассмотрим общую схему работы алгоритмов построения минимального остовного дерева с использованием жадного алгоритма Жадный алгоритм (англ. Greedy algorithm) -- алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Итак, пусть дан связный неориентированный граф G(V;E) c n вершинами и весовая функция w: E > R.

Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграф А исходного графа G, который называется промежуточным остовным лесом. Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое ребро e = (u,v) выбирается так, чтобы не нарушить этого свойства: A ? {e} тоже должно быть подграфом минимального. Такое ребро называется безопасным.

Вот как выглядит общий алгоритм построения минимального остовного дерева в программе Paskal:

MST-GENERIC(G,w)

1: A < 0

2: while (пока) A не является остовом

3: do найти безопасное ребро (u,v) ? E для A

4: A < A ? {(u,v)}

5: return A

По определению A, он должен оставаться подграфом некоторого минимального остова после любого числа повторений. Конечно, главный вопрос состоит в том, как искать безопасное ребро на шаге 3. Понятно, что такое ребро всегда существует, если A еще не является минимальным остовом (любое ребро остова, не входящее в A). Заметим, что так как A не может содержать циклов, то на каждом шаге ребром соединяются различные компоненты связности (изначально все вершины в отдельных компонентах, в конце A - одна компонента). Таким образом цикл выполняется (n-1) раз.

Алгоритм Борувки

Итак, пусть дан связный неориентированный граф G(V;E) и на нем задана весовая функция. Пусть A - промежуточный остовный лес для графа V. На первом шаге A состоит из всех вершин G и пустого множества ребер. В начале очередной фазы алгоритма Борувки, для каждой компоненты связности промежуточного остовного леса выбирается лидер («leader» node, Erickson) или корень - вершина, сопоставляемая каждой компоненте. Сделать это можно в простейшем случае с помощью обхода A в глубину: вершина, с которой начинается обход очередной компоненты, и будет ее лидером. В алгоритме за это отвечает процедура CHOOSE-LEADERS. Лидер для вершины v хранится в переменной leader(v).

После того, как лидеры выбраны, для каждой компоненты связности находится безопасное для нее ребро, по существу методом грубой силы. Это работа процедуры FIND-SAFE_EDGES. Безопасное ребро для лидера v' хранится в переменной safe(v'). Как только все такие ребра отобраны, они добавляются к A. Процесс продолжается до тех пор, пока в A присутствует больше одной компоненты связности.

MST-BORUVKA(G,w)

1: A < (V,0)

2: while (пока) в A больше одной компоненты связности

3: do CHOOSE-LEADERS(A)

4: FIND-SAFE-EDGES(G)

5: foreach (для каждого) лидера v'

6: добавить safe(v') в A

7: return A

Схема работы алгоритма представлена на рисунках Б1-Б5.

Рис. Б1. Начальная фаза. Минимальный покрывающий лес состоит из всех вершин графа и пустого множества ребер.

Рис. Б2. Для каждой компоненты связности (для каждой вершины) находим безопасные ребра. Они отмечены стрелками от компоненты вдоль безопасного ребра.

Рис. Б3. Добавляем безопасные ребра к минимальному остовному лесу.

Рис. Б4. Находим безопасные ребра для каждой компоненты связности.

Рис. Б5. Добавляем найденные ребра. Минимальное остовное дерево построено.

Размещено на Allbest.ru