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

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

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

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

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

[править] Терминология теории графов

До настоящего времени Терминология теории графов не определена совсем строго. В частности в монографии Гудман, Хидетниеми, 1981 сказано «В программистском мире нет единого мнения о том, какой из двух терминов "граф" или "сеть". Мы выбрали термин "сеть", так как он, по-видимому, чаще встречается в прикладных областях»

[править] Устоявшиеся определения наиболее общих видов графов

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

Неориентированный граф — это пара множеств (V,E), где V — множество элементов, называемых вершинами, а E — подмножество множества неупорядоченных пар вершин из V, называемых рёбрами. Говорят, что вершины u и v соединены ребром, если .

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

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

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

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

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

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

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

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

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

Ориентированный граф (сокращенно орграф) G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — это упорядоченная пара вершин (v,w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v w ведёт от вершины v к вершине w, при этом вершина w смежна с вершиной v.

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

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

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

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

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

[править] Применение теории графов

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

[править] Классические задачи теории графов

• Задача о раскраске карты (достаточно 4-х красок для карты на сфере (плоскости))
• Транспортная задача

[править] См. также

• Словарь терминов теории графов
• теория графов и применение её в информатике

[править] Литература

• Оре Теория графов 1965
• Харари Теория графов 1973
• Харари, Палмер Теория графов 1977
• Зыков Теория графов 1987

Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её.