Задание 1. Ориентированный граф

6. Охарактеризовать граф.

7. Назвать специальные вершины и рёбра.

8. Рассчитать полустепени вершин.

9. Выписать матрицы смежности, инцидентности, достижимости, связности.

10. Выписать цикл, цепь, простой цикл, простую цепь.

Решение:

Назовем ребра у графа:

Характеристика графа:

V={V0, V1, V2, V3, V4, V5, V6}; X= {X0, X1, X2, X3, X4, X5, X6, X7, X8}

X0=< V0, V3>, X1=< V0, V2>, X2=< V1, V2>, X3=< V4, V1>, X4=< V2, V5>, X5=< V0, V4>, X6=< V3, V6>, X7=< V6, V4>, X8=< V6V5>

1. V3- висячая вершина

2. Полустепени вершин:

-(V0)=2; -(V1)=2; -(V2)=1; -(V3)=1; -(V4)=1; -(V5)=0; -(V6)=2

+(V0)=1; +(V1)=1; +(V2)=2; +(V3)=0; +(V4)=2; +(V5)=2; +(V6)=1
4.

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

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

Матрица достижимости

Матрица связности

Простой цикл: V1 X0 V0 X5 V4 X3 V1; Цикл: нет;

Простая цепь: V1 X0 V0 X5 V4; Цепь: V1 X0 V0 X5 V4 X3 V1 X2 V2