1. Пусть V={2,3,4,6,8,9}. Элементы a и b из V соединим дугой, идущей от a к b, если a делит b нацело. Изобразить полученный граф на плоскости.

2. Пусть A={1,2,3}. V – множество всех подмножеств множества А.

Элементы a и b из V соединим дугой, идущей от а к b, если aÍb. Изобразить полученный граф на плоскости.

3. Занумеровать вершины и дуги и задать орграфы матрицами инцидентности и матрицами смежности:

а)

б)

4. Будут ли изоморфны орграфы, заданные матрицами смежности

а)		и
б)		и

5. Найти компоненты сильной связности следующих орграфов:

а)

б)

6. Будут ли следующие графы эйлеровыми:

а)

б)

7. Будут ли следующие орграфы гамильтоновыми:

а)

б)

8. Орграф называется полуэйлеровым, если существует путь, проходящий через все дуги графа. Будут ли следующие графы полуэйлеровыми:

а)

б)

9. Доказать, что орграф без изолированных вершин полуэйлеров тогда и только тогда, когда он сильно связный и существуют две вершины a и b графа такие, что r⁺(a)=r^–(a)+1=r^–(b)–1 и для любой другой вершины x орграфа выполняется равенство r⁺(x)=r^–(x).

10. Дан орграф G и вершины a и b этого графа. Определить, существует ли (a,b)–путь, проходящий по всем ребрам графа:

а)

б)

11. Орграф называется полугамильтоновым, если сушествует простой путь, проходящий по всем вершинам графа. Будут ли следующие графы полугамильтоновы?

а)

б)

12. Дан орграф G и вершины a и b этого графа. Определить существует ли простой (a,b)–путь, проходящий во всем вершинам графа

а)

б)

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

а)

б)

14. Используя алгоритм Дейкстры, найти расстояния от вершины v₀ до остальных вершин сети:

а)		б)
в)		г)

15. Найти критические работы проектов, заданных сетевыми графиками (считать, что Т=Т_min). В первых двух случаях найти также наиболее раннее и наиболее позднее время начала каждой работы.

а)
б)
в)
в)

19. Преобразовать алгоритм Дейкстры для нахождения самого длинного пути от v₀ до остальных вершин сети. Используя преобразованный алгоритм, найти Т_min для сетей задачи 15.

20. Найти все минимальные разрезы сетей

а)
б)
в)
в)

21. Показать, что потоки (они указаны в скобках) являются максимальными для сетей

а)		б)
в)		г)

22. Найти (хотя бы один) максимальный поток

а)		б)
в)		г)
д)		е)
ж)		з)

23. Показать, каким образом анализ потоков в сетях с несколькими источниками и стоками можно свести к стандартному случаю (один источник и один сток) с помощью двух дополнительных вершин.