Основные определения теории графов

Графом называется пара , где V – некоторое множество, которое называют множеством вершин графа, а E – отношение на V () - множество ребер графа. То есть все ребра из множества E соединяют некоторые пары точек из V.

Если отношение E симметричное (т.е. ), то граф называют неориентированным, в противном случае граф называют ориентированным. Фактически для каждого из ребер ориентированного графа указаны начало и конец, то есть пара (u, v) упорядочена, а в неориентированном графе (u, v) = (v, u).

Если в графе существует ребро (u, v), то говорят, что вершина v смежна с вершиной u (в ориентированном графе отношение смежности несимметрично).

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

Граф называется связанным, если для любой пары его вершин существует путь из одной вершины в другую.

Если каждому ребру графа приписано какое-то число (вес), то граф называют взвешенным.

При программировании вершины графа обычно сопоставляют числам от 1 до N, где  - количество вершин графа, и рассматривают . Ребра нумерую числами от 1 до M, где . Для хранения графа в программе можно применить различные методы. Самым простым является хранение матрицы смежности, т.е. двумерного массива, скажем A, где для невзвешенного графа (или 1), если  и (или 0) в противном случае. Для взвешенного графа A [ i ][ j ] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j. Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти памяти был достаточен для хранения N ² значений, даже если ребер в графе существенно меньше, чем N ². Это не позволяет построить алгоритм со временем порядка O (N) для графов, имеющих O (N) ребер.

Этого недостатка лишены такие способы хранения графа, как одномерный массив длины N списков или множеств вершин. В таком массиве каждый элемент соответствует одной из вершин и содержит список или множество вершин, смежных ей.

Для реализации некоторых алгоритмов более удобным является описание графа путем перечисления его ребер. В этом случае хранить его можно в одномерном массиве длиной M, каждый элемент которого содержит запись о номерах начальной и конечной вершин ребра, а также его весе в случае взвешенного графа.

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

Графы широко используются в различных областях науки (в том числе в истории!!!) и техники для моделирования отношений между объектами. Объекты соответствуют вершинам графа, а ребра — отношениям между объектами). Подробнее об этой структуре данных можно прочитать в [5 - 7].