1. Существует ли неориентированный граф, степени всех вершин которого различны?
2. Постройте неориентированный граф, степени вершин которого равны 2,2,2,3,3,4,5. Существует ли такой граф?
3. Постройте все неизоморфные неориентированные графы, у которых 4, 5, 6 вершин. Тот же вопрос для ориентированных графов с 4 вершинами.
4. Докажите, что среди 6 человек найдется либо трое попарно знакомых, либо трое попарно не знакомых. А среди 5? Какое минимальное число людей надо взять, чтобы среди них нашлись либо двое попарно знакомых, либо двое попарно не знакомых? (Последний вопрос шуточный)
5. Докажите или опровергните изоморфизм данных пар графов.
6. Постройте дополнительные и смежные графы для данных графов.
7. Сколько существует неизоморфных помеченных графов с p вершинами?
8. Докажите, что смежный граф изоморфен исходному тогда и только тогда, когда он является объединением непересекающихся циклов.
9. Докажите, что число дуг графа, смежного к Г, равно .
10. Постройте матрицы смежности и инциденций для данных графов при различной нумерации вершин и дуг. Решите обратную задачу.
11. Докажите теорему 15.
12. Докажитетеорему 16.
13. Найдите компоненты сильной связности графов, заданных матрицами смежности.
14. Проверьте или опровергните, что граф, заданный матрицей смежности, дерево.
15. Запишите код данного дерева.
16. Восстановите дерево по коду.
17. Найдите эксцентриситеты всех вершин данных графов (полного, двудольного, цикла, цепи и др.), найдите их радиус, диаметр и центр.
18. Найдите минимальное остовное дерево данных неориентированных взвешенных графов.
19. Установите, является ли данный вектор эйлеровым (полуэйлеровым) и при положительном заключении постройте эйлеров цикл (эйлерову цепь).
20. Постройте все гамильтоновы циклы данного графа, если они существуют.
21. Решите задачу коммивояжера для данных взвешенных графов.
22. Установите, является ли данный вектор графовым и при положительном заключении постройте соответствующий граф.
23. Найдите в данном графе максимальное паросочетание и минимальное реберное покрытие.
24. Постройте полное паросочетание в данном двудольном графе или докажите, что оно не существует.
25. Постройте критические пути в данном сетевом графике.
26. Найдите в графе при заданных начальной и конечной вершинах максимальный поток и минимальный разрез.