3.1 Основные понятия и определения

Граф (от греческого   - пишу) - непустое множество вершин   и набор   неупорядоченных и упорядоченных пар вершин вида (v,w). Обычно граф обозначают как G(V,E); количество вершин и ребер обозначается, соответственно, n(G) и m(G).

Неупорядоченная пара вершин называется ребром {v,w}, упорядоченная пара - дугой (v,w).

Граф, содержащий только ребра, называется неориентированным (обозначается G). Граф, содержащий только дуги - ориентированным (или орграфом) (обозначается  ).

Пара вершин может быть соединена двумя или более рёбрами (или, соответственно, дугами одного направления), такие рёбра (или дуги) называются кратными. Дуга (или ребро) может начинаться и заканчиваться в одной и той же вершине, в этом случае соответствующая дуга (или ребро) называетсяпетлёй.

Граф без кратных рёбер и петель называется простым графом.

Граф, все n вершин которого являются изолированными, называется нулевым (пустым) и обозначается  .

Простой граф, любые две вершины которого являются смежными, называется полным. Полный граф с n вершинами обозначается  .

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

Вершины, соединённые ребром или дугой, называются смежными.

Рёбра, имеющие общую вершину, тоже называются смежными.

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

Говорят, что ребро {v,w} соединяет вершины v и w. Для орграфов: дуга (v,w) начинается в вершине v(исходит из вершины v) и заканчивается в вершине w (заходит в вершину w), или идет из вершины vв вершину w.

Степенью вершины v графа G называется число deg v рёбер графа G, инцидентных вершине v, при этом петли учитываются дважды. Вершина графа, имеющая степень 0, называется изолированной, а степень 1 - тупиковой (висячей, концевой).

Для орграфа: полустепенью исхода (захода) вершины v орграфа   называется число   ( ) дуг орграфа, исходящих из вершины v (заходящих в вершину v), при этом каждая петля, инцидентная вершине v , учитывается как в  , так и в  .

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

Для орграфа:  .

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

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

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

• Рисунок.

• Список вершин и рёбер.

• Матрица смежности. Матрицей смежности называется квадратная матрица A(G)=( ), (i,j=1,…,n), у которой элемент   равен числу рёбер, соединяющих   и 

Для орграфа элемент матрицы A( ),   равен числу дуг, идущих из   в  .

• Матрица инцидентности. Матрицей инцидентности графа G (без петель) называется матрицаB(G)=( ) (для орграфа B( )=( )) размерности   , у которой: =1, если вершина   инцидентна ребру  , =0, в противном случае.

Для орграфа:  =1, если вершина   есть начало дуги  ; = - 1, если вершина   есть конец дуги  ; =0, если   и   не инцидентны.

Примеры:

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

Граф и его матрица инцидентности, здесь вершинам соответствуют строки, а ребрам - столбцы.

Матрица инцидентности для ориентированного графа, здесь вершинам соответствуют строки, а дугам - столбцы.