1. Граф имеет следующий вид

4. В обоих случаях графы изоморфны

5. В случае а граф имеет две компоненты сильной связности, в случае б – три.

6. Оба графа будут эйлеровыми.

7. Оба графа гамильтоновыми не будут.

8. В случае а граф будет полуэлеровым, в случае б не будет.

11. В обоих случаях граф будет полугамильтоновым.

13. Решение. В случае а достаточно добавить одну дугу, идущую из левой нижней вершины в правую. В случае б искомый граф имеет следующий вид

Нумерация вершин определяет линейный порядок. Процедурой А (см. доказательство теоремы 6.4) добавлены дуги (1,3), (1,4), (1,6), (2,4) и (2,6), процедурой В – дуги (2,5) и (3,4).

14. Приведем решение в случае а. Вначале занумеруем вершины графа

Работу алгоритма Дейкстры проиллюстрируем таблицей, аналогичной таблице 6.1. Напомним, что d(v_i)=d(v₀,v_i), i=1,…,5.

Ответ: d(v₀,v₁)=3, d(v₀,v₂)=3, d(v₀,v₃)=1, d(v₀,v₄)=4, d(v₀,v₅)=4.

15. В случае а критические работы – в случае б – v₀, v₃, v₅, v₇, v₉; в случае б - v₀,v₁, v₃, v₄, v₅, v₇, v₈; в случае в - v₀,v₂, v₄, v₅, v₇; в случае г - v₀,v₁, v₃, v₄, v₅, v₇, v₁₀.

20. Приведем решение в случае а. Занумеруем вершины графа (кроме источника и стока). Ребра будем задавать парой вершин. Минимальные разрезы находим перебором. Это будут следующие разрезы: S₁={(a,v₂), (a,v₃), (v₁,v₄)}, S₂={(v₂,v₅), (v₃,v₅), (v₆,b)}, S₃={(v₄,b), (v₅,b), (v₆,b). Пропускная способность этих разрезов равна 5.

21. Указание. Найти разрез, пропускная способность которого равна величине потока.

22. Приведем ответ для а, в и д (величина максимального потока указана в скобках)

а)

в)

г)