Виды графов

1) Если множество Е составлено из упорядоченных пар, то есть является подмножеством декартового квадрата, то граф называется ориентированным, или орграфом. В орграфе ребра называются дугами.

.

Рис. 26. Орграф

Примеры дуг:

(V , V ), (V , V ), (V,V ), (V,V ), (V,V ).

Заметим, что (V , V )(V , V ).

Если вершина является началом дуги, то будем говорить, что «дуга исходит из вершины». А если вершина является концом дуги, то «дуга заходит в вершину». Количество заходящих дуг называется полустепенью захода, а количество исходящих дуг – полустепенью исхода.

2) Если допустить, что элементами множества Е являются пары с одиночными вершинами, то такое ребро называется петлей, а граф – псевдографом.

3) Если допустить, что V является не множеством, а набором элементов, то есть допустимо наличие одинаковых элементов, то у нас могут появиться кратные ребра, а граф будет мультиграфом.

4) Если множество Е содержит элементы, состоящие более чем из двух вершин, то такой граф называется гиперграфом.

В дальнейшем будем рассматривать графы плоские и не содержащие петель.

Теорема Эйлера. Сумма степеней графа равна удвоенному числу ребер:

Обозначим количество вершин буквой р, а количество ребер буквой q.

d (V ) = 2 q.

Доказательство:

Для двух смежных вершин в сумму их степеней каждое ребро входит дважды.

Что и требовалось доказать.

Дата добавления: 2014-01-06