Элементы множества  называются независимыми, а остальные подмножества Е (2^Е \ )– зависимыми. Пусть множество Х (произвольное множество) содержится в множестве Е. Максимальным независимым подмножеством множества Х называется множество Y такое, что если множество Y, принадлежащее независимому множеству , содержится в множестве Х и Z, принадлежащем независимому множеству , содержится в множестве Х, то множество Z содержится в множестве Y (YХ  Y  ZX  ZY) . Множество максимальных независимых подмножеств множества Х обозначим Х.

Рассмотрим следующее утверждение, справедливое для любого Х:

М₄: максимальные независимые подмножества данного множества равномощны ( Y  Х  Z  Х  Y= Z).

Пусть М = < E,  > и выполнены аксиомы М₁ и М₂ . Тогда аксиома М₃ и утверждение М₄ эквивалентны, то есть М₁, М₂, М₄ - эквивалентная система аксиом матроида.

Пусть имеются конечное множество Е, весовая функция  и семейство   2^E. Необходимо выбрать в указанном семействе  подмножество Х наибольшего веса. Для решения этой задачи будем считать, что множество Е упорядочено в порядке убывания весов элементов. В начале множество Х пусто. Затем проверяем каждый элемент множества Е, начиная с первого: если объединение его с множеством Х принадлежит указанному семейству , то добавляем его в множество Х, если не принадлежит семейству , то рассматриваем следующий элемент, и так до n-го.

Алгоритм такого типа называется жадным. Очевидно, что жадный алгоритм является очень эффективным, он за наименьшее количество шагов находит искомое подмножество. Жадные алгоритмы и их свойства исследованы сравнительно недавно, но их значение в практике программирования чрезвычайно велико. Если удается свести конкретную экстремальную задачу к такой постановке, где множество допустимых вариантов (из которых необходимо выбрать наилучший) является матроидом, то в большинстве случаев следует сразу применять жадный алгоритм, поскольку он достаточно эффективен в практическом смысле. Если же наоборот, оказывается, что множество допустимых вариантов не образует матроида, то это «плохой признак». Скорее всего, данная задача окажется труднорешаемой. В этом случае целесообразно тщательно исследовать задачу для предварительного получения теоретических оценок сложности, чтобы избежать бесплодных попыток «изобрести» эффективный алгоритм там, где это на самом деле невозможно.

Другими словами, если М = < E,  > - матроид, то для любой весовой функции  жадный алгоритм находит независимое множество Х с наибольшим весом; если же М = < E,  > не является матроидом, то существует такая функция , что множество Х, найденное жадным алгоритмом, не будет максимальным.

Пусть G (V,E) – граф. Остовной подграф G (V,E) – это подграф, содержащий все вершины. Остовной подграф, являющийся деревом, называется остовом. Несвязный граф не имеет остова, связный граф может иметь много остовов. Если задать длины рёбер, то можно поставить задачу нахождения кратчайшего остова. Существует множество различных способов найти какой-то остов графа. Множество кратчайших путей из заданной вершины ко всем остальным тоже образует остов. Однако этот остов может не быть кратчайшим. На рис. 13 показаны диаграмма графа, дерево кратчайших путей из вершины один с суммарным весом 5 и два кратчайших остова этого графа.

Рис. 13

Одним из способов нахождения кратчайшего остова в связном графе является алгоритм Краскала. Он является частным случаем жадного алгоритма. Заметим, что множество подмножеств множества рёбер, не содержащих циклов, образует матроид.

Алгоритм Краскала

Алгоритм Краскала основан на выборе ребер графа, составляющих его наикратчайший остов. Изначально известен список ребер графа с их длинами. Выбор происходит по двум критериям:

1. так как остов должен быть кратчайшим, выбор начинается с ребер минимальной длины;

2. так как остов – это дерево (структура, не содержащая циклов), каждое выбранное ребро проверяется: не составляет ли оно цикла с ранее выбранными ребрами.

Цикл проходит n = v - 1 раз, где v – количество вершин графа.

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

Пример

На рис. 14 задан граф. Необходимо найти его минимальный остов при помощи алгоритма Краскала.

Решение:

Представим список ребер исходного графа с указанием длины каждого из них. Затем отсортируем ребра в порядке возрастания их длин.

Рис. 14

Исходный список		Отсортированный список
(1,2) - 2		(2,3) - 1
(1,4) - 3		(4,5) - 1
(2,3) - 1		(8,9) - 1
(2,5) - 2		(1,2) - 2
(3,6) - 3		(2,5) - 2
(4,5) - 1		(6,9) - 2
(4,7) - 4		(1,4) - 3
(5,6) - 4		(3,6) - 3
(5,8) - 3		(5,8) - 3
(6,9) - 2		(4,7) - 4
(7,8) - 4		(5,6) - 4
(8,9) - 1		(7,8) - 4

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

Шаг	Массив ребер	Компонента связности

Во втором столбце формируем массив ребер по принципу:

Шаг 1. Помещаем в первый столбец первое ребро отсортированного списка. Компонента связности данного ребра будет соответствовать вершинам, которые данное ребро связывает.

Шаг 2…Шаг N. Рассматриваем n-е ребро отсортированного списка:

1. добавляем ребро в массив, если оно удовлетворяет условию ацикличности;

2. пропускаем ребро в противном случае.

И так далее до конца списка ребер.

Проверка ацикличности формируемого массива производится при помощи третьего столбца таблицы, в который помещаются компоненты связности «леса», разрастающегося во втором столбце. Компоненты связности формируются следующим образом:

1. Если вершины добавляемого ребра не входят ни в одну из уже существующих компонент связности, то формируется новая компонента связности из двух вершин.

Шаг	Массив ребер	Компонента связности
1	(2,3)
2	(2,3); (4,5)
3	(2,3); (4,5); (8,9)

1. Если одна из вершин добавляемого ребра входит в одну из имеющихся компонент связности, то ребро заносится в массив, соответствующий компоненте связности, а вторая вершина добавляемого ребра присоединяется к имеющейся компоненте.

Шаг	Массив ребер	Компонента связности
4	(2,3); (4,5); (8,9); (1,2)

1. Если одна вершина рассматриваемого ребра входит в одну из имеющихся компонент связности, а вторая – в другую, то компоненты связности и массивы ребер объединяются.

Шаг	Массив ребер	Компонента связности
5	(2,3); (4,5); (8,9); (1,2); (2,5)

4) Если обе вершины рассматриваемого ребра принадлежат одной компоненте связности, то ребро исключается из рассмотрения, в таблицу изменения не вносятся. В рассматриваемом примере такими ребрами являются (1,4), (5,8), (5,6) и (7,8).

Продолжим решение задачи при помощи алгоритма Краскала, учитывая перечисленные условия.

Шаг	Массив ребер	Компонента связности
6	(2,3); (4,5); (8,9); (1,2); (2,5); (6,9)
7	(2,3); (4,5); (8,9); (1,2); (2,5); (6,9) [(1,4)]
Шаг	Массив ребер	Компонента связности
8	(2,3); (4,5); (8,9); (1,2); (2,5); (6,9); (3,6)
9	(2,3); (4,5); (8,9); (1,2); (2,5); (6,9); (3,6) [(5,8)]
10	(2,3); (4,5); (8,9); (1,2); (2,5); (6,9); (3,6); (4,7)
11	(2,3); (4,5); (8,9); (1,2); (2,5); (6,9); (3,6); (4,7) [(5,6)]
12	(2,3); (4,5); (8,9); (1,2); (2,5); (6,9); (3,6); (4,7) [(7,8)]

Примечание: в квадратных скобках указано рассматриваемое на данном шаге ребро, но не включаемое в массив ребер в силу выполнения условия 4.

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

Таким образом, минимальным остовом исходного графа является остов, состоящий из ребер (2,3); (1,2); (2,5); (4,5); (8,9); (6,9); (3,6); (4,7).

Задания

Найти минимальный остов графа, заданного списком ребер, при помощи алгоритма Краскала.

1. (1,2) – 3; (1,3) – 6; (1,4) – 2; (1,5) – 5; (2,3) – 4; (2,4) – 3; (2,5) – 1;
   (3,4) – 2; (3,5) – 5; (4,5) – 2.

2. (1,2) – 6; (1,6) – 5; (1,8) – 5; (2,3) – 4; (3,4) – 1; (3,8) – 3; (4,5) – 1;
   (4,7) – 2; (5,6) – 2; (6,7) – 4; (7,8) – 1.

3. (1,2) – 5; (1,3) – 3; (1,6) – 4; (2,3) – 6; (2,6) – 1; (3,4) – 2; (3,5) – 5;
   (4,5) – 1; (4,6) – 1; (5,6) – 4.

4. (1,2) – 1; (1,3) – 7; (1,6) – 5; (2,3) – 4; (2,6) – 2; (3,4) – 3; (3,5) – 6;
   (3,6) – 1; (4,5) – 2; (4,6) – 5; (5,6) – 3.

5. (1,2) – 1; (1,8) – 2; (2,3) – 2; (2,4) – 7; (2,8) – 3; (3,4) – 5; (4,5) – 5;
   (4,6) – 6; (5,6) – 3; (6,7) – 4; (6,8) – 1; (7,8) – 1.

6. (1,2) – 4; (1,3) – 5; (1,4) – 2; (1,5) – 3; (2,3) – 1; (2,4) – 2; (2,5) – 3;
   (3,4) – 5; (3,5) – 6; (4,5) – 7.

7. (1,2) – 4; (1,6) – 1; (1,8) – 6; (2,3) – 5; (3,4) – 2; (3,8) – 7; (4,5) – 2;
   (4,7) – 3; (5,6) – 3; (6,7) – 5; (7,8) – 5.

8. (1,2) – 1; (1,3) – 7; (1,6) – 5; (2,3) – 4; (2,6) – 2; (3,4) – 3; (3,5) – 6;
   (4,5) – 2; (4,6) – 5; (5,6) – 3.

9. (1,2) – 5; (1,3) – 3; (1,6) – 4; (2,3) – 6; (2,6) – 1; (3,4) – 2; (3,5) – 5;
   (3,6) – 2; (4,5) – 1; (4,6) – 1; (5,6) – 4.

10. (1,2) – 5; (1,8) – 1; (2,3) – 1; (2,4) – 3; (2,8) – 2; (3,4) – 1; (4,5) – 4;
    (4,6) – 5; (5,6) – 4; (6,7) – 6; (6,8) – 2; (7,8) – 2.

11. (1,2) – 5; (1,3) – 3; (1,4) – 7; (1,5) – 2; (2,3) – 2; (2,4) – 1; (2,5) – 2;
    (3,4) – 4; (3,5) – 5; (4,5) – 2.

12. (1,2) – 5; (1,6) – 2; (1,8) – 5; (2,3) – 3; (3,4) – 1; (3,8) – 2; (4,5) – 7;
    (4,7) – 2; (5,6) – 2; (6,7) – 4; (7,8) – 1.

13. (1,2) – 2; (1,3) – 2; (1,6) – 4; (2,3) – 5; (2,6) – 1; (3,4) – 2; (3,5) – 5;
    (4,5) – 7; (4,6) – 1; (5,6) – 3.

14. (1,2) – 3; (1,3) – 1; (1,6) – 4; (2,3) – 7; (2,6) – 2; (3,4) – 5; (3,5) – 4;
    (3,6) – 1; (4,5) – 3; (4,6) – 2; (5,6) – 1.

15. (1,2) – 3; (1,8) – 2; (2,3) – 3; (2,4) – 1; (2,8) – 5; (3,4) – 2; (4,5) – 4;
    (4,6) – 4; (5,6) – 1; (6,7) – 7; (6,8) – 1; (7,8) – 5.

16. (1,2) – 2; (1,3) – 4; (1,4) – 1; (1,5) – 1; (2,3) – 3; (2,4) – 5; (2,5) – 2;
    (3,4) – 3; (3,5) – 4; (4,5) – 6.

17. (1,2) – 2; (1,6) – 3; (1,8) – 4; (2,3) – 4; (3,4) – 5; (3,8) – 6; (4,5) – 1;
    (4,7) – 2; (5,6) – 1; (6,7) – 3; (7,8) – 1.

18. (1,2) – 3; (1,3) – 6; (1,6) – 3; (2,3) – 2; (2,6) – 5; (3,4) – 1; (3,5) – 4;
    (4,5) – 1; (4,6) – 1; (5,6) – 2.

19. (1,2) – 2; (1,3) – 2; (1,6) – 4; (2,3) – 5; (2,6) – 1; (3,4) – 2; (3,5) – 5; (3,6) – 3; (4,5) – 7; (4,6) – 1; (5,6) – 3.

20. (1,2) – 2; (1,8) – 1; (2,3) – 7; (2,4) – 2; (2,8) – 2; (3,4) – 1; (4,5) – 4; (4,6) – 5; (5,6) – 3; (6,7) – 5; (6,8) – 3; (7,8) – 4.

21. (1,2) – 7; (1,3) – 1; (1,4) – 3; (1,5) – 5; (2,3) – 3; (2,4) – 2; (2,5) – 2; (3,4) – 4; (3,5) – 4; (4,5) – 1.

22. (1,2) – 7; (1,6) – 3; (1,8) – 4; (2,3) – 1; (3,4) – 2; (3,8) – 1; (4,5) – 3; (4,7) – 2; (5,6) – 5; (6,7) – 4; (7,8) – 2.

23. (1,2) – 3; (1,3) – 1; (1,6) – 4; (2,3) – 7; (2,6) – 2; (3,4) – 5; (3,5) – 4; (4,5) – 3; (4,6) – 2; (5,6) – 1.

24. (1,2) – 2; (1,3) – 7; (1,6) – 4; (2,3) – 1; (2,6) – 3; (3,4) – 5; (3,5) – 6; (3,6) – 5; (4,5) – 4; (4,6) – 7; (5,6) – 2.

25. (1,2) – 2; (1,8) – 3; (2,3) – 4; (2,4) – 7; (2,8) – 5; (3,4) – 7; (4,5) – 4; (4,6) – 6; (5,6) – 2; (6,7) – 1; (6,8) – 5; (7,8) – 5.

26. (1,2) – 1; (1,3) – 2; (1,4) – 4; (1,5) – 5; (2,3) – 2; (2,4) – 3; (2,5) – 1; (3,4) – 4; (3,5) – 6; (4,5) – 7.

27. (1,2) – 1; (1,6) – 2; (1,8) – 6; (2,3) – 2; (3,4) – 3; (3,8) – 7; (4,5) – 4; (4,7) – 1; (5,6) – 5; (6,7) – 4; (7,8) – 7.

28. (1,2) – 2; (1,3) – 7; (1,6) – 4; (2,3) – 1; (2,6) – 3; (3,4) – 5; (3,5) – 6; (4,5) – 4; (4,6) – 7; (5,6) – 2.

29. (1,2) – 3; (1,3) – 1; (1,6) – 4; (2,3) – 7; (2,6) – 2; (3,4) – 5; (3,5) – 4; (3,6) – 5; (4,5) – 3; (4,6) – 2; (5,6) – 1.

30. (1,2) – 3; (1,8) – 2; (2,3) – 3; (2,4) – 1; (2,8) – 5; (3,4) – 2; (4,5) – 4; (4,6) – 4; (5,6) – 1; (6,7) – 7; (6,8) – 5; (7,8) – 5.

Нахождение кратчайшего пути

в сети без контуров

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