Виды графов
1) Если множество Е составлено из упорядоченных пар, то есть является подмножеством декартового квадрата, то граф называется ориентированным, или орграфом. В орграфе ребра называются дугами.
.
Рис. 26 . Орграф
Примеры дуг:
(V 
, V 
), (V , V 
), (V
,V), (V,V), (V,V).
Заметим, что (V
,V
)
(V,V).
Если вершина является началом дуги, то будем говорить, что «дуга исходит из вершины». А если вершина является концом дуги, то «дуга заходит в вершину». Количество заходящих дуг называется полустепенью захода, а количество исходящих дуг – полустепенью исхода.
2) Если допустить, что элементами множества Е являются пары с одиночными вершинами, то такое ребро называется петлей, а граф – псевдографом.
3) Если допустить, что V является не множеством, а набором элементов, то есть допустимо наличие одинаковых элементов, то у нас могут появиться кратные ребра, а граф будет мультиграфом.
4) Если множество Е содержит элементы, состоящие более чем из двух вершин, то такой граф называется гиперграфом.
В дальнейшем будем рассматривать графы плоские и не содержащие петель.
Теорема Эйлера. Сумма степеней графа равна удвоенному числу ребер:
Обозначим количество вершин буквойр, а количество ребер буквойq.
d (V) = 2q.
Доказательство:
Для двух смежных вершин в сумму их степеней каждое ребро входит дважды.
Что и требовалось доказать.