Библиографический список. 1. Кузнецов О.П., Адельсон-Вельский Г.М

1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. - М.: Энергоатомиздат, 1988. - 480 с.

2. Коршунов Ю.М. Математические основы кибернетики: Учеб. Пособие для вузов. - 3-е изд. перераб. и доп. - М.: Энергоатомиздат, 1987. - 496 с.: ил.

3. Новиков Ф.А. Дискретная математика для программистов. – Спб: Питер, 2000. – 304 с.: ил.

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

5. Липский В. Комбинаторика для программистов. М.: Мир, 1988. - 213 С.

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

Приложение

Варианты задания №1

1. По таблице смежности построить списки инцидентности неориентированного графа и подсчитать степени его вершин.

2. По таблице рёбер построить списки инцидентности ориентированного графа и подсчитать полустепени его вершин.

3. По таблице смежности построить списки инцидентности ориентированного графа и подсчитать полустепени его вершин.

4. По таблице рёбер построить списки инцидентности неориентированного графа и подсчитать степени его вершин.

5. По таблице смежности построить списки инцидентности неориентированного графа, записи в каждом списке упорядочить по возрастанию номеров вершин.

6. По таблице рёбер построить списки инцидентности неориентированного графа, записи в каждом списке упорядочить по убыванию номеров вершин.

7. По таблице смежности построить списки инцидентности ориентированного графа, записи в каждом списке упорядочить по убыванию номеров вершин.

8. По таблице рёбер построить списки инцидентности ориентированного графа, записи в каждом списке упорядочить по возрастанию номеров вершин.

9. По таблице смежности построить списки инцидентности неориентированного графа, удалить из графа все рёбра, начинающиеся и заканчивающиеся в вершинах n₁, n₂, n₃ или n₄.

10. По таблице рёбер построить списки инцидентности ориентированного графа, добавить рёбра с началом в вершинах, кратных 2, и концом в вершинах, кратных 5.

11. По таблице рёбер построить списки инцидентности ориентированного графа, удалить из графа вершины с номерами n₁ и n₂.

12. По таблице смежности построить списки инцидентности ориентированного графа, добавить рёбра с началом в вершинах n₁, n₂ и n₃ и концом в вершинах n₃, n₄ и n₅.

13. По таблице рёбер построить списки инцидентности неориентированного графа, удалить из графа все рёбра, обе вершины которых кратны 3.

Варианты задания №2

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

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

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

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

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

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

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

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

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

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

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

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

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

Учебное издание

Дата добавления: 2015-06-27