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(vi)=d(v0,vi), i=1,…,5.
0 |
3 |
4 |
1 |
¥ |
¥ |
1 |
3 |
3 |
|
4 |
5 |
2 |
|
3 |
|
4 |
5 |
3 |
|
|
|
4 |
4 |
4 |
|
|
|
|
4 |
Ответ: d(v0,v1)=3, d(v0,v2)=3, d(v0,v3)=1, d(v0,v4)=4, d(v0,v5)=4.
15. В случае а критические работы – в случае б – v0, v3, v5, v7, v9; в случае б - v0,v1, v3, v4, v5, v7, v8; в случае в - v0,v2, v4, v5, v7; в случае г - v0,v1, v3, v4, v5, v7, v10.
20. Приведем решение в случае а.
Занумеруем вершины графа (кроме источника и стока). Ребра будем задавать парой
вершин. Минимальные разрезы находим перебором. Это будут следующие разрезы: S1={(a,v2), (a,v3), (v1,v4)}, S2={(v2,v5), (v3,v5), (v6,b)}, S3={(v4,b), (v5,b), (v6,b). Пропускная способность этих разрезов равна 5.
21. Указание. Найти разрез,
пропускная способность которого равна величине потока.
22. Приведем ответ для а, в и д (величина максимального потока указана в
скобках)
а) |
|
в) |
|
г) |
|
|