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

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

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

Содержание

Терминология теории графов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Теория графов в химии
  • Теория графов в информатике и программировании
  • Теория графов в экономике

См. также

Литература

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


 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home