Графы. Способы задания графов. Степени вершин

Граф
Это совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности

Инцидентное ребро
Каждое ребро e из E ровно двум вершинам v', v'', которые оно соединяет

Петля
Ребро называется петлей, если концевые вершины совпадают

Ориентированное ребро
Ребро (v',v'') ориентированное, если имеет начало (v') и конец (v'')

Кратные ребра
Ребра, инцидентные одной паре вершин, называются параллельными или кратными

Неорграф
Граф, не содержащий ориентированные ребра, называется неографом.

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

Смежные вершины
Если ребро инцидентно,то вершина v' и ребро e называются инцидентными друг другу, а вершины v' и v'' называются смежными

Конечный граф
Граф конечный, если число вершин и ребер конечно

Пустой граф
Граф пустой, если множество ребер пусто

Полный граф
Граф полный, если нет петель и кратных ребер, каждая пара вершин соединена ребром

Локальная степень вершины
Локальная степень вершины - число ребер ей инцидентных

Лемма о рукопожатиях
В неографе сумма степеней всех вершин равна удвоенному числу ребер
Петля дает вклад, равный 2 в степень вершины

Степени вершин в орграфе
В орграфе сумма входящих ребер всех вершин равна сумме исходящих ребер всех вершин и равна числу ребер графа

Равные графы
Графы равны, если множества вершин и инцидентных им ребер совпадают

Изоморфные графы
Графы, отличающиеся только нумерацией вершин и ребер

Способы задания графов
явное задание графа как алгебраической системы
геометрический
матрица смежности
матрица инцидентности

Матрица смежности
Матрица смежности - квадратная симметричная матрица
По горизонтали и вертикали - все вершины
аij= число ребер, соединяющее вершины i,j

Матрица инцидентности
Матрица инцидентности-по вертикали указываются вершины, по горизонтали ребра
aij=1 если вершина i инцидентна ребру j, в противном случае aij=0
Если ребро - петля то aij=2

Маршрут
Маршрут - последовательность ребер, в которых каждые два соседних ребра имеют общую вершину

Цикл
Маршрут, в котором начало и конец совпадают,циклический

Цепь
Маршрут в неографе, в котором все ребра разные - цепь

Путь
Маршрут в орграфе, в котором все дуги разные - путь

Связные вершины
Вершины связанные, если существует маршрут из одной вершины в другую

Пустой граф
Граф пустой, если множество ребер пусто

Связанный граф
Связанный граф - если все его вершины связаны

Плоский граф
Плоский граф - граф с вершинами, расположенными на плоскости и непересекающимися ребрами

Изолированные вершины
Вершины графа, которые не принадлежат ни одному ребру, называются изолированными

Дерево
Связный граф без циклов, называется дерево