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

1. Явное перечисление множеств вершин V и ребер E.

2. Графический способ описания: прообраз вершины – точка, прообраз ребра – отрезок прямой или кривой.

3. Матричные способы описания.

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

,

.

Матрица инцидентности

,

.

Например:

Задан граф G=(V, E), где

V={a, b, c, d},

E={ab, bc, ac, ad, dc}.

Матрица смежности Матрица инцидентности

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

Степень вершины deg(v) графа G – число инцидентных ей ребер.

Максимальная степень всех вершин графа G – D(G):

.

Минимальная степень всех вершин графа G – d(G):

.

Лемма о рукопожатиях

Изолированная вершина графа G – вершина, степень которой равна 0.

Висячая вершинаграфа G – вершина, степень которой равна 1.

Доминирующая вершина графа G – вершина, степень которой равна p-1, где p – количество вершин графа G.