Матрица инцидентности.

Орграфы.

Цель работы: изучение основных понятий орграфов. Получение практических навыков нахождения сильных компонент, построения конденсации, базы и антибазы.

Теоретическая справка

Определение ориентированного графа (орграфа)

Ориентированный граф G =(V, A) – пара множеств V и A, таких, что V – некоторое конечное непустое множество, а A – некоторое подмножество декартового квадрата V (A Í V² =V*V).

Вершины графа G – элементы множества B.

Дуги графа G – элементы множества A.

Дуга – упорядоченная пара вершин a=(u, v).

Начало дуги – вершина u, конец дуги – вершина v.

Дуга исходит из своего начала и заходит в свой конец.

Орграф G – орграф p-го порядка, если мощность множества |V|=p.

Способы описания орграфов

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

A=||a _ij||, i, j = 1.. p, | V |= p, | A |= q.

1, если существует дуга (i, j);

a _ij =

0, иначе.

Матрица инцидентности.

B=||b _ij ||, i=1.. p, j=1.. q, |A|=q, |V|=p.

1, i – начало дуги j;

b _ij = -1, i – конец дуги j;

0, иначе.

Например:

Орграф G(V, A)

Матрица инцидентности:

Матрица смежности:

Основание - неориентированный граф, получившийся в результате снятия ориентации дуг орграфа.

Обратный граф G ^-1=(V, A ^-1) – орграф, у которого множество вершин совпадает с исходным графом, и дуга (u, v)Î A ^-1 Û (v, u)Î A.

Турнир – ориентированый граф, основание которого есть полный граф.