Лекция № 12

Тема: ориентированные графы (орграфы)

Основные вопросы, рассматриваемые на лекции:

1. Определение орграфов

2. Изоморфизмы орграфов

3. Матрицы смежности и инцидентности

Краткое содержание лекционного материала

1. Определение орграфов.

Ориентированный граф (или орграф) G=(V,E) отличается от графа тем, что E является множеством упорядоченных пар различных вершин множества V. На диаграмме две точки орграфа соединятся не линиями, а стрелками.

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

2. Изоморфизмы орграфов.Орграфы G₁=(V₁,E₁) и G₂=(V₂,E₂) называются изоморфными, если существует биекция j: V₁®V₂, которая сохраняет отношение смежности между вершинами орграфа:

"u,vÎV₁ ((u,v)ÎE₁Û(j(u),j(v))ÎE₂).

Пример. Приведем все попарно неизоморфные (3,2)-орграфы:

 

 

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

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