Курсовая работа: Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему

1

1 1

A3

1

1

1 А4 1 1 1

2. Множество антиядерных строк пустое .

3. Вычеркиваем столбцы В1, В3, В5, В6 как поглощающие

4. Вычеркиваем строку А2 как поглощенную.

Теперь таблица покрытий будет иметь вид

(см. Таб .4)

Таб. 4.

В2	В4
А1
А3	1
А4	1

1. Множество ядерных строк Р={A3, A4}.

2. Множество антиядерных строк А={А1}.

3. Множество поглощающих столбцов пустое.

4. Множество поглощаемых строк пустое.

Теперь таблица покрытий примет вид (см. Таб 5)

В2	В4
А3	1
А4	1

Таким образом кратчайшее покрытие {A3, A4} Таб. 5.

4 АЛГОРИТМ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ В ГРАФЕ

4.1 Математическое описание задачи и методов её решения

Графом (G, X) называется совокупность двух конечных множеств: множества точек, которые называются вершинами (X = {Х₁ ,...,Х_n }), и множества связей в парах вершин, которые называются дугами, или ребрами ( (Х_i , Х_j ) ÎG ) в зависимости от наличия или отсутствия направленности связи.

Ребром называются две встречные дуги (Х_i , Х_j ) и (Х_j , Х_i ). На графеони изображаются одной линией без стрелки. Ребро, или дуга, конечные вершины которого совпадают, называется петлей.

Если на каждом ребре задается направление, то граф (G, Х) называется ориентированным. В противном случае граф называется неориентированным.

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

Матрицей инцидентности называется прямоугольная матрица с числом строк, равным числу вершин графа, и с числом столбцов, равным количеству ребер (дуг) графа. Элементы матрицы а задаются следующим образом: “1” ставится в случае если вершина v_i , инцидентна ребру u_j ; “0” - в противном случае.

Вершина и ребро (дуга) называются инцидентными друг другу, если вершина является для этого ребра (дуги) концевой точкой.

Путь из начальной вершины х_н к конечной вершине х_к - последовательность дуг, начинающаяся в вершине х_н ÎХ, заканчивающаяся в вершине х_к ÎХ, и такая, что конец очередной дуги является началом следующей:

(х_н, х_{i 1} )( х_{i 1} , х_{i 2} )( х_{i 2} … х_ik )( х_{ik ,} x_k ) = (x_н , х_к ).

Элементарный путь – путь, в котором вершины не повторяются.

Простой путь - путь, в котором дуги не повторяются.

Маршрут - последовательность ребер, составляющих, как и путь, цепочку.

Длина пути взвешенного графа определяется как сумма весов - его дуг. Если граф не взвешен, то можно считать веса дуг равными 1 .

Кратчайшим путем между выделенной парой вершин х_н и х_к называется путь, имеющий наименьшую длину среди всех возможных путей между этими вершинами.

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

4.2 Словесное описание алгоритма и его работы