Пример готовой курсовой работы по предмету: Программирование
Содержание
1. Введение
2. Теоретическая часть
3. Описание алгоритма
4. Текст программы
5. Результат работы программы
6. Заключение
7.
Список источников информации
Выдержка из текста
Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними).
Считается, что смежные вершины соединены между собой ребрами (или дугами).
Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, также называются смежными (или соседними).
Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой).
Помимо этого, в теории графов рассматриваются также мультиграфы – это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами.
Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление).
Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней.
Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).
Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.
Последовательности вершин: 1– 2– 3– 4– 2– 5 не простой путь, а маршрут; последовательности 1– 2– 3– 4– 7– 5 и 1– 2– 5 – простые пути; 1– 2– 3– 4– 2– 5– 6– 1 –это цикл (но не контур); 1– 2– 5– 6– 1 – это контур.
Алгоритм Беллмана — Форда — алгоритм поиска кратчайшего пути во взвешенном графе. Алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана — Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.
Список использованной литературы
1. Тишин В.В.-дискретная математика в примерах и задачах
2. Е.Л Рабкин, Ю.Б. Фарфоровская – дискретная математика
3. http://sdb.su/diskretka/page,8,337-glava-elementy-teorii-grafov-rabochij-uchebnik-po-diskretnoj-matematike.html
4. http://habrahabr.ru/blogs/algorithm/105825/
5. http://rain.ifmo.ru/cat/view.php/vis/graph-paths/dag-critical-paths/algorithm
