Теоретическая часть. Рассмотрим конечный граф G=(V, E), где |V|=n, |E|=m

Рассмотрим конечный граф G =(V, E), где | V |= n, | E |= m.

Способами аналитического представления графа являются:

1. Матрица инциденций.

Ориентированный граф задается прямоугольной матрицей B (n ´ m), элементы которой определяются по правилу:

Кроме нерационального использования памяти (n× m единиц) недостатком этого способа представления является неудобный доступ к информации. Например, для ответа на вопросы:

а) существует ли ребро (дуга) (v_i, v_j);

б) к каким вершинам ведут ребра (дуги) из вершины v_i

требуется, в худшем случае, перебор n× m элементов, т.е. порядка n× m шагов алгоритма.

2. Матрица смежности.

Элементы квадратной матрицы A (n ´ n) определяются следующим образом:

Проверка существования ребра (дуги) (v_i, v_j) осуществляется за один шаг, в отличие от матрицы инциденций, однако, проверка свойств графа на основе такого представления требует, в худшем случае, порядка n ² шагов алгоритма.

3. Таблицы ребер.

Она представляет собой матрицу размером m ´ 2, каждая строка которой содержит вершины инцидентные i -му ребру (i -ой дуге). Для работы со взвешенными графами нужно добавить к матрице столбцы, соответствующие весам ребер (дуг).

Этому способу представления графа присущ тот же недостаток, что и матрице инциденций, - неудобство доступа к информации, хотя число шагов при поиске ребра здесь значительно меньше (порядка m). Поиск можно ускорить, введя лексикографический порядок в упорядочении пар и применяя двоичный поиск.

4. Списки инцидентности.

Для каждой вершины v_i Î V создается список записей, характеризующих ребра (дуги), инцидентные этой вершине.

Таким образом, это представление использует объем памяти порядка (n + m), поиск вершины смежной с данной требует порядка (n + m) шагов, проверка свойств графа осуществляется за число шагов порядка. Поэтому остановимся подробнее на этом способе задания графа.