Для чего нужны графы

Граф: что это такое в математике, какие существуют его виды и другое

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

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

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

Что такое граф или теория графов для чайников

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

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

Какие бывают графы

• ориентированные;
• неориентированные.

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

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

Какими еще бывают графы

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

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

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

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

Взвешенный граф — это такой граф, у которого вершинам и/или ребрам присваивается какое-то числовое значение, это значение означает «вес» или «стоимость» ребра или вершины.

Граф-дерево — это такой вид графа, у которого все вершины связаны без циклов, а строго в иерархическом порядке. У такого графа у любых двух вершин будет только одно ребро или путь соединения. Это самый распространенный вид графа, который используется человеком вне науки. В жизни такие графы можно выделить при организации управленческой структуры в школах, организациях, структурах и государствах. Суть такого графа заключается в том, что у него есть «корень графа», то есть это та вершина, с которой начинается весь граф. У людей это может быть: директор, старший менеджер, глава ведомства, мэр, президент и т. д. Граф-дерево может выглядеть вот так:

Для чего нужны графы

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

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

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

Вершины называются смежными, если их соединяет ребро. Например, на рис. смежны вершины V₁ и V₂ , так как их соединяет ребро R₁₂ .

Множество V , R являются конечными – мы можем перечислить все вершины и ребра графа. Количество вершин и количество ребер графа определяют мощности множеств V и R . Так, количество вершин графа G ровно 5, а количество ребер равно 8.

Ребро и любая из его двух вершин называются инцидентными. Под степенью вершин подразумевается количество инцидентных ей ребер. Так, степень вершин V₁ равно 3, а степень вершин V ₅ равна 4.

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

Длина маршрута равна количеству ребер, входящих в него.

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

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

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

Взвешенные графы.

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

Полный граф
Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром. В полном графе каждая его вершина принадлежит одному и тому же числу ребер. Для задания полного графа достаточно знать число его вершин. Полный граф с n вершинами обычно обозначается через K_n .

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

Двудольный граф

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

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

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

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

На рисунке показано плоское представление графа G с тремя гранями: (1, 5,4,1), (1, 3, 2,4,1) , (1,2,3,1). Часть плоскости, ограниченная простым циклом (1,2,4,1), гранью не является, так как содержит цикл (1, 2, 3,1). Простой цикл, ограничивающий грань, называется границей грани. Две грани будем называть соседними, если их границы имеют хотя бы одно общее ребро.

В данном графе часть плоскости, ограниченная простым циклом (1,2,3,4,1), является гранью, так как ребро (4,5), расположенное внутри грани, не образует цикла.

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

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

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

Два графа гомеоморфны (или тождественны с точностью до вершин степени 2), если они оба могут быть получены из одного и того же графа «включением» в его ребра новых вершин степени 2.

Гомеоморфные графы

Элементарным стягиванием называется такая процедура: берем ребро е (вместе с инцидентными ему вершинами, например, V и W ) и»стягиваем» его, то есть удаляем е и отождествляем V и W . Полученная при этом вершина инцидентна тем ребрам (отличным от е ), которым первоначально были инцидентны V или W .

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

Граф планарен тогда и только тогда, если он не содержит подграфов, стягиваемых в К₅ или к К _з.з .

Формула Эйлера

Для всякого плоского представления связного плоского графа без перегородок число вершин ( V ), число ребер ( Е ) и число граней с учетом бесконечной ( R ) связаны соотношением V –Е + R = 2 .

Пусть граф G — связный, плоский граф без перегородок. Определим значение алгебраической суммы V –Е + R для его произвольного плоского представления.

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

Заметим, что при таком удалении одного ребра число граней уменьшается на 1, так как при этом либо пропадет один простой цикл, либо два простых цикла преобразуются в один. Следовательно, значение разности Е — R при этом остается неизменным.

На рисунке ребра, которые мы удаляем, изображены кривыми. В полученном дереве обозначим число вершин — V_d , число ребер — E_d , число граней — R_d . Справедливо равенство Е — R = E_d — R_d .

В дереве одна грань, то есть Е — R = E_d — 1. Операция удаления ребер из графа не меняет число его вершин, то есть V = V_d . По теореме в дереве V_d — E_d = 1. Отсюда V — E_d = 1, то есть E_d = V — 1, а потому Е- R = V — 2 или V — Е + R = 2.

Итак, доказано, что если в плоском представлении связного графа без перегородок V вершин, Е ребер и R граней, то V — Е + R = 2 . Полученная формула называется формулой Эйлера.

Для чего нужны графы

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

Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.

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

Встречаются такие графы, ребрам которых поставлено в соответствие конкретное числовое значение, они называются взвешенными графами , а это значение – весом ребра .

Когда у ребра оба конца совпадают, т.е. оно выходит из вершины и входит в нее, то такое ребро называется петлей .

Классификация графов

Графы делятся на

• связные
  
• несвязные
  

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

В несвязном графе существует хотя бы одна вершина, не связанная с другими.

Графы также подразделяются на

• ориентированные
  
• неориентированные
  
• смешанные.

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

В неориентированном графе по каждому из ребер можно осуществлять переход в обоих направлениях.

Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.

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

Граф может быть представлен (сохранен) несколькими способами:

• матрица смежности;
• матрица инцидентности;
• список смежности (инцидентности);
• список ребер.

Использование двух первых методов предполагает хранение графа в виде двумерного массива (матрицы). Размер массива зависит от количества вершин и/или ребер в конкретном графе.

Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.
Число строк матрицы смежности равно числу столбцов и соответствует количеству вершин графа.

• 0 – соответствует отсутствию ребра,
• 1 – соответствует наличию ребра.

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

Матрица инцидентности (инциденции) графа — это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер. В ней указываются связи между инцидентными элементами графа (ребро(дуга) и вершина).

В неориентированном графе если вершина инцидентна ребру то соответствующий элемент равен 1, в противном случае элемент равен 0.

В ориентированном графе если ребро выходит из вершины, то соответствующий элемент равен 1, если ребро входит в вершину, то соответствующий элемент равен -1, если ребро отсутствует, то элемент равен 0.

Матрица инцидентности для своего представления требует нумерации рёбер, что не всегда удобно.

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

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

Преимущества списка смежности:

• Рациональное использование памяти.
• Позволяет быстро перебирать соседей вершины.
• Позволяет проверять наличие ребра и удалять его.

Недостатки списка смежности:

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

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

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

  Основными алгоритмами обхода графов являются

  Поиск в ширину подразумевает поуровневое исследование графа:

  • вначале посещается корень – произвольно выбранный узел,
  • затем – все потомки данного узла,
  • после этого посещаются потомки потомков и т.д.

  Вершины просматриваются в порядке возрастания их расстояния от корня.
  Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения требуемого условия (например, найти кратчайший путь из вершины 1 в вершину 6).
  Каждая вершина может находиться в одном из 3 состояний:

  • 0 — оранжевый – необнаруженная вершина;
  • 1 — зеленый – обнаруженная, но не посещенная вершина;
  • 2 — серый – обработанная вершина.

  Фиолетовый – рассматриваемая вершина.

  Применения алгоритма поиска в ширину

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

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

  Реализация на C++ (с использованием очереди STL)

  Результат выполнения
  

  Задача поиска кратчайшего пути
  Реализация на С++

  Результат выполнения
  
  

  Поиск в глубину – это алгоритм обхода вершин графа.

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

  Отсутствие последнего свидетельствует об одной из двух возможных ситуаций:

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

  Каждая вершина может находиться в одном из 3 состояний:

  • 0 — оранжевый – необнаруженная вершина;
  • 1 — зеленый – обнаруженная, но не посещенная вершина;
  • 2 — серый – обработанная вершина;

  Фиолетовый – рассматриваемая вершина.

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

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

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

  Реализация на C++ (с использованием стека STL)

  Результат выполнения
  
  Задача поиска лексикографически первого пути на графе.
  Реализация на C++

  Результат выполнения
  
  

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

  Реализация обхода графа в глубину на C++ (с использованием рекурсии)

  Результат выполнения
  

  Похожие публикации:

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