Теоретический материал

Общая теория графов

Граф (от греческого * – пишу) – непустое множество, образованное вершинами *. Также это набор * упорядоченных либо неупорядоченных пар последних, имеющих следующий вид: *. Граф обозначают как *, а количество вершин и ребер через *. Неупорядоченная пара первых – это единичный случай вторых – *, а упорядоченная представляет собой дугу.

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

Конкретная пара вершин поддается соединению посредством ребер в количестве от двух, а также через дуги с единым направлением. В таком случае соответствующие компоненты становятся кратными. Если они берут начало и заканчиваются в одной и той же вершине, образуется петля. Граф, не содержащий ее и кратных ребер, называется простым. Если все n вершин изолированы, говорят о пустой разновидности (или нулевой). Предполагается обозначение в виде *.

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

Смежность и инцидентность, степени

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

Ребро (v, w) соединяет вершины v и w. В ориентированных графах дуга соответствующего вида берет начало в v и заканчивается в w либо идет подобным образом.

Степень v в графе G обозначает число ребер, образующих инцидентность относительно начальной вершины. Петли подлежат учету в повторяющемся сценарии, то есть дважды. Вершина G с нулевой степенью считается изолированной. При условии единичного значения говорят о тупиковом варианте (альтернативные термины: висячий, концевой). Для ориентированного графа справедливо следующее: половинная степень исхода или захода v обозначается количеством * дуг, исходящих из v и или заходящих в нее; каждая петля, образующая инцидентность с последней, учитывается как в *, так и в *.

Теорема (рукопожатие). Сумма степеней всех вершин G равна удвоенному количеству ребер, то есть * (число, обозначающее факты пожатых рук, всегда является четным).

Для ориентированного графа: *.

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

Следствие. В каждом графе количество вершин нечетной степени является четным.

Способы задания графов

Способов множество. Возможно использование рисунка, списка вершин и ребер, матрицы смежности. Последний вариант интересен. Предполагается использование квадратной матрицы A (G) = (a_ij), (i, j = 1, …, n). Элемент * при этом равен количеству ребер, которые соединяют * и *.

В случае с ориентированным графом элемент A (*), * равен числу, обозначающему совокупность дуг, исходящих из * и входящих в *.

Есть еще один интересный способ. Он предполагает построение матрицы инцидентности. Для графа G без петель это B (G) = (b_ij). Для ориентированного варианта справедливо аналогичное обозначение с характерной стрелкой. Возможны такие ситуации: b_ij = 1, если соответствующая вершина образует инцидентность с ребром e_j; b_ij = 0 в ином случае.

Интересны и такие правила, справедливые для ориентированного графа: b_ij = 1, если соответствующая вершина v_i – начало дуги e_j; b_ij = - 1, если конец; b_ij = 0, если инцидентность отсутствует.

Примеры:

Граф и матрица смежности

Граф и матрица инцидентности предполагают, что имеет место соответствие строк вершинам, а ребер – столбцам. В случае с ориентированным вариантом все несколько меняется. Срабатывает первое правило, но столбцам начинают соответствовать дуги.

Подграфы, операции на графах

Подграф графа G (V, E) включает все вершины и ребра исходной математической абстракции реальной системы.

Целесообразно рассмотреть некоторые типичные операции. Это:

- удаление ребра. Также возможным является его добавление;

- удаление вершины. Все ребра, образующие с ней инцидентность, исключаются;

- стягивание ребра. В этом случае вершины, образующие с ним инцидентность, объединяются;

- добавление вершины. Операция сопровождается тем, что ребро (u, v) удаляется. После этого добавляется новая вершина w. Вместе с тем образуются ребра (u, w) и (w, v);

- объединение графов * и *. Результат – появление *;

- пересечение графов * и *. В результате образуется *.