Курсовая работа: Алгоритмическая реализация теоремы менгера

РЕФЕРАТ
Отчёт 19 стр., 1 кн., 6 рис., 6 источн., 1 прил.,
ГРАФ, ОРИЕНТИРОВАННЫЙ ГРАФ, НЕОРИЕНТИРОВАННЫЙ ГРАФ, МАТРИЦА СМЕЖНОСТИ, ОБХОД В ШИРИНУ, ОБХОД В ГЛУБИНУ, РЕБРО, ВЕРШИНА, ПУТЬ
Цель работы: необходимо разработать программное обеспечение, которое реализует теорему Менгера.
Объект исследования: теорема Менгера

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1 Математическое обеспечение
1.1 Граф
1.2 Теорема Менгера
2 Алгоритмическое обеспечение
2.1 Обход в глубину
2.2 Обход в ширину
2.3 Алгоритмическая реализация теоремы Менгера
3 Программная реализация
4 Тестирование
5 Инструкция программисту
6 Инструкция пользователю
ЗАКЛЮЧЕНИЕ
БИБЛЕОГРАФИЧЕСКИЙ СПИСОК
ПРИЛОЖЕНИЕ А

ВВЕДЕНИЕ

Теорема Менгера – основной результат о связности в конечном неориентированном графе. Была сформулирована и доказана в 1927 году австрийско-американским математиком Карлом Менгером младшим.
Теорема Менгера имеет значительную роль в теории графов, так как она устанавливает связь между числом непересекающихся простых цепей, соединяющих две несмежные вершины графа, и его связностью.

1 Математическое обеспечение

1.1 Граф

Граф – совокупность точек, соединяющая линиями точки. Точки называются вершинами (узлами), а линии – ребрами (дугами).
Графы бывают ориентированные и неориентированные.
В ориентированном графе все ребра имеют направление, в котором можно передвигаться между смежными вершинами, соединенными ребром.
В неориентированном графе по ребрам можно передвигаться в независимости от направления.
Граф можно задать разными способами. Для реализации будем использовать матрицу смежности.