1.2. Машинное представление графа

Приведем сравнительную характеристику существующих способов представления графа в памяти ЭВМ, их достоинства и недостатки.

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

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

где a – любое натуральное число, отличное от 1. У неориентированного графа оба элемента матрицы, соответствующие вершинам, инцидентным ребру e_j, равны 1.

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

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

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

требуется, в худшем случае, перебор nm элементов, т.е. порядка nm шагов алгоритма. От этого недостатка свободен следующий способ представления графа.

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

Такая форма эквивалентна матричному представлению бинарного отношения (см. тема “Отношения”). Проверка существования ребра (дуги) (v_i, v_j) осуществляется за один шаг, в отличие от матрицы инциденций, однако, проверка свойств графа на основе такого представления требует, в худшем случае, порядка n² шагов алгоритма. При этом способе объем неиспользованной памяти по-прежнему велик.

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

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

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

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

Тема 2. Степени, маршруты, связность

2.1. Степени вершин графов

Def. Степенью вершины v графа называется число инцидентных ей ребер. Обозначается deg v. Вершина степени 0 называется изолированной, степени 1 – концевой или висячей.

Для орграфа вводятся также понятия

- полустепень исхода – число дуг выходящих из v; обозначается deg^– v;

- полустепень захода – число дуг входящих в v; обозначается deg⁺ v;

Свойство. .

Теорема 2.1. (Теорема Эйлера, лемма о рукопожатиях). ;

Доказательство очевидно, если учесть, что каждое ребро в данной сумме учитывается 2 раза.

Теорема 2.2. (о нечетных степенях). В конечном графе число вершин с нечетными степенями четно.

Доказательство. Обозначим .По теореме 1.2. S четно. Далее, положим S_Ч – сумма степеней вершин с четной степенью, S_Н – сумма степеней вершин с четной степенью. Очевидно, S = S_Ч + S_Н. В S_Ч каждое слагаемое четно, значит, само S_Ч тоже четно. Отсюда, в силу четности S, получаем, что S_Н четно. Но каждое слагаемое в нем – нечетно. Следовательно, таких слагаемых должно быть четное число. Ч Т Д.