Русская Википедия:Граф (математика)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Другие значения

Файл:Sample graph.svg
Неориентированный граф с шестью вершинами и семью рёбрами

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

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

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

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

Определения

Шаблон:Main

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

Простой граф

Файл:Undirected.svg
Пример диаграммы неориентированного графа

Определение. Простой граф <math>G(V,E)</math> есть совокупность двух множеств – непустого множества <math>V</math> и множества <math>E</math> неупорядоченных пар различных элементов множества <math>V</math> . Множество <math>V</math> называется множеством вершин, множество <math>E</math> называется множеством рёбер

<math>G(V,E) = \left \langle V,E \right \rangle, \quad V \ne \varnothing , \quad E \subseteq V \times V , \quad \left \{ v,v \right \} \notin E, \quad v \in V </math>,

то есть множество <math>E</math> состоит из 2-элементных подмножеств множества <math>V</math>.

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

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

  • Вершина (узел, точка) (Шаблон:Lang-en) графа <math>G</math> есть элемент множества вершин <math>v \in V(G)</math>;
  • Ребро (линия) (Шаблон:Lang-en) графа <math>G</math> есть элемент множества ребер <math>e \in E(G)</math>, или <math>e = \left \{ v_1, v_2 \right \}</math>, где <math>v_1 \in V(G), \quad v_2 \in V(G)</math>;
  • Элементами графа <math>G</math> называются его вершины <math>v \in V(G)</math> и рёбра <math>e \in E(G)</math> графа;
  • Порядок (Шаблон:Lang-en) графа <math>G</math> есть кардинальное число множества вершин <math> n = |V(G)|</math> или, другими словами, количество вершин;
  • Размер (Шаблон:Lang-en) графа <math>G</math> есть кардинальное число множества ребер <math> m = |E(G)|</math> или, другими словами, количество ребер;
  • Вершина <math>v</math> инцидентна (Шаблон:Lang-en) ребру <math>e</math>, если <math>v \in e</math>; тогда еще говорят, что <math>e</math> есть ребро при <math>v</math>;
  • Концевые вершины (концы) (Шаблон:Lang-en) есть две вершины, инцидентные ребру. Ребро соединяет (Шаблон:Lang-en) свои концевые вершины;
  • Соседние (смежные) вершины (Шаблон:Lang-en) есть такие вершины <math>v_1</math> и <math>v_2</math> что <math>\left \{v_1, v_2 \right \} \in E(G)</math> или, другими, словами обе вершины являются концевыми для одного ребра;
  • Смежные ребра (Шаблон:Lang-en) это ребра, инцидентные одной вершине или <math>e_1=\left \{ v,v_1 \right \} </math> и <math>e_2=\left \{ v,v_2 \right \} </math> - смежные;
  • Степень (валентность) вершины (Шаблон:Lang-en) <math>\operatorname\mathit{d}\left(v\right)</math> есть количество инцидентных ей рёбер.
  • Изолированной вершиной (Шаблон:Lang-en) называется вершина со степенью <math>d(v)=0</math> , то есть не является концом ни для одного ребра;
  • Висячей вершиной (листом) (Шаблон:Lang-en) называется вершина со степенью <math>d(v)=1</math>, то есть которая является концом ровно одного ребра.

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

Псевдограф

Псевдограф <math>G(V,E)</math> есть совокупность двух множеств – непустого множества <math>V</math> и множества <math>E</math> неупорядоченных пар элементов множества <math>V</math>.

<math>G(V,E) = \left \langle V,E \right \rangle, \quad V \ne \varnothing , \quad E \subseteq V \times V </math>

В множестве ребер псевдографа разрешен элемент <math>\left \{ v,v \right \} \in E(G)</math>.

  • Петлёй (Шаблон:Lang-en) называется элемент <math>e=\left\{v,v \right \}</math>, являющийся ребром, у которого концевые вершины совпадают.

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

Мультиграф

Файл:Multi-pseudograph.svg
Псевдомультиграф с кратными рёбрами (красные) и петлями (синие).

Мультиграф <math>G(V,\mathbf E)</math> есть совокупность двух множеств – непустого множества <math>V</math> и мультимножества <math>\mathbf E</math> неупорядоченных пар различных элементов множества <math>V</math>.

<math>G(V,\mathbf E) = \left \langle V, \mathbf E \right \rangle, \quad V \ne \varnothing , \quad \mathbf E \subseteq V \times V \quad \left \{ v,v \right \} \notin \mathbf E, \quad v \in V </math>
  • Кратными рёбрами называются одинаковые элементы мультимножества <math>\left \{e,e, \dots ,e \right \} \in \mathbf E</math>, то есть ребра, чьи концевые вершины совпадают.

Другими словами Если <math>E</math> не множество, а семейство, то есть если <math>\mathbf E</math> содержит одинаковые элементы, то такие элементы называются кратными рёбрами, а граф называется мультиграфом Шаблон:Sfn.

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

Псевдомультиграф <math>G(V,\mathbf E)</math> есть совокупность двух множеств – непустого множества <math>V</math> и мультимножества <math>\mathbf E</math> неупорядоченных пар элементов множества <math>V</math>.

<math>G(V,\mathbf E) = \left \langle V, \mathbf E \right \rangle, \quad V \ne \varnothing , \quad \mathbf E \subseteq V \times V </math>

Другими словами, если <math>\mathbf E</math> – семейство, содержащее одинаковые элементы (кратные ребра), и <math>\mathbf E</math> может содержать петли, то граф называется псевдомультиграфомШаблон:Sfn.

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

Файл:Directed.svg
Ориентированный граф

Ориентированный граф (орграф) (Шаблон:Lang-en) <math>G(V,E)</math> есть совокупность двух множеств – непустого множества <math>V</math> и множества <math>E</math> дуг или упорядоченных пар различных элементов множества <math>V</math>

<math>G(V,E) = \left \langle V,E \right \rangle, \quad V \ne \varnothing , \quad \left \langle \left \{ v_1,v_2 \right \}, \prec \right \rangle \in E, \quad v \in V </math>.

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

<math> init: E \rightarrow V, \quad ter: E \rightarrow V</math>,

где отображение <math> init: E \rightarrow V </math> ставит в соответствие каждой дуге ее начальную вершину (начало дуги) <math> init(e) </math>, а отображение <math> ter: E \rightarrow V </math> ставит в соответствие каждой дуге ее конечную вершину (конец дуги) <math> ter(e) </math>. Говорят что дуга <math>e </math> ведет из <math> init(e) </math> в <math> ter(e) </math>

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

Шаблон:Main Смешанный граф (Шаблон:Lang-en) <math>G(V,E,U)</math> — это совокупность трех множеств – непустого множества вершин <math>V</math>, и множества дуг <math>E</math> или упорядоченных пар различных элементов множества <math>V</math> и множества ребер <math>U</math> неупорядоченных пар различных элементов множества <math>V</math>

<math>G(V,E,U) = \left \langle V,E,U \right \rangle, \quad V \ne \varnothing , \quad \left \langle \left \{ v_1,v_2 \right \}, \prec \right \rangle \in E, \quad \left \{ v_3 , v_4 \right \} \in U , \quad v \in V</math>.

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

<math> init: E \rightarrow V, \quad ter: E \rightarrow V</math>

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

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

Граф <math>G</math> называется изоморфным графу <math>H</math>, если существует биекция <math>f</math> из множества вершин графа <math>G</math> в множество вершин графа <math>H</math>, обладающая следующим свойством: если в графе <math>G</math> есть ребро из вершины <math>A</math> в вершину <math>B</math>, то в графе <math>H</math> должно быть ребро из вершины <math>f(A)</math> в вершину <math>f(B)</math> и наоборот — если в графе <math>H</math> есть ребро из вершины <math>A</math> в вершину <math>B</math>, то в графе <math>G</math> должно быть ребро из вершины <math>f^{-1}(A)</math> в вершину <math>f^{-1}(B)</math>. В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Более абстрактно, граф можно задать как тройку <math>(V, E, \varphi)</math>, где <math>V</math> и <math>E</math> — некоторые множества (вершин и рёбер, соотв.), а <math>\varphi</math> — функция инцидентности (или инцидентор), сопоставляющая каждому ребру <math>e\in E</math> (упорядоченную или неупорядоченную) пару вершин <math>u</math> и <math>v</math> из <math>V</math> (его концов). Частными случаями этого понятия являются:

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

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

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

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

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

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

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

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

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

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

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

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

Размер занимаемой памяти: <math>O(|V|+|E|)</math>.

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

Список рёбер

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

Размер занимаемой памяти: <math>O(|E|)</math>.

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

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

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

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

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

Разработана серия коммерческих программ для построения графов, так, построение графов лежит в основе прикладных программных пакетов фирмы 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[1].

См. также

Шаблон:Викисловарь

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Граф_(математика)&oldid=9619843