Граф (математика)
Материал из Википедии — свободной энциклопедии
В математической теории графов и информатике граф — это совокупность объектов со связями между ними.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа (орграф), в котором вершины — это статьи, а дуги (ориентированные рёбра) — это связи, созданные гиперссылками.
Содержание |
[править] Определения
Теория графов не обладает устоявшейся терминологией. В различных статьях под одними и теми же терминами понимаются разные вещи. Приводимые ниже определения -- наиболее часто встречаемые.
[править] Граф
Граф или неориентированный граф 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 w ведёт от вершины v к вершине w.
[править] Смешаный граф
Смешаный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G: = (V,E,A), где V, E и A определены так же, как выше.
Понятно, что ориентированный и неориентированный графы являются частными случаями смешаного.
[править] Прочие связанные определения
Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром. Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.
Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:
- Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.
- Всякий простой неэлементарный путь содержит элементарный цикл.
- Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).
Бинарное отношение на множестве вершин графа, заданное как "существует путь из u в v", является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.
[править] Дополнительные характеристики графов
Граф называется:
- связным, если для любых вершин u,v есть путь из u в v.
- деревом, если он связный и не содержит простых циклов.
- полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.
- двудольным, если его вершины можно разбить на два непересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2.
- планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
- взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.
[править] Обобщение понятия графа
Простой граф является одномерным симплициальным комплексом.
Более абстрактно, граф можно задать как тройку , где V и E — некоторые множества (вершин и рёбер, соотв.), а — функция инцидентности (или инцидентор), сопоставляющая каждому ребру e∈E (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов). Частными случаями этого понятия являются:
- ориентированные графы (орграфы) — когда всегда является упорядоченной парой вершин;
- неориентированные графы — когда всегда является неупорядоченной парой вершин;
- смешанные графы — в котором встречаются как ориентированные, так и неориентированные рёбра и петли;
- мультиграфы — графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;
- псевдографы — это мультиграфы, допускающие наличие петель;
- простые графы — не имеющие петель и кратных рёбер.
Под данное выше определение не подходят некоторые другие обобщения:
- гиперграф — если ребро может соединять более двух вершин.
- ультраграф.
[править] Популярные программы для визуализации графов
- Graphviz
- aiSee (на русском)
- Список Давида Эпстейна (на английском)
- Список Роберто Тамассиа (на английском)
- Список Георга Зандера (на английском)