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

Настоящая курсовая работа моделирует логическую задачу, состоящую из следующих частей:

1) Изучение конкретного раздела дискретной математики.

2) Решение 5-ти задач по изученной теме с методическим описанием.

3) Разработка и реализация в виде программы алгоритма по изученной теме. Разработка программного интерфейса.

2. Введение

 

2.1 Теоретическая часть

дискретный математика программа интерфейс

Пусть дан граф G=(X, Г), дугам которого приписаны веса (стоимости), задаваемые матрицей C=[cij]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины sX до заданной конечной вершины tX, при условии, что такой путь существует, т.е. при условии tR(s). Здесь R(s) – множество, достижимое из вершины s. Элементы cij матрицы весов C могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в G не было циклов с отрицательным суммарным весом. Если такой цикл Ф все же существует и xi – некоторая его вершина, то, двигаясь от s к xi, обходя затем Ф достаточно большое число раз и попадая наконец в t, мы получим путь со сколь угодно малым () весом. Таким образом, в этом случае кратчайшего пути не существует.

Если, с другой стороны, такие циклы существуют, но исключаются из рассмотрения, то нахождение кратчайшего пути (простой цепи) между s и t эквивалентно нахождению в этом графе кратчайшего гамильтонова пути с концевыми вершинами s и t. Это можно усмотреть из следующего факта. Если из каждого элемента cij матрицы весов C вычесть достаточно большое число L, то получится новая матрица весов C'=[cij'], все элементы cij' которой отрицательны. Тогда кратчайший путь от s к t – с исключением отрицательных циклов – необходимо будет гамильтоновым, т.е. проходящим через все другие вершины. Так как вес любого гамильтонова пути с матрицей весов C' равен весу этого пути с матрицей весов C, но уменьшенному на постоянную величину (n-1)×L, то кратчайший путь (простая цепь) от s к t с матрицей C' будет кратчайшим гамильтоновым путем от s к t при первоначальной матрице C. Задача о нахождении кратчайшего гамильтонова пути намного сложнее, чем задача о кратчайшем пути. Поэтому мы будем предполагать, что все циклы в G имеют неотрицательный суммарный вес. Отсюда также вытекает, что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.

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

1) Для заданной начальной вершины s найти кратчайшие пути между t и всеми другими вершинами xiX.

2) Найти кратчайшие пути между всеми парами вершин.

Частные случаи, когда все cij неотрицательны, встречаются на практике довольно часто (например, когда cij являются расстояниями), так что рассмотрение этих специальных алгоритмов оправдано. Мы будем предполагать, что матрица не удовлетворяет, вообще говоря, условию треугольника, т.е. не обязательно  для всех . В противном случае кратчайший путь между xj и xj состоит из одной единственной (xj xj) дуги, если такая дуга существует, и задача становится тривиальной. Если в графе G дуга (xj xj) отсутствует, то ее вес полагается равным .

На практике часто требуется найти не только кратчайший путь, но также второй, третий и т.д. кратчайшие пути в графе. ............