| [Оглавление] | [<< страница] | [>>страница] |
Графы как структуры данных широко применяются при решении многих задач. Они могут использоваться для представления данных, моделей процессов, структур программ и т.д. Мы с вами рассмотрим два основных вопроса:
Необходимо отметить, что многие задачи, решаемые с использованием графов, относятся к задачам выбора. Все они могут быть, решены с помощью переборных алгоритмов. Однако сложность таких алгоритмов настолько велика, что многие практические задачи не могут быть решены за приемлемое время. Мы рассматрим некоторые из известных алгоритмов на графах, получивших практическое применение. Большинство из них основано на эвристических методах.
1. Основные определения
Граф G = (V,E) включает непустое множество V, называемое множеством вершин (узлов) графа, множество Е, представляющее собой множество ребер графа и отображение множества ребер на множество пар элементов из множества V.
Множества V и Е конечны. Из определения следует, что каждому ребру графа x&8712E можно поставить в соответствие пару вершин (u,v) ∈V этого графа, тогда говорят, что ребро х соединяет вершины u и v. Любые две вершины u и v, соединен-ные в графе ребром x называются смежными, и говорят, что ребро х инци¬дентно вершинам u и v. Граф, у которого каждая вершина смеж¬на со всеми остальными вершинами, называется полным графом.
Ребро x, направленное от одной вершины u к другой v, называется ориентированным ребром, или дугой. Граф, содержащий только ориентированные ребра, называется ориентированным графом(орграфом). Ребро, не имеющее определенного направления, называется неориентированным ребром. Граф содержащий неориентированные рёбра называется неориентированным. Граф, содержащий как ребра, так и дуги, называется смешанным графом.
Графическому представлению ориентированного графа с 6 вершинами и 8 дугами, приведенному на рис., соответствует граф G = (V,E), у которого
V = {1,2,3,4,5,6} и Е ={(1,2),(1,3),(3,2),(3,4),(3,5),(4,5),(5,6),(6,4)}.
Рис. Ориентированный граф
Ребро х, соответствующее упорядоченной паре вершин (u,v), начинается в вершине u (исходит из u) и заканчивается в вершине v (входит в v), u — начальная вершина ребра (дуги), v — конечная. Ребро, соединяющее некоторую вершину саму с собой, называется петлей, в нашем рассмотрении петли не допускаются. В случае ориентированных ребер между парой вершин возможны два ребра, которые имеют противоположную направленность и считаются разными ребрами х1= (u,v), X2= (v,u). Если между любой парой вершин графа имеется не более одного ребра в неориентированном графе или не более одного ребра данного направления в ориентированном графе, то такой граф называется простым, в противном случае — мультиграфом. Мы будем рассматривать только простые графы.
Граф, у которого каждому ребру приписан вес, называется взвешенным графом. Вершина, у которой нет ни одной смежной вершины, называется изолированной. Граф, имеющий только изолированные вершины, называется нульграфом. Для ориентированного графа число ребер, исходящих из некоторой начальной вершины v, называется полустепенью исхода. Число ребер, для которых вершина v является конечной, называется полустепенью захода вершины v, а сумма полустепеней исхода и захода называется полной степенью этой вершины. Любая последовательность ребер простого орграфа такая, что конечная вершина любого ребра этой последовательности является начальной вершиной следующего за ним ребра, задает путь в графе. Путь в графе обходит все вершины данной последовательности, если начало пути находится в начальной вершине первого ребра, а конец — в конечной вершине последнего ребра последовательности. Длиной пути считается число ребер в пути. Простой путь (простой относительно ребер) — это путь в графе, все ребра которого различны. Элементарный путь (простой относительно вершин) — путь, в котором все вершины различны. Все элементарные пути — простые, но не наоборот. Цикл (контур) — путь, начинающийся и заканчивающийся в одной и той же вершине. Простой цикл — соответствующий ему путь простой. Элементарный цикл проходит через любую вершину не более одного раза. В элементарном цикле начальная вершина появляется два раза, в простом — может более двух раз. Ациклический орграф — граф, не имеющий ни одного цикла. Связный граф — граф, в котором есть пути между любыми двумя вершинами
| [Оглавление] | [<<страница] | [>>страница] | [В начало ] |