Тема: ориентированные графы (орграфы)
Основные вопросы, рассматриваемые на лекции:
1. Определение орграфов
2. Изоморфизмы орграфов
3. Матрицы смежности и инцидентности
Краткое содержание лекционного материала
1. Определение орграфов.
Ориентированный граф (или орграф) G=(V,E) отличается от графа тем, что E является множеством упорядоченных пар различных вершин множества V. На диаграмме две точки орграфа соединятся не линиями, а стрелками.
В орграфах нет петель. Бинарное отношение
графически представляются орграфом, в котором соотношение
изображается петлей, а соотношения
и
двусторонней стрелкой (объединяются две противоположно направленные стрелки).
2. Изоморфизмы орграфов.Орграфы G1=(V1,E1) и G2=(V2,E2) называются изоморфными, если существует биекция j: V1®V2, которая сохраняет отношение смежности между вершинами орграфа:
"u,vÎV1 ((u,v)ÎE1Û(j(u),j(v))ÎE2).
Пример. Приведем все попарно неизоморфные (3,2)-орграфы:

3. Матрицы смежности и инцидентности. Матрицей смежности орграфа
называется матрица
, определяемая следующим образом: для всех 

Матрицей инцидентности
-орграфа
называется прямоугольная
-матрица
, определяемая следующим образом: для всех 
