3. Содержание отчета.

1. Постановка задачи.

2. Описание алгоритма, способы его реализации и применение к решению задачи варианта.

3. Описание программы и используемых в ней процедур и функций.

4. Текст программы.

5. Исходные данные контрольного примера (графическое представление графа и соответствующий ему текстовый файл) и результат работы программы для этого примера.

Библиографический список

1. Новиков, Ф.А. Дискретная математика для программистов [Текст] : учебное пособие для студ.вузов (гриф МО .— 2-е изд. — СПб. : ПИТЕР, 2006 .— 364с. : рис.

2. Белоусов, А.И. Дискретная математика [Текст] : учебник для студ. втузов (гриф МО / под ред. В. С. Зарубина, А. П. Крищенко .— 3-е изд., стереотип. — М. : МГТУ, 2004 .— 744 с.

3. Кузнецов, О.П. Дискретная математика для инженера [Текст] : [учебник для вузов] .— 6-е изд., стер. — СПб. : Лань, 2009 .— 400 с.

4. Поздняков, С.Н. Дискретная математика [Текст] : учебник для студ. вузов (гриф МО .— М. : Академия, 2008 .— 448 с.

5. Яблонский, С.В. Введение в дискретную математику [Текст] : Учебное пособие для Вузов/ Под ред. В.А. Садовничего – 3-е изд. стер. – М.: Высш. шк., 2001. – 384 с.

6. Липский, В. Комбинаторика для программистов [Текст] – М.: Мир, 1988. – 213 С.

7. Кристофидес, Р. Теория графов. Алгоритмический подход [Текст] – М.: Мир, 1978. – 432 с.

Приложение

Варианты заданий

1. С помощью поиска в глубину определить число компонент связности графа.

2. С помощью поиска в ширину определить число компонент связности графа.

3. С помощью поиска в глубину проверить существование маршрута между вершинами U и V графа, если маршрут существует, то восстановить его.

4. С помощью поиска в ширину проверить существование маршрута между вершинами U и V графа, если маршрут существует, то восстановить его.

5. Построить остов графа с помощью поиска в глубину.

6. Построить остов графа с помощью поиска в ширину.

7. Проверить, является ли граф деревом с помощью построения его остова поиском в глубину.

8. Проверить, является ли граф деревом с помощью построения его остова поиском в ширину.

9. Для графа дерева найти длину пути от вершины U до V (использовать поиск в глубину и счётчик глубины рекурсии WG).

10. Для графа дерева найти длину пути от вершины U до V (использовать поиск в ширину и счётчик слоёв).

11. С помощью поиска в глубину проверить является ли заданное ребро графа мостом.

12. С помощью поиска в ширину проверить является ли заданное ребро графа мостом.

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

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

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

15