Степени вершины графа. Лемма о рукопожатиях. Матрица смежности и инцедентности.

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

Лемма 1 (“о рукопожатиях”). Сумма степеней всех вершин графа G есть число чётное, ровно в два раза большее числа рёбер графа G.

При использовании компьютера, для построения графа удобно переходить от наглядного представления графа к его двоичному представлению, для этого используется матрица смежности-это квадратная матрица, размера nxn элемент а_ijкоторой

А=( а_ij)= а_ij=

Еще одна матрица, называемая матрицей инцидентности, также является характеристикой графа и имеет размер mxn, где m-перенумерованные ребра графа, n-вершина

В: если граф неориентированный то его элемент равен 1, если

В=(b_ij) =>а_ij=

Если граф ориентированный

В=(b_ij) =>b_ij=