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

Материал из Википедии — свободной энциклопедии

У этого термина существуют и другие значения, см. Граф (значения).

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

В математической теории графов и информатике граф — это совокупность объектов со связями между ними.

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

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

Содержание

1 Определения
2 Обобщение понятия графа
3 Популярные программы для визуализации графов
4 См. также

[править] Определения

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

[править] Граф

Граф или неориентированный граф $G$ — это упорядоченная пара $G : = (V, E)$ , для которой выполнены следующие условия:

$V$ это множество вершин или узлов,
$E$ это множество пар (неупорядоченных) различных вершин, называемых рёбрами.

$V$ (а значит и $E$ ) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе ( $| V |$ )— порядком, число рёбер ( $| E |$ )— размером графа.

Вершины $u$ и $v$ называются концевыми вершинами (или просто концами) ребра $e = {u, v}$ . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Ребро называется петлёй, если его концы совпадают, то есть $e = {v, v}$ .

Степенью (deg 'v') вершины 'v' называют количество рёбер, для которых она является концевой (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

[править] Ориентированный граф

Ориентированный граф (сокращенно орграф) $G$ — это упорядоченная пара $G : = (V, A)$ , для которой выполнены следующие условия:

$V$ это множество вершин или узлов,
$A$ это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга — это упорядоченная пара вершин (v,w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v $\to$ w ведёт от вершины v к вершине w.

[править] Смешаный граф

Смешаный граф $G$ — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой $G : = (V, E, A)$ , где V, E и A определены так же, как выше.

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

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

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

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

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

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

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

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

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

[править] Обобщение понятия графа

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

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

ориентированные графы (орграфы) — когда $\varphi(e)$ всегда является упорядоченной парой вершин;
неориентированные графы — когда $\varphi(e)$ всегда является неупорядоченной парой вершин;
смешанные графы — в котором встречаются как ориентированные, так и неориентированные рёбра и петли;
мультиграфы — графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;
псевдографы — это мультиграфы, допускающие наличие петель;
простые графы — не имеющие петель и кратных рёбер.