Обозначения. Множество вершин будем обозначать большой латинской буквой V

Множество вершин будем обозначать большой латинской буквой V. Элементы этого множества (вершины) – маленькими латинскими буквами v с индексом. Множество ребер (дуг) обозначим большой латинской буквой Е, а сами ребра (дуги) - маленькими латинскими буквами е с индексом. Граф G с множеством вершин V и множеством ребер Е будем обозначать G(V,E). Количество вершин (мощность множества V) будем обозначать |V|, количество ребер (дуг) – |E|.

Для графа, изображенного на рисунке 1.5

V={v₁, v₂, v3, v₄, v₅, }, |V|=5,

E={ e₁, e₂, e₃, e₄, e₅, e₆, e₇, e₈ }, |E|=8.

Определение. Вершины, соединенные ребром (дугой), называются смежными. Ребра (дуги), имеющие общую вершину, также называются смежными.

Определение. Ребро и любая из его двух вершин называются инцидентными.

Определение. Степень вершины в неориентированном графе - число ребер, концом которых является эта вершина. Будем обозначать степень i-той вершины через deg v_i.

Например, для графа, изображенного на рисунке 5:

- вершины v₁ и v₂ смежны, а вершины v₄ и v₂ не смежны.

- ребро е₁ инцидентно вершинам v₁ и v₂

- степень первой вершины равна 4 (deg v₁ =4).

Определение. Пусть v вершина орграфа D назовем полустепенью исхода v число дуг орграфа D, имеющих вид (v, w); аналогично полустепенью захода v назовем число дуг вида (w, v).

Будем обозначать полустепень захода i-той вершины через deg⁺ v_i, полустепень исхода i-той вершины через deg^- v_i.

Например, для графа, изображенного на рисунке 6 deg⁺ v₁ =3, deg^- v₁ =1.

Определение. Если два ребра инцидентны одной и той же паре вершин, они называются кратными.

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

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

Определение. Ребро (дуга) называется петлей, если начало и конец его (её)совпадают.

Определение. Граф содержащий петли называется псевдографом

Рис. 9

На рисунке 9 изображен мульти-псевдограф.

Определение. Неориентированный граф без петель и кратных ребер называется простым графом.

Теорема. (Лемма о рукопожатиях). В простом графе сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа.

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

Теорема. Число нечетных вершин простого графа четно.

Доказательство. Предположим противное: существует граф G, имеющий нечетное количество вершин нечетной степени. Подсчитаем сумму степеней всех вершин – она будет нечетной, что противоречит лемме о рукопожатиях.

Орлемма о рукопожатии. Сумма полустепеней захода всех вершин орграфа равна сумме полустепеней исхода всех вершин.

Доказательство. Каждая дуга “участвует” в каждой сумме ровно один раз.

Примеры графов

Определение. Регулярный граф – граф, у которого все вершины имеют одну и ту же степень.

На рисунке 10 изображен регулярный граф со степенью регулярности 2. На рисунке 11 – регулярный граф со степенью регулярности 3. Граф, изображенный на рисунке 11 называют графом Петерсона, он интересен тем, что любые две его вершины соединены маршрутом, проходящим не более чем по двум ребрам.

Определение. Граф называется полным, если каждые две его различные вершины соединены одним и только одним ребром.

Полный граф с n вершинами обозначается К_n. На рисунке 12 изображены полные графы на 2, 3 и 5 вершинах.

Определение. Двудольный граф-это граф G(V,E), такой что множество V разбито на два непересекающихся множества V₁ и V₂(, Æ), причем всякое ребро из E соединяет вершину из V₁ с вершиной из V_2. Множества V₁ и V₂ называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющий множества V₁ и V₂, то он называется полным двудольным графом.

Полный двудольный граф с m вершинами в одной доле и n вершинами в другой обозначается К_mn. На рисунке 13 изображен полный двудольный граф К₃₃

Способы описания графа.

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

Дата добавления: 2014-12-29