1. Списки ребер

Представление произвольного графа с помощью списка ребер состоит в заполнении массива, содержащего все пары вершин, представляющие ребра графа. Недостатком такого способа представления является возможность утраты информации об изолированных вершинах.

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

Пусть G = (V, U)  это граф с вершинами V = {v₁, ... v_n}. Тогда матрицей смежности этого графа называется квадратная таблица размером nn, строки и столбцы которой поставлены во взаимно однозначное соответствие вершинам множества V.

Значение элемента этой матрицы, расположенного на пересечении i -й строки и j-го столбца определяется по правилу:

=

ПУТИ И СВЯЗНОСТЬ В ГРАФАХ

Пусть G = (V, U)  некоторый граф.

Отношение смежности (или соседства) вершин этого графа задает пары соседних вершин в G. Рассмотрим транзитивное обобщение понятия связи вершин посредством одного ребра для отношения смежности вершин.

ОПРЕДЕЛЕНИЕ

Последовательность W = a₁, ... , a_n  вершин графа G образует путь в G, если i = 1, ... , n  1 ((a_i, a_i+1)  U).

Прохождение пути в графе  это последовательное перемещение по вершинам графа, по ребрам, соединяющим такие вершины. О таких ребрах говорят, что они принадлежат пути и что путь проходит через эти ребра. Если W это путь в графе G, то запись E(W) используется для обозначения множества ребер, принадлежащих пути.

Частный случай пути  это пустой путь W = a, который состоит из единственной вершины a. Такой путь начинается и заканчивается в этой вершине.

Вершины a₁ и a_n называются началом и концом пути. При этом говорят, что W ведет из a₁ в a_n. Длиной пути W называется число ребер, проходимых при движении по W из a₁ в a_n. То есть, если W содержит m вершин, то длина W равна m  1.

Путь W называется элементарным, если все вершины в нем разные. Путь W называется простым, если все ребра из E(W) являются разными.

Путь W называется циклом, если его начало и конец совпадают.

Цикл называется элементарным (простым) циклом, если в нем все вершины за исключением первой и последней (все ребра) разные.

Если некоторый путь W в графе G не является элементарным, то он может быть преобразован в элементарный путь с теми же началом и концом.

Для этого необходимо последовательно выбирать пары одинаковых вершин, одна из которых  это внутренняя вершина пути.

Для каждой такой пары вершин a_i и a_j из W удаляется часть, состоящая из вершин a_i+1, ... , a_j, т.е. путь W=a₁, ... ,a_i, ...,a_j, ... ,a_n преобразуется в путь W₁ = a₁, ... , a_i, a_j+1 , ... , a_n.

Содержательно приведенное преобразование пути означает замену в W части, образующей цикл, начинающийся и заканчивающийся в вершине a из W, на вершину a. Для получения элементарного пути приведенное преобразование повторяется до тех пор, пока не будет получен требуемый элементарный путь.

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

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

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