Граф (математика)

Перейти к навигацииПерейти к поиску
Неориентированный граф с шестью вершинами и семью рёбрами

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

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

В качестве простейшего примера из жизни можно привести схему перелётов определённой авиакомпании, которая моделируется графом, где вершинами графа являются города, а рёбрами — рейсы, соединяющие пары городов. Дерево каталогов в компьютере также является графом: диски, папки и файлы являются вершинами, а рёбра показывают вложенность файлов и папок в папки и диски[1]. Строение Википедии моделируется ориентированным графом, в котором статьи — вершины графа, а гиперссылки — дуги (тематическая карта).

Графы являются основным объектом изучения теории графов.

Определения

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

Простой граф

Пример диаграммы неориентированного графа

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

,

то есть множество состоит из 2-элементных подмножеств множества .

Сопутствующие термины

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

  • Вершина (узел, точка) (англ.  vertex, node, point) графа есть элемент множества вершин ;
  • Ребро (линия) (англ.  edge, line) графа есть элемент множества ребер , или , где ;
  • Элементами графа называются его вершины и рёбра графа;
  • Порядок (англ.  order) графа есть кардинальное число множества вершин или, другими словами, количество вершин;
  • Размер (англ.  size) графа есть кардинальное число множества ребер или, другими словами, количество ребер;
  • Вершина инцидентна (англ. incident) ребру , если ; тогда еще говорят, что есть ребро при ;
  • Концевые вершины (концы) (англ. endvertices, ends) есть две вершины, инцидентные ребру. Ребро соединяет (англ. joins) свои концевые вершины;
  • Соседние (смежные) вершины (англ. neighbours, adjacent) есть такие вершины и что или, другими, словами обе вершины являются концевыми для одного ребра;
  • Смежные ребра (англ. adjacent edges) это ребра, инцидентные одной вершине или и - смежные;
  • Степень (валентность) вершины (англ. degree, valency) есть количество инцидентных ей рёбер.
  • Изолированной вершиной (англ. isolated) называется вершина со степенью , то есть не является концом ни для одного ребра;
  • Висячей вершиной (листом) (англ. leaf) называется вершина со степенью , то есть которая является концом ровно одного ребра.

Обычно граф изображают диаграммой: вершины – точками, ребра – линиями.

Псевдограф

Псевдограф есть совокупность двух множеств – непустого множества и множества неупорядоченных пар элементов множества .

В множестве ребер псевдографа разрешен элемент .

  • Петлёй (англ. loop) называется элемент , являющийся ребром, у которого концевые вершины совпадают.

Другими словами, если элементами множества E могут быть петли, то граф называется псевдографом [2].

Мультиграф

Псевдомультиграф с кратными рёбрами (красные) и петлями (синие).

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

  • Кратными рёбрами называются одинаковые элементы мультимножества , то есть ребра, чьи концевые вершины совпадают.

Другими словами Если не множество, а семейство, то есть если содержит одинаковые элементы, то такие элементы называются кратными рёбрами, а граф называется мультиграфом [2].

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

Псевдомультиграф есть совокупность двух множеств – непустого множества и мультимножества неупорядоченных пар элементов множества .

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

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

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

Ориентированный граф (орграф) (англ.  directed graph or dirgaph) есть совокупность двух множеств – непустого множества и множества дуг или упорядоченных пар различных элементов множества

.

совместно с двумя отображениями

,

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

Смешанный граф

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

.

совместно с двумя отображениями

Ориентированный и неориентированный графы являются частными случаями смешанного.

Изоморфные графы

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

Прочие связанные определения

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

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

Циклом называют цепь, в которой первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины и являются концами некоторого ребра, то согласно данному определению, последовательность является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если рёбра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются (за исключением начальной и конечной в случае цикла).

Простейшие свойства путей и циклов:

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

Бинарное отношение на множестве вершин графа, заданное как «существует путь из в », является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

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

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

Дополнительные характеристики графов

Граф называется:

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

Также бывает:

  • k-раскрашиваемым
  • k-хроматическим

Обобщение понятия графа

Простой граф является одномерным симплициальным комплексом.

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

  • эйлеровы графы — граф, в котором существует циклический эйлеров путь (эйлеров цикл);

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

Матрица смежности

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

Это наиболее удобный способ представления плотных графов.

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

  • Двумерный массив;
  • Матрица с пропусками;
  • Неявное задание (при помощи функции).

Матрица инцидентности

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

1
в случае, если связь «выходит» из вершины ,
−1,
если связь «входит» в вершину,
0
во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

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

Список смежности

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

Размер занимаемой памяти: .

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

Список рёбер

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

Размер занимаемой памяти: .

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

Языки описания и программы построения графов

Языки описания

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

Программы для построения

Разработана серия коммерческих программ для построения графов, так, построение графов лежит в основе прикладных программных пакетов фирмы ILOG (с 2009 года принадлежит корпорации IBM), среди других программ — GoView, Lassalle AddFlow, LEDA (есть бесплатная редакция).

Также существует свободная программа для построения графов igraph и свободная библиотека Boost.

Программы для визуализации

Для визуализации графов применяются следующие программные средства:

  • Graphviz (Eclipse Public License)
  • LION Graph Visualizer.
  • Графоанализатор — русскоязычная программа, с простым пользовательским интерфейсом (GNU LGPL; только для Windows).
  • Gephi — графическая оболочка для представления и изучения графов (GNU GPL, CDDL).
  • GRIN — русскоязычная программа для представления и изучения графов (freeware)
  • Библиотека GraphX — свободная библиотека для .NET для расчёта и отрисовки графов, использует WPF 4.0.
  • Библиотека MSAGL — свободная библиотека для .NET[3].

См. также

Примечания

  1. Буркатовская, 2014, с. 3.
  2. 1 2 3 Буркатовская, 2014, с. 6.
  3. Microsoft Automatic Graph Layout - Microsoft Research. research.microsoft.com. Дата обращения: 15 ноября 2015. Архивировано 14 мая 2012 года.

Литература

  • Буркатовския Ю. Б. Теория графов. — Томск: Издательство Томского политехнического университета, 2014. — Т. 1. — 200 с.
  • Дистель Р. Теория графов. — Новосибирск: Издательство Института математики им. С. Л. Соболева СО РАН, 2002. — 336 с. — ISBN 5-86134-101-Х.
  • Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
  • Касьянов В. Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. — С. 1104. — ISBN 5-94157-184-4.
  • Кирсанов М. Н. Графы в Maple. — М.: Физматлит, 2007. — 168 с. — ISBN 978-5-9221-0745-7.
  • Кормен Т. М. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1.
  • Оре О. Теория графов. — М.: Наука, 1968. — 336 с.
  • Графы // Энциклопедический словарь юного математика / Сост. А. П. Савин. — М.: Педагогика, 1985. — С. 86-88. — 352 с.
  • Салий В. Н., Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997. — ISBN 5-02-015033-9.
  • Уилсон Р. Введение в теорию графов. — М.: Мир, 1977. — 208 с.
  • Харари Ф. Теория графов. — М.: Мир, 1973.