Лекция № 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. Матрицы смежности и инцидентности. Матрицей смежности орграфа называется матрица , определяемая следующим образом: для всех

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

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