10 алгоритмов на графах в гифках

Оглавление (нажмите, чтобы открыть):

Графы. Обход графов в ширину и глубину.

Граф – это множество однотипных объектов (вершин), некоторые из которых связаны друг с другом какими-либо связями (ребрами). Одна связь всегда соединяет только две вершины (иногда – вершину саму с собой). Основные разновидности графов:

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

Примеры графов разных типов:

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

Недостатки данного способа:

  • заранее надо знать хотя бы ориентировочное число вершин в графе
  • для графов с большим числом вершин матрица становится слишком большой (например 1000*1000 = 1 миллион чисел)
  • при малом числе связующих ребер матрица заполнена в основном нулями

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

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

  • добавление новой связи (ребра) между заданной парой существующих вершин
  • добавление новой вершины вместе со всеми необходимыми связями
  • удаление связи (ребра) между двумя вершинами
  • удаление вершины вместе со всеми ее связями

Добавление нового ребра включает в себя (на примере обычного графа):

  • получение имен связываемых вершин
  • поиск в основном списке первой связываемой вершины
  • поиск в списке смежных ей вершин второй связываемой вершины и либо вывод сообщения об ошибке, либо добавление в этот список нового элемента с именем второй вершины
  • поиск в основном списке второй связываемой вершины
  • поиск в списке смежных ей вершин первой связываемой вершины и либо вывод сообщения об ошибке, либо добавление в этот список нового элемента с именем первой вершины

Добавление новой вершины включает в себя:

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

Удаление ребра производится следующим образом:

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

Удаление вершины производится следующим образом:

  • запрос имени удаляемой вершины
  • поиск ее в основном списке
  • просмотр вспомогательного списка удаляемой вершины, для каждого элемента которого:
    • поиск смежной вершины в основном списке и удаление из ее вспомогательного списка элемента, соответствующего удаляемой вершине
    • удаление самого элемента из вспомогательного списка
  • удаление вершины из основного списка

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

Обход в глубину

Поиск в глубину использует две структуры – стек для запоминания еще не обработанных вершин и список для запоминания уже обработанных. Поиск выполняется следующим образом:

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

Например, для рассмотренного выше обычного графа получим:

      • пусть стартовая вершина – B
      • включаем B в список обработанных вершин: список = (В)
      • помещаем в стек смежные с В вершины, т.е. A и E: стек = (А, Е)
      • извлекаем из стека вершину E: стек = (А)
      • т.к. E нет в списке обработанных вершин, то обрабатываем ее и помещаем в список: список = (В, Е)
      • смежные с E вершины – это A и B, но B уже обработана, поэтому помещаем в стек только вершину А: стек = (А, А)
      • извлекаем из стека вершину А: стек = (А)
      • т.к. А нет в списке обработанных вершин, то помещаем ее туда: список = (В, Е, А)
      • смежные с А вершины – это B, C, D, E, из которых B и E уже обработаны, поэтому помещаем в стек C и D: стек = (A, C, D)
      • извлекаем из стека вершину D: стек = (A, C)
      • т.к. D не обработана, то помещаем ее в список: список = (B, E, A, D)
      • смежные с D вершины – это А и С, из которых А уже обработана, поэтому помещаем в стек вершину С: стек = (А, С, С)
      • извлекаем из стека вершину С: стек = (А, С)
      • т.к. С не обработана, помещаем ее в список: список = (B, E, A, D, C)
      • смежные с С вершины – это A и D, но они обе уже обработаны, поэтому в стек ничего не заносим
      • извлекаем из стека С, но она уже обработана
      • извлекаем из стека А, но она тоже уже обработана
      • т.к. стек стал пустым, то завершаем обход с результатом (B, E, A, D, C)

Поиск в ширину

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

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

Тот же что и раньше пример даст следующий результат:

      • пусть стартовая вершина – B
      • включаем B в список обработанных вершин: список = (В)
      • помещаем в очередь смежные с В вершины, т.е. A и E: очередь = (А, Е)
      • извлекаем из очереди вершину А: очередь = (Е)
      • т.к. она не обработана, добавляем ее в список: список = (В, А)
      • смежные с А вершины – это B, C, D и E, помещаем в очередь вершины C, D и E: очередь = (E, C, D, E)
      • извлекаем из очереди вершину Е: очередь = (C, D, E)
      • т.к. Е не обработана, помещаем ее в список: список = (B, A, E), т.е. в первую очередь обработаны обе смежные с В вершины
      • смежные с Е вершины – это А и В, но обе они уже обработаны, поэтому очередь новыми вершинами не пополняется
      • извлекаем из очереди вершину С: очередь = (D, E)
      • т.к. С не обработана, то помещаем ее в список: список = (B, A, E, С)
      • смежные с С вершины – это А и D, помещаем в очередь только D: очередь = (D, E, D)
      • извлекаем из очереди вершину D: очередь = (E, D)
      • т.к. D не обработана, помещаем ее в список: список = (B, A, E, С, D)
      • смежные с D вершины – это А и С, но обе они обработаны, поэтому очередь не пополняется
      • извлекаем из очереди вершину Е, но она уже обработана: очередь = (D)
      • извлекаем из очереди вершину D, но она уже обработана и т.к. очередь становится пустой, то поиск заканчивается с результатом (B, A, E, С, D), что отличается от поиска в глубину.

В заключение отметим несколько наиболее часто встречающихся задач на графах:

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

Подборка визуализаций по алгоритмам поиска

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

Список рассматриваемых алгоритмов:

Алгоритм поиска A*

Алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. С исходным кодом алгоритма вы сможете ознакомиться на дополнительном ресурсе.

Алгоритм поиска Jump Point Search (JPS)

JPS выполняет поиск пути быстрее, будто «перескакивая» некоторые места, которые должны быть просмотрены. Характерным отличием JPS от других алгоритмов является отсутствие требований для предварительной обработки и дополнительных затрат памяти.

Более подробно ознакомиться с работой этого алгоритма вы сможете в развёрнутой статье, посвящённой ему. С кодом этого алгоритма предлагаем ознакомиться на дополнительном ресурсе.

Алгоритм обнаружения циклических схем в направленном графе

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

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

Алгоритм поиска в глубину

Стратегия алгоритма состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска в глубину описывается рекурсивно: перебираются все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то алгоритм нужно запустить от неё, а после вернуться и продолжить перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.

Давайте рассмотрим работу алгоритма на анимации ниже. Как видите, путь «вглубь» графа начинается с вершины A, затем проверяется вершина B, дальше вершины D и E. Таким образом алгоритм проверяет все вершины данной ветви и «возвращается» для исследования другой ветви. Алгоритм заканчивает работу на вершине A, потому что вершина D уже была проверена раннее. С кодом алгоритма вы сможете ознакомиться в статье, посвящённой ему.

Алгоритм поиска в ширину

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

Примечание Вы можете экспериментировать с этим алгоритмом в специальном визуализаторе.

Примечание граф — это, говоря простыми словами, множество точек, называемых вершинами, соединенных какими-то линиями, называемыми рёбрами (необязательно все вершины соединены). Можно представлять себе как города, соединённые дорогами.

Вы сможете ознакомиться с исходным кодом и интерактивной презентацией алгоритма в источнике.

Алгоритм Дейкстры

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

Примечание Вы можете экспериментировать с этим алгоритмом в специальном визуализаторе.

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

Дополнительные материалы для практики

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

Лабораторная работа №10. Исследование алгоритмов на графах. Алгоритмы обхода графа.

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

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

Ориентированный граф (орграф) – граф, у которого все ребра ориентированы, т.е. ребрам которого присвоено направление.

Неориентированный граф (неорграф) – граф, у которого все ребра неориентированы, т.е. ребрам которого не задано направление.

Смешанный граф – граф, содержащий как ориентированные, так и неориентированные ребра.

Петлей называется ребро, соединяющее вершину саму с собой. Две вершины называются смежными, если существует соединяющее их ребро. Ребра, соединяющие одну и ту же пару вершин, называются кратными.

Простой граф – это граф, в котором нет ни петель, ни кратных ребер.

Мультиграф – это граф, у которого любые две вершины соединены более чем одним ребром.

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

Маршрут называется открытым, если его начальная и конечная вершины различны, в противном случае он называется замкнутым.

Маршрут называется цепью, если все его ребра различны. Открытая цепь называется путем, если все ее вершины различны.

Замкнутая цепь называется циклом, если различны все ее вершины, за исключением концевых.

Граф называется связным, если для любой пары вершин существует соединяющий их путь.

Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.). Вес (длина) ребра – число или несколько чисел, которые интерпретируются по отношению к ребру как длина, пропускная способность и т. д.

Взвешенный граф – граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).

Выбор структуры данных для хранения графа в памяти компьютера имеет принципиальное значение при разработке эффективных алгоритмов. Рассмотрим несколько способов представления графа.

Пусть задан граф, у которого количество вершин равно n, а количество ребер – m. Каждое ребро и каждая вершина имеют вес – целое положительное число. Если граф не является помеченным, то считается, что вес равен единице.

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

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

Матрица инцидентности – это двумерный массив размерности n x m, в котором указываются связи между инцидентными элементами графа (ребро и вершина). Столбцы матрицы соответствуют ребрам, строки – вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром. Данный способ является самым емким для хранения, но облегчает нахождение циклов в графе.

Существует много алгоритмов на графах, в основе которых лежит систематический перебор вершин графа, такой что каждая вершина просматривается (посещается) в точности один раз. Поэтому важной задачей является нахождение хороших методов поиска в графе.

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

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

поиск в глубину (Depth First Search, DFS);

поиск в ширину (Breadth First Search, BFS).

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

10 алгоритмов на графах в гифках

Алгоритмы на графах

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

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

Программы из текста

  • © 2020 GitHub , Inc.
  • Terms
  • Privacy
  • Security
  • Status
  • Help

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

10 алгоритмов на графах в гифках

1. Как задаются структуры данных графы?

2. Какие основные алгоритмы их обработки?

( Козьма Прудков )

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

10.1 Виды графов и их определения

Определение 10.1 Графом называется модель 〈V, E; R 〉, где R – бинарное отношение множеств V и E, такое, что каждый элемент e E находится в отношении R либо ровно с одним, либо ровно с двумя элементами множества V. При этом элементы множества V называются вершинами графа, элементы множества E называются рёбрами графа, а отношение R – отношением инцидентности. Вершины, инцидентные одному и тому же ребру, называются смежными.

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

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

Графы обычно изображаются в виде геометрических фигур так, что вершины графа изображаются точками, а ребра – линиями, соединяющими те точки, соответствующие вершинам которых ребра инцидентны, обычно граф обозначают как G(V, E).

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

Остановимся подробнее на способах задания графов. Это является важным для их представления при реализации на ЭВМ алгоритмов, применяющих графы как объекты программирования.

Задать граф — значит описать множества его вершин и ребер, а также отношение инцидентности. Когда граф G — конечный, для описания его вершин и ребер достаточно их занумеровать. Пусть v1, v2, . . . , vn — вершины графаG; e1, e2, . . . , em — его ребра. Отношение инцидентности можно определить матрицей || ij ||, имеющей m строк и n столбцов. Столбцы соответствуют вершинам графа, строки — ребрам. Если ребро ei инцидентно вершине Vj , то ij = 1, в противном случае ij = 0. Это так называемая матрица инцидентности неориентированного графа G, которая является одним из способов его определения.

Ориентированный граф. Неориентированный граф

Рисунок 10.1 – Виды графов

Рисунок 10.2 – Матрицы инцидентности графов

В матрице инцидентности || ij || ориентированного графа G, если вершина vj — начало реб-ра ai, то ij = -1; если vj — конец ai, то ij = 1; если ai — петля, а vj — инцидентная ей вершина, то ij = a, где a — любое число,отличное от 1, 0 и -1, в остальных случаях ij = 0.

В каждой строке матрицы инцидентности для неориентированного или ориентированного графа только два элемента отличны от 0 (или один, если ребро является петлей). Поэтому такой способ задания графа оказывается недостаточно экономным. Отношение инцидентности можно еще задать списком ребер графа. Каждая строка этого списка соответствует ребру, в ней записаны номера вершин, инцидентных ему. Для неориентированного графа порядок этих вершин в строке произволен, для ориентированного первым стоит номер или другое наименование начала ребра, а вторым — его конца. На рис. 10.3 приводятся списки ребер для графов, изображенных выше. По списку ребер графа легко построить его матрицу инцидентности. Действительно, каждая строка этого списка соответствует строке матрицы с тем же номером. Для неориентированного графа в строке списка указаны номера элементов строки матрицы инцидентности, равные 1, и для ориентированного графа в этой строке первым стоит номер элемента строки матрицы, равного -1, а вторым — номер элемента, равного +1.

Рисунок 10.3 – Задание графов списком ребер

Еще одним способом задания графа является матрица смежности — это квадратная матрица || ij ||, столбцам и строкам которой соответствуют вершины графа. Если существует ребро, связывающее вершины vi и vj , то ij =1, в противном случае ij =0.

Матрицы смежностей, рассмотренных выше графов приведены на рис. 10.4.

Рисунок 10.4 – Матрицы смежностей графов

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

Степень вершины – число инцидентных этой вершине рёбер, S(х).

Граф полный – граф G=(V, E), в котором любая пара вершин инцидентна единственному ребру. Обозначается Kp, где р=|V|, при этом |E|=p(p-1)/2.

Число рёбер в графе вычисляется по формуле: n=p(p-1)/2, где р – количество вершин.

Теорема 10.1 Сумма степеней вершин любого графа равна удвоенному числу его ребер.

Теорема 10.2 Число нечетных вершин любого графа четно.

Теорема 10.3 Во всяком графе с n вершинами, где n ≥ 2, всегда найдутся две или более вершины с одинаковыми степенями.

Теорема 10.4. Если в графе с n вершинами только одна пара имеет одинаковую степень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.

Важными понятиями теории графов являются понятия маршрута и пути, которые ассоциируются с последовательным перемещением от вершины к вершине по соединяющим их ребрам или дугам. Маршрут длины определяется как последовательность ребер графа таких, что граничные вершины двух соседних ребер совпадают. Маршрут проходит и через все вершины, инцидентные входящим в него ребрам. Замкнутый маршрут приводит в ту же вершину, из которой он начинался. Маршрут, все ребра которого различны, называется цепью, а маршрут, для которого различны все вершины, называется простой цепью. Замкнутая цепь называется циклом, а простая замкнутая цепь – простым циклом. Для маршрута с n вершинами: вершины , vn называются связанными данным маршрутом (или просто связанными). Вершину называют началом, а vn – концом маршрута. Число n называется длиной маршрута.

Мастер Йода рекомендует:  Классы и ID CSS Что использовать

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

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

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

Два графа G(V, E) и H(W, I) называются изоморфными , если существует взаимно-однозначное соответствие между множествами вершин V, W и множествами ребер E, I, сохраняющее отношение инцидентности. Можно сказать, что изоморфные графы – это один и тот же граф, в котором вершины названы по-разному.

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

Теорема Эйлера . Конечный неориентированный граф эйлеров тогда и только тогда, когда он связан и степени его вершин четны.

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

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

Длина маршрута (цепи, простой цепи) равна количеству ребер в порядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершины vi и vj в графе G, называется расстоянием d (vi, vj) между vi и vj. В связном неориентированном графе расстояние удовлетворяет аксиомам метрики.

С помощью различных операций можно строить графы из более простых, переходить от графа к более простому, разбивать графы на более простые и т.д. Среди одноместных операций наиболее употребительны: удаление и добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра (т.е. замена ребра (u, v) на пару (u, w), (w, v), где w — новая вершина) и др. Известны двухместные операции: соединение, сложение, различные виды умножений графов и др. Такие операции используются для анализа и синтеза графов с заданными свойствами.

Некоторые виды графов имеют специальные названия. Полным графом называется неориентированный граф, содержащий все возможные ребра для данного множества вершин ( любая вершина смежная любой другой ). Неориентированный граф называют двудольным , если множество вершин V можно разбить на две части V1 и V2 таким образом, что концы любого ребра оказываются в разных частях. Остановимся подробнее на основном для теории алгоритмов классе графов – деревьях.

Граф без циклов называется ациклическим. Ациклический связной граф называется деревом . Произвольный ациклический граф называется лесом .

Теорема 10.5 (свойства деревьев). Пусть G=(V,E) – неориентированный граф. Тогда следующие свойства равносильны:

G – является деревом ( без выделенного корня );

для двух любых вершин G существует единственный соединяющий их простой путь;

граф G связен, но перестает быть связным, если удалить любое его ребро;

граф G связен и |E|=|V|-1;

граф G ациклический и |E|=|V|-1;

граф G ациклический, но добавление любого ребра к нему порождает цикл.

Деревом в теории графов называется такой граф D=(V, E), между любыми двумя вершинами которого существует единственная простая цепь, т. е. неориентированный маршрут, у которого вершины и ребра не повторяются. Применительно к ориентированным графам соответствующее определение является более сложным, поскольку основывается на выделении некоторой специальной вершины v, которая получила специальное название корневой вершины или просто — корня. В этом случае ориентированный граф D=(V, Е) называется ориентированным деревом или сокращенно — деревом, если между корнем дерева v и любой другой вершиной существует единственный путь, берущий начало в v. Ниже представлены два примера деревьев: неориентированного дерева а) и ориентированного дерева б).

Дерево с корнем, или корневое дерево (rooted tree), получается, если в дереве выделить одну из вершин, назвав её корнем ( root).

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

Рисунок 10.5 – К вопросу выбора корня дерева

Для случая ориентированного дерева б) вершина v2 является единственным его корнем и имеет специальное обозначение v. Единственность корня в ориентированном дереве следует из того факта, что ориентированный путь всегда имеет единственную вершину, которая является его началом. Поскольку в теории графов имеет значение только наличие или отсутствие связей между отдельными вершинами, деревья, как правило, изображаются специальным образом в виде иерархической структуры. При этом корень дерева изображается самой верхней вершиной в данной иерархии. Далее следуют вершины уровня 1, которые связаны с корнем одним ребром или одной дугой. Следующий уровень будет иметь номер 2, поскольку соответствующие вершины должны быть связаны с корнем двумя последовательными ребрами или дугами. Процесс построения иерархического дерева продолжается до тех пор, пока не будут рассмотрены вершины, которые не связаны с другими вершинами, кроме рассмотренных, или из которых не выходит ни одна дуга. В этом случае самые нижние вершины иногда называют листьями дерева. Важно иметь в виду, что в теории графов дерево «растет» вниз, а не вверх, как в реальной жизни. Изображенные выше деревья можно преобразовать к виду иерархий. Например, неориентированное дерево может быть представлено в виде иерархического дерева следующим образом в). В этом случае корнем иерархии является вершина v1. Ориентированное дерево также может быть изображено в форме иерархического дерева г), однако такое представление является единственным.

В первом случае вершина v2 образует первый уровень иерархии, вершины v4 и v3 — второй уровень иерархии, вершина v5 — третий и последний уровень иерархии. При этом листьями данного неориентированного дерева являются вершины v3 и v5. Во втором случае вершины v1 и v5 образуют первый уровень иерархии, вершины v4 и v6 — второй уровень иерархии, вершина v3 — третий и последний уровень иерархии. Листьями данного ориентированного дерева являются вершины v3 и v6.

Рисунок 10.6 – К вопросу определения листьев

Если (y,x) – последнее ребро на пути из корня в x, то y называется родителем (parent) x, а x называется ребёнком (child) y. Корень является единственной вершиной, у которой нет родителя. Вершины, имеющие общего родителя, называют братьями . Вершины, имеющие детей, называются внутренними. Число детей у вершины корневого дерева называется её степенью (degree). Длина пути от корня до произвольной вершины x называется глубиной (depth) вершины x. Максимальная глубина вершин дерева называется высотой (height) дерева.

Двоичное дерево (binary tree) проще всего определить рекурсивно как конечный набор вершин, который

либо пуст ( не содержит вершин );

либо разбит на три непересекающиеся части : вершину, называемую корнем (root), двоичное дерево, называемое левым поддеревом (left subtree) корня, и двоичное дерево, называемое правым поддеревом (right subtree) корня.

Двоичное дерево, не содержащее вершин, называется пустым (empty). Оно иногда обозначается NIL. Изобразим полное двоичное дерево высоты 3.

Рисунок 10.7 – Полное бинарное дерево высоты 3.

Число внутренних вершин полного k дерева высоты h равно .

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

10.2 Алгоритмы на графах. Обход графа в ширину и в глубину

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

Представление графа в памяти.

Существует два основных метода представления графов в памяти:

  • в виде маccива множеств смежных вершин или
  • в виде матрицы смежности.

Если вершины графа являются сложными объектами, то следует в первую очередь, поставить в соответствие вершинам идентификаторы от 0 до |V | − 1, либо использовать одну из реализаций ассоциативного массива. Кроме того, существует несколько различных способов хранения множества смежных вершин. Например, его можно реализовать односвязный список или как ассоциативный массив, сопоставляющий значение true только смежным вершинам.

У каждого из указанных методов есть свои преимущества и недостатки.

Когда мы используем представление графа G = (V, E) в виде списков смежных вершин, мы храним в памяти массив Adj, содержащий для каждой вершины u ∈ V список всех смежных с ней вершин Adj[u]. Суммарное число элементов во всех списках составляет |E| для ориентированных графов и 2|E| для неориентированных. Поэтому для хранения графа в таком виде, требуется O(V + E) памяти. Этот способ особенно удобен, когда мы имеем дело с разреженными графами.

Заметим, что это представление вполне пригодно для хранения графов с весами. Для этого мы должны в списке, соответствующем вершине u, хранить пары (v, w(u, v)). Такое представление не позволяет быстро проверить, есть ли в графе ребро (u, v). Действительно, для этого нам придётся пробежаться по всему списку Adj[u], который может иметь размер |V | − 1. Поэтому в некоторых случаях удобно для каждой вершины хранить хэш-таблицу, содержащую отображение вершины v на множество пар (v, w(u, v)).

Есть второй, более простой способ представления графов в памяти, в котором описание графа хранится в виде матрицы инцидентности, то есть в виде массива размерности 2. В этом способе вершины графа необходимо пронумеровать числами 0, . . . , |V | − 1. Элемент aij матрицы инцидентности показывает, соединены вершины i и j ребром или нет:

  • aij = 1, если есть ребро из i-й вершины в j -ю,
  • 0, если такого ребра нет.

Для неориентированных графов матрица инцидентности симметрична. Этот способ требует O(V 2 ) памяти для хранения графа. Поэтому его используют в основном для небольших и/или плотных графов — графов, в которых число ребер достаточно велико, а именно, |E| сравнимо с |V | 2 . Для случая графов с взвешенными рёбрами граф представляют в виде матрицы весов — для ребра (i, j ) вместо 1 в матрице храним вес w(i, j ) этого ребра. Для обозначение ребра, отсутствующего в графе, обычно используется некоторый специфический вес (0, −1 или ∞).

Следующая таблица обобщает сведения о представлениях графов в памяти.

Алгоритмы на графах. Алгоритмы обхода графа

Цель лекции: изучить основные алгоритмы обхода графа и научиться решать задачи обхода графа на основе поиска в ширину и поиска в глубину.

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

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

Ориентированный граф (орграф) – граф , у которого все ребра ориентированы, т.е. ребрам которого присвоено направление.

Неориентированный граф (неорграф) – граф , у которого все ребра неориентированы, т.е. ребрам которого не задано направление.

Смешанный граф – граф , содержащий как ориентированные, так и неориентированные ребра .

Петлей называется ребро , соединяющее вершину саму с собой. Две вершины называются смежными, если существует соединяющее их ребро . Ребра , соединяющие одну и ту же пару вершин, называются кратными.

Простой граф – это граф , в котором нет ни петель, ни кратных ребер.

Мультиграф – это граф , у которого любые две вершины соединены более чем одним ребром .

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

Маршрут называется открытым, если его начальная и конечная вершины различны, в противном случае он называется замкнутым.

Маршрут называется цепью, если все его ребра различны. Открытая цепь называется путем, если все ее вершины различны.

Замкнутая цепь называется циклом, если различны все ее вершины, за исключением концевых.

Граф называется связным, если для любой пары вершин существует соединяющий их путь .

Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость , пропускная способность и т. д.). Вес (длина) ребра – число или несколько чисел, которые интерпретируются по отношению к ребру как длина , пропускная способность и т. д.

Взвешенный граф – граф , каждому ребру которого поставлено в соответствие некое значение ( вес ребра ).

Выбор структуры данных для хранения графа в памяти компьютера имеет принципиальное значение при разработке эффективных алгоритмов . Рассмотрим несколько способов представления графа.

Пусть задан граф (например, рис. 44.1), у которого количество вершин равно n , а количество ребер – m . Каждое ребро и каждая вершина имеют вес – целое положительное число. Если граф не является помеченным, то считается, что вес равен единице.

  1. Список ребер – это множество, образованное парами смежных вершин ( рис. 44.2). Для его хранения обычно используют одномерный массив размером m, содержащий список пар вершин, смежных с одним ребром графа. Список ребер более удобен для реализации различных алгоритмов на графах по сравнению с другими способами.

Существует много алгоритмов на графах, в основе которых лежит систематический перебор вершин графа , такой что каждая вершина просматривается (посещается) в точности один раз. Поэтому важной задачей является нахождение хороших методов поиска в графе.

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

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

  • поиск в глубину (Depth First Search, DFS );
  • поиск в ширину (Breadth First Search, BFS ).

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

Графы. Реализация на языке Java обхода графа в глубину и в ширину.

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

Итак, что нам нужно? Первое, что мы сделаем – создадим структуру данных, представляющую вершину в графе. Это будет класс Vertex.

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

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

Что нам понадобится? Мы создали несколько полей. Давайте по порядку. Поле VERTEX_MAX хранит максимально возможное количество вершин в нашем графе. Мы для примера выбрали 100. В реальных задачах их может быть гораздо больше. Массив vertexList[] необходим нам для хранения наших вершин в порядке их добавления в граф. Переменная vertexCount просто хранит число уже добавленных вершин. Ну а двумерный массив matrix есть ни что иное, как матрица смежности, описывающая наш граф.

В конструкторе класса Graph просто инициализируем все поля и заполняем матрицу смежности нулями. Что теперь? А теперь мы добавим для метода для вставки новой вершины в граф и для добавления ребра между двумя вершинами. Будем считать, что работаем с ориентированными графами. Затем вы легко сможете изменить метод для работы как с неориентированными, так и со смешанными графами, изменив буквально пару строк.

Анимирование алгоритма поиска в глубину на графе

Я граф нарисовал в picturebox, теперь получается, что мне нужно с начало закрашивать кружочек цветом фона, а потом рисовать сам кружочек, с ребрами такая же ситуация. Мне кажется, что можно сделать как — то проще. Просто здесь столько нюансов и гемора, что аж руки отпускаются. И еще вопрос с таймером как его правильно использовать. нашел вот такое:

Напишите, еще какие нибудь примеры с использованием timer

Добавлено через 16 минут
По второй ссылке не качайте, там файла с графом нет

28.05.2020, 09:57

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

Алгоритм поиска в глубину в ориентированном графе
Добрый вечер,форумчане:) Знаю, что подобная тема встречалась тут довольно часто, но у меня все-таки.

Процедура поиска в глубину в графе, заданном списками инцидентности
Нужна помощь знающего Паскаль человека, по заданию: Напишите и используйте в программе процедуру.

Нахождение основного дерева в графе методом поиска в глубину.
УСЛОВИЕ: Разработайте программу нахождения основного дерева в графе методом поиска в глубину.

Поиск в ширину, глубину в графе
Есть ли у кого программка для поиска в ширину/в глубину на графах с использованием матрицы.

10 алгоритмов на графах в гифках

1. Как задаются структуры данных графы?

2. Какие основные алгоритмы их обработки?

( Козьма Прудков )

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

10.1 Виды графов и их определения

Определение 10.1 Графом называется модель 〈V, E; R 〉, где R – бинарное отношение множеств V и E, такое, что каждый элемент e E находится в отношении R либо ровно с одним, либо ровно с двумя элементами множества V. При этом элементы множества V называются вершинами графа, элементы множества E называются рёбрами графа, а отношение R – отношением инцидентности. Вершины, инцидентные одному и тому же ребру, называются смежными.

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

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

Графы обычно изображаются в виде геометрических фигур так, что вершины графа изображаются точками, а ребра – линиями, соединяющими те точки, соответствующие вершинам которых ребра инцидентны, обычно граф обозначают как G(V, E).

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

Остановимся подробнее на способах задания графов. Это является важным для их представления при реализации на ЭВМ алгоритмов, применяющих графы как объекты программирования.

Задать граф — значит описать множества его вершин и ребер, а также отношение инцидентности. Когда граф G — конечный, для описания его вершин и ребер достаточно их занумеровать. Пусть v1, v2, . . . , vn — вершины графаG; e1, e2, . . . , em — его ребра. Отношение инцидентности можно определить матрицей || ij ||, имеющей m строк и n столбцов. Столбцы соответствуют вершинам графа, строки — ребрам. Если ребро ei инцидентно вершине Vj , то ij = 1, в противном случае ij = 0. Это так называемая матрица инцидентности неориентированного графа G, которая является одним из способов его определения.

Ориентированный граф. Неориентированный граф

Рисунок 10.1 – Виды графов

Рисунок 10.2 – Матрицы инцидентности графов

В матрице инцидентности || ij || ориентированного графа G, если вершина vj — начало реб-ра ai, то ij = -1; если vj — конец ai, то ij = 1; если ai — петля, а vj — инцидентная ей вершина, то ij = a, где a — любое число,отличное от 1, 0 и -1, в остальных случаях ij = 0.

В каждой строке матрицы инцидентности для неориентированного или ориентированного графа только два элемента отличны от 0 (или один, если ребро является петлей). Поэтому такой способ задания графа оказывается недостаточно экономным. Отношение инцидентности можно еще задать списком ребер графа. Каждая строка этого списка соответствует ребру, в ней записаны номера вершин, инцидентных ему. Для неориентированного графа порядок этих вершин в строке произволен, для ориентированного первым стоит номер или другое наименование начала ребра, а вторым — его конца. На рис. 10.3 приводятся списки ребер для графов, изображенных выше. По списку ребер графа легко построить его матрицу инцидентности. Действительно, каждая строка этого списка соответствует строке матрицы с тем же номером. Для неориентированного графа в строке списка указаны номера элементов строки матрицы инцидентности, равные 1, и для ориентированного графа в этой строке первым стоит номер элемента строки матрицы, равного -1, а вторым — номер элемента, равного +1.

Рисунок 10.3 – Задание графов списком ребер

Еще одним способом задания графа является матрица смежности — это квадратная матрица || ij ||, столбцам и строкам которой соответствуют вершины графа. Если существует ребро, связывающее вершины vi и vj , то ij =1, в противном случае ij =0.

Матрицы смежностей, рассмотренных выше графов приведены на рис. 10.4.

Рисунок 10.4 – Матрицы смежностей графов

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

Степень вершины – число инцидентных этой вершине рёбер, S(х).

Граф полный – граф G=(V, E), в котором любая пара вершин инцидентна единственному ребру. Обозначается Kp, где р=|V|, при этом |E|=p(p-1)/2.

Число рёбер в графе вычисляется по формуле: n=p(p-1)/2, где р – количество вершин.

Теорема 10.1 Сумма степеней вершин любого графа равна удвоенному числу его ребер.

Теорема 10.2 Число нечетных вершин любого графа четно.

Теорема 10.3 Во всяком графе с n вершинами, где n ≥ 2, всегда найдутся две или более вершины с одинаковыми степенями.

Теорема 10.4. Если в графе с n вершинами только одна пара имеет одинаковую степень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.

Важными понятиями теории графов являются понятия маршрута и пути, которые ассоциируются с последовательным перемещением от вершины к вершине по соединяющим их ребрам или дугам. Маршрут длины определяется как последовательность ребер графа таких, что граничные вершины двух соседних ребер совпадают. Маршрут проходит и через все вершины, инцидентные входящим в него ребрам. Замкнутый маршрут приводит в ту же вершину, из которой он начинался. Маршрут, все ребра которого различны, называется цепью, а маршрут, для которого различны все вершины, называется простой цепью. Замкнутая цепь называется циклом, а простая замкнутая цепь – простым циклом. Для маршрута с n вершинами: вершины , vn называются связанными данным маршрутом (или просто связанными). Вершину называют началом, а vn – концом маршрута. Число n называется длиной маршрута.

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

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

Мастер Йода рекомендует:  Администраторы сообществ в «Ok» смогут получать денежные переводы

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

Два графа G(V, E) и H(W, I) называются изоморфными , если существует взаимно-однозначное соответствие между множествами вершин V, W и множествами ребер E, I, сохраняющее отношение инцидентности. Можно сказать, что изоморфные графы – это один и тот же граф, в котором вершины названы по-разному.

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

Теорема Эйлера . Конечный неориентированный граф эйлеров тогда и только тогда, когда он связан и степени его вершин четны.

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

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

Длина маршрута (цепи, простой цепи) равна количеству ребер в порядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершины vi и vj в графе G, называется расстоянием d (vi, vj) между vi и vj. В связном неориентированном графе расстояние удовлетворяет аксиомам метрики.

С помощью различных операций можно строить графы из более простых, переходить от графа к более простому, разбивать графы на более простые и т.д. Среди одноместных операций наиболее употребительны: удаление и добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра (т.е. замена ребра (u, v) на пару (u, w), (w, v), где w — новая вершина) и др. Известны двухместные операции: соединение, сложение, различные виды умножений графов и др. Такие операции используются для анализа и синтеза графов с заданными свойствами.

Некоторые виды графов имеют специальные названия. Полным графом называется неориентированный граф, содержащий все возможные ребра для данного множества вершин ( любая вершина смежная любой другой ). Неориентированный граф называют двудольным , если множество вершин V можно разбить на две части V1 и V2 таким образом, что концы любого ребра оказываются в разных частях. Остановимся подробнее на основном для теории алгоритмов классе графов – деревьях.

Граф без циклов называется ациклическим. Ациклический связной граф называется деревом . Произвольный ациклический граф называется лесом .

Теорема 10.5 (свойства деревьев). Пусть G=(V,E) – неориентированный граф. Тогда следующие свойства равносильны:

G – является деревом ( без выделенного корня );

для двух любых вершин G существует единственный соединяющий их простой путь;

граф G связен, но перестает быть связным, если удалить любое его ребро;

граф G связен и |E|=|V|-1;

граф G ациклический и |E|=|V|-1;

граф G ациклический, но добавление любого ребра к нему порождает цикл.

Деревом в теории графов называется такой граф D=(V, E), между любыми двумя вершинами которого существует единственная простая цепь, т. е. неориентированный маршрут, у которого вершины и ребра не повторяются. Применительно к ориентированным графам соответствующее определение является более сложным, поскольку основывается на выделении некоторой специальной вершины v, которая получила специальное название корневой вершины или просто — корня. В этом случае ориентированный граф D=(V, Е) называется ориентированным деревом или сокращенно — деревом, если между корнем дерева v и любой другой вершиной существует единственный путь, берущий начало в v. Ниже представлены два примера деревьев: неориентированного дерева а) и ориентированного дерева б).

Дерево с корнем, или корневое дерево (rooted tree), получается, если в дереве выделить одну из вершин, назвав её корнем ( root).

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

Рисунок 10.5 – К вопросу выбора корня дерева

Для случая ориентированного дерева б) вершина v2 является единственным его корнем и имеет специальное обозначение v. Единственность корня в ориентированном дереве следует из того факта, что ориентированный путь всегда имеет единственную вершину, которая является его началом. Поскольку в теории графов имеет значение только наличие или отсутствие связей между отдельными вершинами, деревья, как правило, изображаются специальным образом в виде иерархической структуры. При этом корень дерева изображается самой верхней вершиной в данной иерархии. Далее следуют вершины уровня 1, которые связаны с корнем одним ребром или одной дугой. Следующий уровень будет иметь номер 2, поскольку соответствующие вершины должны быть связаны с корнем двумя последовательными ребрами или дугами. Процесс построения иерархического дерева продолжается до тех пор, пока не будут рассмотрены вершины, которые не связаны с другими вершинами, кроме рассмотренных, или из которых не выходит ни одна дуга. В этом случае самые нижние вершины иногда называют листьями дерева. Важно иметь в виду, что в теории графов дерево «растет» вниз, а не вверх, как в реальной жизни. Изображенные выше деревья можно преобразовать к виду иерархий. Например, неориентированное дерево может быть представлено в виде иерархического дерева следующим образом в). В этом случае корнем иерархии является вершина v1. Ориентированное дерево также может быть изображено в форме иерархического дерева г), однако такое представление является единственным.

В первом случае вершина v2 образует первый уровень иерархии, вершины v4 и v3 — второй уровень иерархии, вершина v5 — третий и последний уровень иерархии. При этом листьями данного неориентированного дерева являются вершины v3 и v5. Во втором случае вершины v1 и v5 образуют первый уровень иерархии, вершины v4 и v6 — второй уровень иерархии, вершина v3 — третий и последний уровень иерархии. Листьями данного ориентированного дерева являются вершины v3 и v6.

Рисунок 10.6 – К вопросу определения листьев

Если (y,x) – последнее ребро на пути из корня в x, то y называется родителем (parent) x, а x называется ребёнком (child) y. Корень является единственной вершиной, у которой нет родителя. Вершины, имеющие общего родителя, называют братьями . Вершины, имеющие детей, называются внутренними. Число детей у вершины корневого дерева называется её степенью (degree). Длина пути от корня до произвольной вершины x называется глубиной (depth) вершины x. Максимальная глубина вершин дерева называется высотой (height) дерева.

Двоичное дерево (binary tree) проще всего определить рекурсивно как конечный набор вершин, который

либо пуст ( не содержит вершин );

либо разбит на три непересекающиеся части : вершину, называемую корнем (root), двоичное дерево, называемое левым поддеревом (left subtree) корня, и двоичное дерево, называемое правым поддеревом (right subtree) корня.

Двоичное дерево, не содержащее вершин, называется пустым (empty). Оно иногда обозначается NIL. Изобразим полное двоичное дерево высоты 3.

Рисунок 10.7 – Полное бинарное дерево высоты 3.

Число внутренних вершин полного k дерева высоты h равно .

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

10.2 Алгоритмы на графах. Обход графа в ширину и в глубину

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

Представление графа в памяти.

Существует два основных метода представления графов в памяти:

  • в виде маccива множеств смежных вершин или
  • в виде матрицы смежности.

Если вершины графа являются сложными объектами, то следует в первую очередь, поставить в соответствие вершинам идентификаторы от 0 до |V | − 1, либо использовать одну из реализаций ассоциативного массива. Кроме того, существует несколько различных способов хранения множества смежных вершин. Например, его можно реализовать односвязный список или как ассоциативный массив, сопоставляющий значение true только смежным вершинам.

У каждого из указанных методов есть свои преимущества и недостатки.

Когда мы используем представление графа G = (V, E) в виде списков смежных вершин, мы храним в памяти массив Adj, содержащий для каждой вершины u ∈ V список всех смежных с ней вершин Adj[u]. Суммарное число элементов во всех списках составляет |E| для ориентированных графов и 2|E| для неориентированных. Поэтому для хранения графа в таком виде, требуется O(V + E) памяти. Этот способ особенно удобен, когда мы имеем дело с разреженными графами.

Заметим, что это представление вполне пригодно для хранения графов с весами. Для этого мы должны в списке, соответствующем вершине u, хранить пары (v, w(u, v)). Такое представление не позволяет быстро проверить, есть ли в графе ребро (u, v). Действительно, для этого нам придётся пробежаться по всему списку Adj[u], который может иметь размер |V | − 1. Поэтому в некоторых случаях удобно для каждой вершины хранить хэш-таблицу, содержащую отображение вершины v на множество пар (v, w(u, v)).

Есть второй, более простой способ представления графов в памяти, в котором описание графа хранится в виде матрицы инцидентности, то есть в виде массива размерности 2. В этом способе вершины графа необходимо пронумеровать числами 0, . . . , |V | − 1. Элемент aij матрицы инцидентности показывает, соединены вершины i и j ребром или нет:

  • aij = 1, если есть ребро из i-й вершины в j -ю,
  • 0, если такого ребра нет.

Для неориентированных графов матрица инцидентности симметрична. Этот способ требует O(V 2 ) памяти для хранения графа. Поэтому его используют в основном для небольших и/или плотных графов — графов, в которых число ребер достаточно велико, а именно, |E| сравнимо с |V | 2 . Для случая графов с взвешенными рёбрами граф представляют в виде матрицы весов — для ребра (i, j ) вместо 1 в матрице храним вес w(i, j ) этого ребра. Для обозначение ребра, отсутствующего в графе, обычно используется некоторый специфический вес (0, −1 или ∞).

Следующая таблица обобщает сведения о представлениях графов в памяти.

10 алгоритмов на графах в гифках

Лабораторная работа N5

«Алгоритмы на графах»

Цель работы : «Изучение способов представления графов».

Краткие теоретические сведения

1.1 Машинное представление графов

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

Будем рассматривать как ориентированные графы, так и неориентированные. Будем обозначать граф

где V — множество вершин, а Е — множество ребер, причем

— для ориентированного графа

— для не ориентированного графа.

Будем использовать так же обозначение (мощность множества).

В теории графов классическим способом представления графа является матрица инциденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге (х,у)ÎЕ, содержит +1 в строке, соответствующей вершине х,-1 в строке, соответствующей вершине у и нули во всех остальных строках. Петлю, т.е. дугу вида (х, х), удобно представлять другим значением, например 2, в строке х.

Для неориентированного графа столбец, соответствующий ребру <х, у>, содержит 1 в строках, соответствующих х и у, и 0 — во всех остальных строках (рис. 1, рис. 2).

Рис. 1 Матрица инциденций для ориентированного графа

Рис. 2. Матрица инциденций для неориентированного графа

С алгоритмической точки зрения матрица инциденций является одним из самых худших способов представления графа, так как:

• требуется n x m ячеек памяти, причем большинство ячеек занято нулями;

• неудобен доступ к информации, т.к. ответ на вопросы: существует ли дуга (x, у)? к каким вершинам ведут ребра из x? — требует в худшем случае перебора всех столбцов, т.е. m шагов.

Немного лучше способ представления графа с помощью матрицы

смежности В=[bij] размера nхm, где bij =1, если существует ребро, ведущее из х в у, и bij = 0 — противном случае. При этом подразумевается, что ребро неориентированного графа идет как от х к у, так и от у к х. Поэтому матрица смежности для неориентированного графа всегда симметрична. Для наших графов матрицы смежности имеют вид (рис. 3):

Рис. 3. Матрицы смежности для неориентированных графов.

Основное преимущество матрицы смежности состоит в том, что за один шаг можно ответить на вопрос — существует ли ребро из х в у? Недостатком является тот факт, что независимо от числа ребер объем занимаемой памяти составляет n 2 . На практике это неудобство иногда можно исправить, храня целую строку или столбец в одном машинном слове (для малых п).

Более экономным в отношении памяти (особенно для неплотных графов, когда т гораздо меньше п ) является способ представления графа с помощью списка пар, соответствующих его ребрам. Пара (х,у) соответствует дуге (х, у), если граф ориентированный, и ребру <х, у>, если граф неориентированный. В нашем

случае списки пар:

Очевидно, что в этом случае объем памяти составляет 2 m . Неудобством является большое число шагов (порядка m в худшем случае) для нахождения множества вершин, к которым ведут ребра из данной вершины.

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

Лучшим решением во многих случаях является структура данных, которую назовем списками инцидентности. Она содержит для каждой вершины v Î V список вершин и таких, что V —> и для ориентиро­ванного графа и v u для неориентированного графа. Каждый элемент такого списка является записью r , состоящей из двух полей:

r .строка — вершина графа;

r .след — указатель на следующую запись в списке.

Для последней записи в списке — r .след = nil . Указатель на начало каждого списка хранится в таблице НАЧАЛО. Таким образом, НАЧАЛО[ v ] — указатель на начало списка, содержащего вершины из множества <и: (v, и)>для ориентированного графа или <и: > для неориентированного графа, соответственно.

Весь список обозначим (неформально) СПИСОК[ v ], а цикл, выполняющий некоторую операцию над каждым элементом и из этого списка, запишем как

For u Î СПИСОК [v]do.

Отметим, что для неориентированного графа каждое ребро <и, v> представлено дважды:

через вершину v в списке СПИСОК[ u ] и

через вершину и в списке СПИСОК[v].

Для Наших примеров список инцидентности СПИСОК[v], v Î V выглядят следующим образом (рис. 4):

Рис. 4 Список инцидентности.

Во многих алгоритмах структура графа динамически модифицируется добавлением и удалением ребер. В таких случаях полагаем, что в списке СПИСОК[ u ] элемент, содержащий вершину v , снабжен указателем на элемент списка СПИСОК[ v ], содержащий вершину и, что каждый элемент списка снабжен указателем не только на последующий, но и на предыдущий элемент. Тогда удаляя некоторый элемент из списка, мы можем легко за ограниченное число шагов удалить и другой элемент, представляющий то же самое ребро, не просматривая список, содержащий этот элемент.

Число ячеек памяти, необходимых для представления графа с помощью списков инцидентности, имеет порядок ( n + m ).

Оговорим некоторые понятия, связанные с записью алгоритмов. Алгоритмы будем записывать на неформальном языке, использующем основные конструкции Паскаля. Если реализация какого-либо фрагмента алгоритма очевидна, то такой фрагмент будем записывать на естественном языке. Будем также применять некоторые неформальные конструкции, например:

FOR x Î X DO — выполнять оператор Р для всех элементов х

Р множества Х в произвольной последовательности;

за значение переменной х;

качестве значения переменной х.

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

Для любого алгоритма нас будет интересовать его вычислительная сложность, т.е. число шагов, выполняемых в худшем случае, как функция от размерности задачи. Под размерностью задачи будем понимать | V | или пару V |, |Е|>. Тогда сложность алгоритма будет f ( n ) -наибольшее число шагов алгоритма для произвольного графа с n вершинами или f ( n , m ) — наибольшее число шагов алгоритма для произвольного графа с n вершинами и m ребрами. При этом под шагом, вообще говоря, следует понимать любую машинную команду (перенос слова из памяти в буфер и наоборот, выполнение арифметических операций, условные переходы, ввод-вывод, косвенную адресацию и т.д.). Однако нас будет интересовать не точная сложность в этом смысле, а так называемая асимптотическая сложность, т.е. скорость увеличения числа шагов алгоритма при неограниченном (теоретически) росте размерности задачи. Тогда для характеристики сложности удобно использовать такие обозначения:

f ( n ) = существуют константы С, N такие, что f ( n )≤ C g ( n )

0( g ( n )) для любого n ≥ N

g ( n ) — некоторая заданная функция

f ( n ) = существуют константы С, N такие, что f ( n ) ≥ C g ( n )

Ω( g ( n )) для любого n ≥ N

Читается: 0( g ( n )) — «порядка не более чем g ( n )»

Ω ( g ( n )) — «порядка не менее чем g ( n )»

То же для функции g ( n , m ).

1.1.1 Поиск в глубину в графе

Основные требования к методам поиска в графе:

1) метод должен легко реализовываться алгоритмом решения интересующей нас задачи;

2) каждое ребро графа анализируется один раз (или ограниченное число раз, что существенно не меняет ситуации).

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

Рассмотрим один метод поиска в неориентированном графе, который является основой многих графовых алгоритмов. Этот метод называется поиском в глубину ( depth first search ).

Общая идея метода состоит в следующем. Начинаем поиск с некоторой фиксированной вершины v . Затем выбираем произвольную вершину и, смежную с v , и повторяем наш просмотр от u . В общем случае предположим, что мы находимся в некоторой вершине v . Если существует новая (ещё не просмотренная) вершина u , u — v , то мы рассматриваем эту вершину (она перестает быть новой), начиная с неё, продолжаем поиск. Если же не существует новой вершины, смежной с v, мы говорим, что вершина v использована, возвращаемся в вершину, из которой мы попали в v, и продолжаем поиск (если v = v , то поиск закончен).

Иначе говоря, поиск в глубину из вершины v основывается на поиске в глубину из всех новых вершин, смежных с v.

Это можно легко записать с помощью рекурсивной процедуры WG ( v ):

PROCEDURE WG ( v );

BEGIN рассмотреть v; НОВЫЙ[ v ]:- false ;

FOR u СПИСОК [v] do

IF НОВЫЙ [u] THEN WG(u)

Весь процесс поиска в глубину в произвольном, необязательно связном графе производится по следующему алгоритму:

FOR v V DO НОВЫЙ [v]:= true;

IF НОВЫЙ [v] THEN WG(v)

Можно убедиться в том, что этот алгоритм просмотрит каждую вершину ровно один раз и его сложность порядка O ( n + m ). Дополнительно каждый вызов WG ( v ) влечет за собой просмотр всех вершин компоненты связности графа, содержащей v (если они ещё не просмотрены, т.е. НОВЫЙ[ u ] = true для каждой вершины и, принадлежащей этой компоненте). При этом каждая вершина просматривается не более одного раза.

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

Чтобы оценить сложность алгоритма, заметим, что число шагов в обоих циклах FOR (строки 2,3)≈ n (не считая шагов, выполненных при вызове WG). Эта программа выполняется не более чем n раз во втором цикле сразу после посещения каждой из вершин для каждого из её новых соседей, суммарно не более чем ( n + m ) раз. Полное число шагов, выполняемых циклом в третьей строке процедуры WG (не считая шагов, выполняемых WG ( n )), для всех вызовов этой процедуры будет порядка т, где m — число ребер. Это дает общую сложность алгоритма O ( n + m ).

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

Стандартным способом устранения рекурсии является использование стека. Каждая просмотренная вершина помещается в стек и удаляется из него после использования.

предполагаем, что в начале поиска P[u] — указатель на 1-ую запись списка СПИСОК[ u ] для каждой вершины u ;

массивы Р, НОВЫЙ — глобальные>

1 PROCEDURE WGl(v);

2 BEGIN СТЕК := 0; СТЕК v ] := false;

3 WH IL E CTEK ≠ 0 DO

5 IF P[t]= nil THEN b:=false

6 ELSE b := not НОВЫЙ [ Р [t]^. строка ];

7 WHILE b DO BEGIN

9 IF P[t]=nil THEN b := false

10 ELSE b :=not НОВЫЙТ P[t]^. строка ]

12 IF P[t] <>nil THEN

13 BEGIN t := Р [t]^. строка ; СТЕК

14 рассмотреть t; НОВЫЙ[ t ] := false

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

Рис. 5. Поиск в глубину.

Метод легко переносится и на ориентированные графы. Нетрудно проверить, что и в этом случае результатом вызова процедуры WG ( v ), а также WGl ( v ), будет посещение за O ( n + m ) шагов всех вершин и таких, что существует путь из v и u .

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

1.1.2 Поиск в ширину в графе

Рассмотрим несколько иной метод поиска в графе, называемый поиском в ширину ( breadth first search ). Этот метод основан, грубо говоря, на замене стека очередью. В этом случае чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью просмотра сразу всех еще не просмотренных соседей этой вершины.

1 PROCEDURE WS ( v );

переменные НОВЫЙ, СПИСОК — глобальные>

3 ОЧЕРЕДЬ := 0; ОЧЕРЕДЬ v ; HOB ЫЙ[ v ] := false ;

4 WHILE ОЧЕРЕДЬ := 0 DO begin

6 FOR u€ СПИСОК [ р ] DO

7 IF НОВЫЙ [u] THEN BEGIN

8 ОЧЕРЕДЬ НОВЫЙ [u]:=false

Как и для поиска в глубину, можно легко показать, что вызов процедуры WS ( v ) приводит к посещению всех вершин компоненты связности графа, содержащей вершину v , причем каждая вершина просматривается ровно один раз. Вычислительная сложность алгоритма также имеет порядок m + n , т.к. каждая вершина помещается в очередь и удаляется из очереди в точности один раз, а число итераций цикла 6, очевидно, будет иметь порядок числа ребер графа.

Оба вида поиска в графе — в глубину и ширину — могут быть использованы для нахождения пути между фиксированными вершинами v и u . Для этого достаточно начать поиск в графе с вершины v и вести его до вершины и.

Преимущество поиска в глубину: в момент посещения вершины и стек содержит последовательность вершин, определяющую путь из v и u .

Недостаток: полученный таким образом путь в общем случае не будет кратчайшим.

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

Модифицируем процедуру WS , заменяя строки 7-9 на

IF НОВЫЙ [u] THEN BEGIN

ОЧЕРЕДЬ НОВЫЙ [u]:= false;

ПРЕДЫДУЩИЙ [ u ]:=Р

По окончанию работы модифицированной процедуры таблица ПРЕДЫДУЩИЙ содержит для каждой вершины и вершину ПРЕДЫДУЩИЙ[ u ], из которой мы попали в u . Методом математической индукции можно показать, что эта таблица действительно определяет кратчайший путь от каждой просмотренной вершины до исходной вершины v. Пронумеруем в квадратных скобках для нашего графа вершины в той очередности, в которой они посещаются в процессе поиска в ширину.

Как и в случае поиска в глубину, процедуру WS можно использовать без всяких модификаций и тогда, когда списки инцидентности СПИСОК[ v ], v Î V , определяют некоторый ориентированный граф. Очевидно, что тогда посещаются только те вершины, до которых существует путь от вершины, с которой мы начали поиск.

1.2 Стягивающие деревья (каркасы)

Вспомним, что деревом называется произвольный неориентированный связный граф без циклов. Для произвольного неориентированного графа

G = V , Е> каждое дерево V , Т>, где Т Е, будем называть стягивающим деревом или каркасом графа G. Ребра такого графа (дерева) назовем ветвями, а остальные ребра графа G будем называть хордами.

Отметим, что каждое дерево с n вершинами имеет n -1 ветвь. (В каждую вершину, кроме корня, входит только одно ребро).

Пусть имеем граф, в котором стягивающие деревья можно построить, например, способами а) и б) (рис. 6).

Рис. 6. Два способа построения стягивающего дерева

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

Рассмотрим алгоритм нахождения стягивающего дерева связного графа методом поиска в глубину. Пусть исходный граф G = V , E > задан списками инцидентности СПИСОК[ v ], v Î V . Алгоритм реализуем процедурой WGD ( v ):

1 PROCEDURE WGD ( v );

2 BEGIN НОВЫЙ [v] := false;

3 FOR u СПИСОК [v] DO

4 IF НОВЫЙ [u] THEN BEGIN

2 FOR u V DO НОВЫЙ[ u ] := true ;

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

1) в момент добавления к множеству Т новой ветви (строка 5 WGD) в дереве V , Т> существует путь из г в v. Таким образом, алгоритм строит связанный граф;

Мастер Йода рекомендует:  9 гениальных способов для продвижения вашего блога на Facebook

2) каждая новая ветвь , добавляемая к множеству Т, соединяет уже рассмотренную вершину v с новой вершиной u. Отсюда следует, что построенный граф V , T > не имеет циклов. (Действительно, последняя ветвь, замыкающая цикл, должна была бы соединить две уже рассмотренных вершины);

3) из свойства поиска в глубину следует, что программа WGD просматривает все вершины связного графа.

Следовательно, граф V , T >, построенный нашим алгоритмом, есть стягивающее дерево графа G . Очевидно, что вычислительная сложность алгоритма будет порядка C ( n + m ), т.е. того же порядка, что u поиск в глубину.

Стягивающее дерево, построенное для нашего примера с помощью поиска в глубину, изображено на рис. 6а. Вершина г, с которой начинается поиск, есть корень дерева. Очевидно, что в дереве V , T > существует в точности один путь от произвольной вершины к корню. Для двух различных вершин v и u дерева V , T > будем говорить, что u является потомком v, если v лежит на пути (в дереве) из u в корень.

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

Подобным же способом можно построить стягивающее дерево, используя метод поиска в ширину. Алгоритм, реализующий этот метод, можно записать так:

2 FOR u V DO НОВЫЙ[ u ] := true ;

4 ОЧЕРЕДЬ := ; ОЧЕРЕДЬ

5 НОВЫЙ[г] := false ;

6 WHILE ОЧЕРЕДЬ ≠ DO BEGIN

8 FOR u СПИСОК [u] DO

9 IF НОВЫЙ [u] THEN BEGIN

10 ОЧЕРЕДЬ НОВЫЙ [u] := false; Т := Т

Путем рассуждении, которые приводили ранее, можно показать, что данный алгоритм корректно строит стягивающее дерево для произвольного связного графа за 0( n + m ) шагов, т.е. за число шагов не более, чем C ( n + m ).

На рис. 7б приведено стягивающее дерево, построенное для нашего примера с помощью поиска в ширину.

Преимущества процедуры поиска в ширину, о которых мы уже говорили, приводят к следующему выводу.

Пусть V , Т> — стягивающее дерево произвольного связного графа G = V , E >, построенное с помощью алгоритма поиска в ширину. Тогда путь в V , Т> из произвольной вершины v к корню г является кратчайшим путем из v к г в графе G .

Все рассуждения о стягивающих деревьях легко перенести на произвольные, не обязательно связанные графы. Максимальный подграф без циклов произвольного графа G называется стягивающим лесом графа G. Очевидно, что стягивающий лес графа с k компонентами связности определяется через стягивающие деревья этих компонент и, следовательно, содержит n — k -1 ребер.

Тесно связана с задачей нахождения стягивающего дерева задача отыскания фундаментального множества циклов в графе.

1.3 Отыскание фундаментального множества циклов в графе

Если к стягивающему дереву V , Т> графа G = V , E > мы добавим произвольную хорду е Е\Т, то возникший при этом подграф С = V , TU < e >> содержит в точности один цикл (под циклом мы здесь будем понимать элементарный цикл). Обозначим этот цикл через Се. Множество С = <Се: е Е \ Т> называют фундаментальным множеством циклов графа G (относительно стягивающего дерева V , T >). Название «фундаментальное» связано с тем, что каждый цикл графа G можно достаточно просто получить из циклов множества G.

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

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

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

Поэтому, если анализируемое нами ребро замыкает цикл (т.е. WGN [ v ] > WGN [ u ] > 0 b u не находится непосредственно под верхним элементом стека), то вершина u находится в стеке и цикл, замыкаемый ребром , представлен группой элементов стека, начиная с v и кончая вершиной u.

1 PROCEDURE цикл( v );

2 BEGIN d := d+1; CTEK[d] := v; num := num+1; WGN[ ] := num;

3 FOR u СПИ COK[v] DO

4 IF WGN[u] = 0 THEN цикл ( г )

5 ELSE IF (u CTEK[d-l]) and (WGN[v] > WGN[u]) THEN < ребро замыкает новый цикл )

7 CTEK [ d ], CTEK [ d — l ]. СТЕК[с], где СТЕК[с] = u

2 FOR v V DO WGN [ r ] := 0; num := 0;

3 d := 0; СТЕК[0] := 0;

5 IF WGN[r] = 0 THEN цикл (v)

Оценим вычислительную сложность алгоритма. Отметим, что общее число шагов, не считая вычисления циклов, как и во всех алгоритмах, основанных на поиске в глубину, имеет порядок 0( n + m ). К этому следует добавить суммарную длину всех циклов. Эта длина не превосходит ( m — n +1), что дает общую сложность алгоритма 0( nm + n ) (или 0( nm ), если отбросить вырожденный случай m =0).

1.2 Эйлеровы пути в графе

Эйлеров путь в графе — произвольный путь, проходящий через каждое ребро графа ровно один раз , т.е. такой путь V 1 . Vm +1 , что каждое ребро e E появляется один раз как < νi , νi +1 > для некоторого i . Если ν 1 = νm +1 , то такой путь называется эйлеровым циклом.

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

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

Пусть G = V , E > — связанный граф, представленный списками СПИСОК[ r ], v V . Алгоритм нахождения эйлерова цикла в графе построим следующим образом. Используем два стека СТЕК1 и СТЕК2.

Выбираем произвольную вершину графа ν и строим последовательно путь из этой вершины. Вершины этого пути помешаем в СТЕК1, а ребра удаляем из графа. Эти действия продолжаем до тех пор, пока оказывается, что путь удлинить, включив в него новую вершину, уже нельзя. Т.е. СПИСОК[ v ]= . Отметим, что тогда должно быть ν = ν , иначе это бы означало, что вершина ν – нечетной степени. Таким образом из нашего графа был удален цикл, а вершины этого стека находятся СТЕК1. При этом в графе, модифицированном таким образом, степень произвольной вершины остается четной. Вершина ν = ν переносится из СТЕК1 в СТЕК2, а процесс повторяется, начиная с вершины, верхней в СТЕК1 (если ее список не пустой). Теперь снова в СТЕК1 помещается некоторый цикл проходящий через эту вершину и т.д. Процесс продолжается до тех пор, пока СТЕК1 не станет пустым.

Очевидно, что вершины помещенные в СТЕК2, образуют некоторый путь . причем вершина ν переносится в СТЕК2 только тогда , когда СПИСОК[ ν ] т.е. когда все ребра, инцедентные этой вершине , представлены в СТЕКе1 (парами соседних вершин).

Отсюда следует что по окончанию алгоритма СТЕК2 содержит эйлеров цикл.

3 v:= произвольная вершина графа

5 WHILE СТЕК 1 = do BEGIN

1.3 Алгоритмы с возвратом

Рассмотрим теперь задачу нахождения путей, проходящих ровно один раз через каждую вершину (а не через каждое ребро) графа. Путь с таким свойством называется гамильтоновым путём, а цикл — гамильтоновым циклом. Пример гамильтонова пути в графе и графа, в котором такого пути не существует, показан на рис. 8. Несмотря на кажущееся сходство задач, пути их решения совершенно различны.

а) Гамильтонов путь в графе б) Гамильтонов путь не существует

Рис. 8. Различные типы графов

В отличие от эйлеровых путей для гамильтоновых путей не известно ни одного простого необходимого и достаточного условия существования. Не известен также алгоритм, который проверял бы существование гамильтонова пути в произвольном графе, используя число шагов, ограниченное многочленом от n (количество вершин в графе)

Очевидным алгоритмом нахождения гамильтонова пути в графе является полный перебор всех возможностей: генерируем все n ! различных последовательностей вершин и для каждой проверяем, определяет ли она гамильтонов путь. Такие действия потребуют по крайней мере n ! n шагов, а такая функция растет гораздо быстрее, чем произвольный многочлен и даже быстрее, чем экспоненциальная функция вида а n (а>1).

Однако существует общий метод, позволяющий значительно сократить число шагов в алгоритмах типа полного перебора. Для применения этого метода искомое решение должно иметь вид последовательности x 1 . xn >. Идея метода состоит в следующем.

Строим наше решение последовательно, начиная с пустой последовательности, т.е. последовательности длины 0. Имея некоторое частичное решение x 1 . xi >, стараемся найти такое допустимое значение xi +1 , относительно которого мы не можем сразу заключить, что x 1 . xi , xi +1 > можно расширить до некоторого решения (а мо-жет быть x 1 . xi , xi +1 > уже является решением). Если такое предполагаемое, но еще не использованное значение xi +1 существует, то мы добавляем его к нашему частичному решению и продолжаем процесс для последовательности x 1 . xi , xi +1 >. Если его не существует, то мы возвращаемся к частичному решению x 1 . xi -1 > и продолжаем наш процесс, отыскивая новое, еще не

использованное допустимое значение xi ’ Такие алгоритмы называют­ся алгоритмами с возвратом ( backtracking ).

Точнее говоря, мы предполагаем, что для каждого k > 0 существует некоторое множество А k , из которого мы будем выбирать кандидатов для k-й координаты частичного решения. Очевидно, что множества Ak должны быть определены таким образом, что для каждого целочисленного решения x 1 . xn > нашей задачи и для каждого k n множество Ak содержало бы элемент х^ (на практике А k может содержать и «лишние» элементы, не появляющиеся в k-й координате ни одного целочисленного решения).

Предполагаем также, что существует некоторая простая функция Р, которая произвольному частичному решению x 1 . xi > ставит в соответствие

если последовательность x 1 . xi > нельзя расширить до решения и

если значение xi , допустимо для частичного решения x 1 . xi -1 >. Это не означает, что x 1 . xi -1 > обязательно расширяется до полного решения.

Этот процесс можно записать в виде следующей схемы алгоритма

IF существует еще неиспользованный элемент у А k ,

такой, что Р(х[1]. x [ k — l ], у)

x [ k ] := у; <элемент у использован>IF x [ l ]. x [ k ]> является целочисленным решением

THEN write(x[l]. x[k]);

все элементы множества Ak вновь становятся неиспользованными>

Этот алгоритм находит все решения в предположении, что множества AK — конечны, и что существует такое n , что P x 1 . xi > = false для всех x 1 A 1, …, xn An . Последнее условие означает, что все решения имеют длину меньше n . Можно доказать и более общее свойство, а именно.

Пусть S > 0 и пусть x 1 . xs -1 > — некоторое частичное решение, построенное алгоритмом. Тогда, начиная с итерации цикла 3, для которого k = s , X [ i ] = Xi , 1 i ^ s, алгоритм генерирует все целочисленные решения, являющиеся расширением последовательности x 1 . xs -1 >, и приходит к состоянию, когда k = s — 1.

Последнее свойство приводит непосредственно к рекурсивному варианту алгоритма с возвратом.

1 PROCEDURE AP ( k );

последовательности Х[1]. X [ k — l ]; массив Х — глобальный>

3 FOR y Ak такого, что Р(х[1]. x [ k — l ], у) DO

4 BEGIN X [ k ]:= y ;

5 IF x [ l ], . X [ k ] есть целочисленное решение

6 THEN write(X[l]. X[k]);

Применим алгоритм с возвратом для нахождения гамильтонова цикла в графе G = V , E >. Каждый такой цикл можно представить последовательностью x 1 , x 2 , . xn +1 > такой, что x 1 = xn +1 = v , где v — некоторая фиксированная вершина графа и xi xj для 1 i j k = V.

Граф G = V , E > представим списками инцидентности

СПИСОК[ v ], v V . Тогда процедура для нахождения всех гамильтоновых циклов, являющихся расширением последовательности x 1 . xk -1 >

1 PROCEDURE гамильт(К);

3 FOR у СПИСОК [x[k-1]] DO

4 IF(k = n+1) and (y = v0)

5 THEN write(x[l]. x[n], v0)

6 ELSE IF DOP[y] THEN

8 x[k] := y; DOP[y] := false;

FOR v V DO DOP [ v ] := true ;

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

1.4 Нахождение кратчайших путей в графе

Будем рассматривать ориентированные графы G = V , E >, дугам которых приписаны веса. Это означает, что каждой дуге ( u , v ) E поставлено в соответствие некоторое вещественное число a ( u , v ), назы­ваемое весом данной дуги. Полагаем, что a ( u , v )= , если не существует дуга (u, v). Если последовательность вершин определяет путь в графе G, то его длина определяется как сумма

Нас будет интересовать нахождение кратчайшего пути между двумя фиксированными вершинами s , t V . Длину такого пути обозначим d ( s , t) и назовем расстоянием от s до t (расстояние, определенное таким образом, может быть и отрицательным). Если не существует ни одного пути из s в t, то полагаем d ( s , t ) = . Отметим, что если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем. Практическая интерпретация:

1) вершины — города, дуги — пути между городами, длины которых представлены весами. Ищем кратчайшие пути между городами;

2) вес дуги — стоимость (или время) передачи информации между вершинами. Тогда ищем самый дешевый (или самый скорый) путь передачи информации.

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

Действительно, для произвольных s , t V ( s t ) существует вершина v такая, что

d ( s , t ) = d ( s , v ) + d ( v , t ).

Таким свойством обладают предпоследние вершины кратчайшего пути из s в t. Далее мы можем найти вершину и, для которой d ( s , v ) = d ( s , u ) + d ( u , v ) и т.д. Из условия положительности длины всех контуров следует, что последовательность t, v, u. не содержит повторений и заканчивается вершиной s. Перечислив вершины в обратном порядке, найдем кратчайший путь из s в t.

Алгоритм для нахождения кратчайшего пути можно построить с использованием стека, куда последовательно заносим вершины t, v, u, . s:

2 СТЕК := ; СТЕК t ; v := t ;

5 u := вершина , для которой d[v] = d[u] + a[u, v]

Отметим, что если выбор вершины и в строке 5 происходит в результате просмотра всех вершин, то сложность нашего алгоритма O( n 2 ). Если же будем просматривать только список ПРЕДШ[ v ], содержащий все вершины и, такие, что u -^ v , то сложность будет 0(т).

1.5 Кратчайшие пути от фиксированной вершины

Суть большинства алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t состоит в следующем.

При данной матрице весов дуг a [ u , v ], u , v V, вычисляем некото­рые верхние ограничения d [ v ] на расстояния от вершины s до всех v V .

Каждый раз, когда окажется,

что D [ u ]+ a [ u , v ] D [ v ] (1),

оценку D [ v ] улучшаем: D [ v ] := D [ u ]+ a [ u , v ]. Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно. Легко показать, что значение каждой из переменных D [ v ] в этом случае равно кратчайшему пути от s к v.

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

Следует иметь в виду, что на эффективность алгоритма очень сильное влияние оказывает очередность, в которой выбираются вершины u, v для проверки условия (1).

Рассмотрим общий алгоритм, определяющий расстояния от некоторой фиксированной вершины s (назовем ее источником) до всех остальных вершин графа. Обычно этот алгоритм называют алгоритмом Форда-Беллмана. При работе алгоритма предполагается, что граф не имеет контуров отрицательной длины.

2 FOR v V DO D[v] := a[s, v]; D[s]:= 0;

3 FOR k := 1 TO n-2 DO

5 FOR u V DO D[v] := min(D[v], D[u]+a[u, v])

Очевидно, что сложность алгоритма есть 0(п 3 ). В практике мы можем закончить вычисления, когда выполнение цикла 4 не вызывает изменения ни одной из переменных D [ v ], v V . Это может произойти при k n -2, однако такая модификация алгоритма не изменит существенным образом его сложности. Для редких графов ( m « n 2 ) удобнее представлять граф списками инцидентности ПРЕДШ[ v ], v V . В этом случае заменим строку 5 на

FOR u ПРЕДШ [v] DO D[v] := min(D[v], D[u]+a[u, v]). Получим алгоритм, имеющий сложность O ( n * m ). На рис. 9 приведен пример, иллюстрирующий работу алгоритма Форда-Беллмана. Здесь циклы 4, 5 выполняются в порядке возраста­ния номеров вершин.

Рис. 9. Работа алгоритма Форда-Беллман a

1.6 Алгоритм Двйкстры

Существуют более эффективные алгоритмы для двух важных случаев:

1) веса всех дуг неотрицательны;

2) граф не имеет контуров.

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

Обобщенно он может быть записан следующим образом.

2 FOR v V DO D[v] := a[s, v]; D[s] := 0;

6 u := произвольная вершина t T , <такая, что

8 FOR v Т DO D[v] — min(D[v], D[u]+a[u, v])

Чтобы пояснить работу алгоритма, покажем, что инвариантом цикла 4 является следующее условие:

для каждой вершины D [ v ]= d ( s , v ), v V \ T

для каждой вершины D [ v ]= длине кратчайшего из тех путей (1) v Т из s в v, для которых предпоследняя вершина принадлежит множеству V \ Т.

В самом деле, в строке 5 мы находим вершину u Т такую, что значение D [ u ] является минимальным из всех значением D [ t ] для t Т. Причем, D [ u ]= d ( s , u ).

Это действительно так. Если кратчайший путь из s в u имеет длину, меньше D [ u ], то, (в силу второй части условия (1)), его предпоследняя вершина принадлежит множеству Т. Пусть t — первая вершина пути, принадлежащая множеству Т. Начальный отрезок нашего пути из s в t составляет кратчайший путь из s в t, причем его предпоследняя вершина не принадлежит множеству Т. По первой части условия (1) имеем:

Используя предположение о неотрицательности весов, получаем

вопреки принципу, по которому была выбрана вершина u.

Таким образом D [ u ] = d ( s , u ) и мы можем в строке 7 удалить u из множества Т, не нарушая 1-ой части условия (1). Чтобы обеспечить выполнение и второй части условия (1), нужно проверить пути из s в v Т, предпоследняя вершина в которой есть u, и уточнить оценки D [ v ], v Т. Именно это выполняет цикл 8.

Очевидно, что условие (1) выполняется при входе в цикл 4. По окончании работы алгоритма Т = , а следовательно, согласно условию (1),

Оценим сложность алгоритма Дейкстры. Цикл 4 выполняется n -1 раз, прчем каждое его выполнение требует O ( n ) шагов:

O ( n ) шагов для нахождения вершины u в строке 6 и

O ( n ) шагов для выполнения цикла 8.

Таким образом общая сложность алгоритма есть O ( n 2 ).

При удачном подборе структуры данных можно получить вариант алгоритма со сложностью O ( mlog 2 n ). Для этого множество Т нужно представить бинарным деревом с высотой O ( mlog 2 n ) и с таким свойством, что для произвольных его вершин u и v ,

если u — сын v, то D [ u ] D [ v ]. (2)

Вершина и, для которой D [ u ] минимально, является тогда корнем дерева. Этот корень можно устранить за O ( log n ) шагов, сохраняя свойство уменьшения значения D [ j ] на каждом пути до корня. Достаточно сместить на место корня его сына s с большим (или равным) значением D [ j ], затем на освободившееся место передвинуть сына вершины s с большим значением D [ j ] и т.д.

Если граф представлен списками инцидентности, то строку 8 можно заменить на

FOR v СПИСОК [u] DO

D [ v ] := D [ u ] + a ( u , v );

передвинуть вершину v в дереве в направлении корня так, чтобы сохранить условие (2)

Если существует таблица указателей на вершины нашего дерева, то передвижение вершины v может быть осуществлено за O ( log n ) шагов.

В алгоритме, модифицированном таким способом, каждая дуга графа анализируется ровно один раз, причем с этим связано O ( log n ) шагов на перемещение соответствующей вершины в дереве, представляющем множество Т. Это дает в сумме O ( mlog n ) шагов. Сюда нужно добавить O ( nlog n ) шагов, необходимых для построения нашего дерева и для устранения n -1 раз из него корня. Общая сложность алгоритма есть O ( mlog n ).

1.7 Пути в бесконтурном графе

Рассмотрим второй случай, для которого известен алгоритм нахождения расстояний от фиксированной вершины за время O ( n 2 ), a именно, случай, когда граф является бесконтурным.

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

Пример такой нумерации приведен на рис. 10.

Рис. 10. Самый длинный путь в бесконтурном графе

Для доказательства рассмотрим алгоритм, реализующий такую перенумерацию.

В качестве исходных данных будем использовать граф (ориентированный, бесконтурный) G = V , E >, заданный списками инцидентности СПИСОКМ , v V . Результатом работы алгоритма для каждой вершины v V является номер N [ v ] такой, что для произвольной дуги ( u , v ) E выполняется неравенство N [ u ] N [ v ].

2 FOR v V DO nz [ v ] := 0;

4 FOR у СПИСО K[u] DO nz[v] := nz[v]+l;

7 IF nz[v] = 0 THEN СТЕК

9 WHILE СТЕК DO BEGIN

11 num := num + 1; N[u] := num;

12 FOR v C ПИ COK[u] DO BEGIN

14 IF nz[v] = 0 THEN СТЕК

Алгоритм основывается на следующем факте: в произвольном бесконтурном графе существует вершина, в которую не заходит ни одна дуга.

Чтобы убедиться в этом, выберем произвольную вершину w 1 графа, затем некоторую вершину w 2 , такую, что w 2 → w 1 , затем вершину

w 3 , такую, что w 3 → w 2 , и т.д. Через конечное число шагов мы должны дойти до некоторой вершины wi , в которую не заходит ни одна дуга, т.к. в силу бесконтурности графа ни одна вершина в последовательности w 1 , w 2 , w 3 . не может повторяться.

В нашем алгоритме вершины, в которые не заходит ни одна дуга, накапливаются в стеке. В строке 10 выбирается верхний элемент стека и (это мог бы быть произвольный элемент стека) и этой вершине присваивается самый маленький из еще неиспользованных номеров. Таким образом мы гарантируем, что все дуги, выходящие из этой вершины, ведут к вершинам с большими номерами. Затем вершина и вместе с выходящими из нее дугами удаляется из графа. Это приводит к уменьшению на 1 числа дуг, заходящих в каждую вершину v , такую, что и → v. Это число запоминается в nz [ v ]. Если для какой-либо из вершин v это число сводится к нулю, то v помещается в стек.

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

Мы видим, что каждая дуга анализируется один раз в строке 4 и один раз в строке 12. Таким образом сложность алгоритма есть O ( m ).

Рассмотрим теперь алгоритм нахождения расстояний от источника до всех вершин в бесконтурном графе. При этом будем считать, что вершины графа уже перенумерованы, так что каждая дуга идет из вершины с меньшим номером в вершину с большим номером. Кроме того, будем считать, что граф задан списками инцидентности СПИСОК[ v ], v V .

Результатом работы алгоритма будут являться расстояния от V 1 до всех вершин графа, а именно D [ vi ]= d ( v 1 , vi ), i=1..n.

3 FOR j := 2 TO n DO D[vj]:= ;

4 FOR j := 2 TO n DO

Можно доказать (это нетрудно) индукцией по j , что после выполнения цикла 4 для некоторого значения j выполняется равенство

Это вытекает из того факта, что все промежуточные вершины кратчайшего пути из vi в vj имеют номера меньше j.

Сложность алгоритма есть O ( m ), т.к. каждая дуга ( vi , vj ) анализируется в строке 5 ровно один раз.

Последние два алгоритма находят применение, например, в методах управления выполнения некоторого проекта. Эти методы основаны на построении графа, дуги которого соответствуют некоторым задачам, составляющим проект, а их веса указывают на время, необходимое для решения отдельных задач. Кроме того, мы предполагаем, что для произвольных дуг ( u , v ) и ( v , t ) этого графа задача, изображаемая дугой (u, v) должна быть закончена перед началом решения задачи, изображаемой дугой (v, t). Легко заметить, что такой граф будет бесконтурным. Нашей целью является нахождение самого длинного пути из вершины s , соответствующей началу проекта, до вершины t, соответствующей его окончанию (см. путь на рис. 33). Такой путь называется критическим путем. Его длина определяет время, необходимое для реализации всего проекта. Очевидно, эта задача сводится к задаче о кратчайшем пути простым изменением знака каждого веса а[ u , v], где u → v , на обратный.

1. Построить граф. Осуществить поиск в глубину в графе. Стандартным способом устранить рекурсию.

2. Построить граф. Осуществить поиск в ширину в графе.

3. Построить граф (Стягивающие деревья (каркасы)) Осуществить поиск в глубину в графе.

4. Построить граф (Стягивающие деревья (каркасы)) Осуществить поиск в ширину в графе.

5. Построить граф. Осуществить отыскание фундаментального множества циклов в графе

6. Построить граф. Найти Эйлеров путь в графе.

7. Решить задачу нахождения пути, проходящего ровно один раз через каждую вершину (а не через каждое ребро) графа. (гамильтоновый путь)

8. Рассмотрите пример выбора кратчайшего пути для графа, показанного на рис.10.

9. Рассмотрите пример выбора кратчайшего пути, показанный на рис.11. Узел 7 будем считать источником, а узел 2 стоком.

10. Рассмотрите пример выбора кратчайшего пути, показанный на рис.12. Найдите кратчайший путь от склада1 до склада 3. Пронумерованные узлы в кружках обозначают номер склада.

14. Компания имеет восемь крупных оптовых складов, размещенных в нескольких штатах. На рис.12 представлен граф. Необходимо найти кратчайший путь от склада 1 до склада 8.

15. Компания имеет восемь складов в нескольких городах. Граф представлен на рис.12. Найдите кратчайший путь от склада4 до склада 8.

1. Тема и цель работы.

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

3. Описание алгоритмов.

4. Листинги и результаты программ.

5. Ответы на контрольные вопросы.

6. Резюме проделанной работы.

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

2. Поиск в глубину в графе.

3. Поиск в ширину в графе.

4. Стягивающие деревья.

5. Нахождение стягивающего дерева методом поиска в ширину.

6. Нахождение стягивающего дерева методом поиска в глубину.

7. Фундаментальное множество циклов в графе.

8. Нахождение множества фундаментальных циклов графа.

9. Эйлеровы пути и циклы. Необходимое и достаточное условие су­ществования эйлерова пути.

10. Нахождение эйлерова цикла в графе.

11. Нахождение гамильтоновых циклов графа.

12. Нахождение кратчайших путей в графе.

13. Алгоритм Форда-Беллмана.

14. Алгоритм Дейкстры.

1. Г. Вагнер, Основы исследования операций,т. 1, Москва. : Мир, 1972.-335 с.

2. Павлов А.А., Гриша С.Н.,Основы системного анализа и проектирования. -К. : Высш. шк., 1991.-367 с.

3. Бахвалов Н.С., Численные методы-Москва.: Наука, главная редакция физико-математической литературы, 1973.-630 с.

4. Фурунджиев Р.И. и др., Применение математических методов и ЭВМ: Практикум: Учеб. пособие для вузов.-Мн:Высш. шк.,1988.-1991с.:илл.

5. Перегудов Ф.И., Тарасенко Ф.П., Введение в системный анализ : Учеб. пособие для вузов.-М.: Высш. шк., 1989.-367 с.: илл.

6. Банди Б., Основы линейного программированияю, пер. с англ.-М: Радио и связь, 1989.-176 с.: илл.

7. Полак Э, Численные методы оптимизации. Единичный подход, пер. с англ. Ф.Н. Ерешко. Под ред. И.А. Вателя.-М: Мир, 1974, 376 c. с черт.

Добавить комментарий