X:	1	2	3	4	5	6	7	8
	0	1	0	0	1	1	1	1

1. Начинаем формировать список смежности ориентированного дерева (Г’). Для этого берем вершину v и выписываем из списка смежности исходного графа (Г) вершины, совпадающие с вершинами, находящимися в структуре Т (это будут вершины, смежные с v), то есть

Г’: 5 – 2, 6, 7, 8;

1. Затем извлекаем из структуры Т вершину 8 (v = 8). Дополняем список смежности Г’ восьмой вершиной. У нее нет смежных вершин.

T:

2

6

7

Г’: 5 – 2, 6, 7, 8; 8 – ;

1. Затем извлекаем из структуры Т вершину 7 (v = 7). Дополняем список смежности Г’.

T:

2

6

Г’: 5 – 2, 6, 7, 8; 8 – ; 7 – ;

1. Затем извлекаем из структуры Т вершину 6 (v = 6). Дополняем список смежности Г’.

T:

2

Г’: 5 – 2, 6, 7, 8; 8 – ; 7 – ; 6 – ;

1. Затем извлекаем из структуры Т вершину 2 (v = 2). В структуру Т вносим номера вершин, смежных с вершиной 2 (ранее не пройденных). Дополняем список смежности Г’.

T:

1

4

X:	1	2	3	4	5	6	7	8
	1	1	0	1	1	1	1	1

Г’: 5 – 2, 6, 7, 8; 8 – ; 7 – ; 6 – ; 2 – 1, 4;

1. Извлекаем из структуры Т вершину 4 (v = 4). Дополняем список смежности Г’.

T:

1

Г’: 5 – 2, 6, 7, 8; 8 – ; 7 – ; 6 – ; 2 – 1, 4; 4 – ;

1. Извлекаем из структуры Т вершину 1 (v = 1). Дополняем список смежности Г’. Помещаем смежные с ней вершины (ранее не пройденные) в Т.

T:

3

X:	1	2	3	4	5	6	7	8
	1	1	1	1	1	1	1	1

Г’: 5 – 2, 6, 7, 8; 8 – ; 7 – ; 6 – ; 2 – 1, 4; 4 – ; 1 – 3;

1. Извлекаем из структуры Т вершину 3 (v = 3). Дополняем список смежности Г’.

T:

Г’: 5 – 2, 6, 7, 8; 8 – ; 7 – ; 6 – ; 2 – 1, 4; 4 – ; 1 – 3; 3 – ;

1. Структура Т пуста. Обход графа закончен. Получили следующий список смежности ориентированного дерева (Г’):

1 – 3

2 – 1, 4

3 –

4 –

5 – 2, 6, 7,8

6 –

7 –

8 –

Задания

Задание 1. Построить из исходного неориентированного дерева ориентированное методом обхода в глубину из первой вершины.

1.

2.

3.

4.

5.

6.

Задание 2. Построить из исходного неориентированного дерева ориентированное методом обхода в глубину из третьей вершины.

7.

8.

9.

10.

11.

12.

Задание 3. Построить из исходного неориентированного дерева ориентированное методом обхода в глубину из второй вершины.

13.

14.

15.

16.

17.

18.

Задание 4. Построить из исходного неориентированного дерева ориентированное методом обхода в глубину из четвертой вершины.

19.

20.

21.

22.

23.

24.

Задание 5. Построить из исходного неориентированного дерева ориентированное методом обхода в глубину из первой вершины.

25.

26.

27.

28.

29.

30.

Алгоритм ТэррИ

Описание алгоритма

Алгоритм Тэрри – алгоритм поиска маршрута в связном графе G (V,E), соединяющего заданные вершины v и w. Исходя из вершины v и осуществляя последовательный переход от каждой достигнутой вершины к смежной ей вершине, всегда можно найти маршрут в связном графе G (V,E), соединяющий заданные вершины v и w. Переход от вершины к вершине согласно алгоритму осуществляется по следующим правилам:

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

2. исходя из некоторой вершины v^‘, нужно всегда следовать по тому ребру, которое не было пройдено или было пройдено в противоположном направлении;

3. для всякой вершины v^‘, отличной от v, необходимо отмечать пометкой «х» первое заходящее ребро, если вершина v^‘ встречается первый раз;

4. исходя из вершины v^‘, отличной от v, по первому заходящему в v^‘ ребру нужно идти лишь тогда, когда нет других возможностей.

Пример

	Рассмотрим алгоритм Тэрри на примере поиска маршрута между вершинами 1 и 4 графа G (V, E) (рис. 4). Если это не противоречит правилам алгоритма, то переходить от одной вершины будем к смежной ей с меньшим номером.
Рис. 4

1. Переходим из вершины 1 в вершину 2. отмечаем направление прохода ребра (рис. 5).

1. Из вершины 2 можем перейти к вершинам 3 и 5, а также к вершине 1, но лишь в том случае, если нет других вариантов. Переходим к вершине 3. Отмечаем направление перехода (рис. 6).

   Рис. 5	Рис. 6

2. Из третьей вершины переходим в первую, так как она имеет наименьший номер среди всех возможных вариантов перехода (рис. 7).

1. Первая вершина смежна с вершинами 2, 3 и 5. В вершину 2 мы не можем осуществить переход, так как это направление уже отмечено. В вершину 3 осуществлять переход не будем, так как ребро 1-3 уже отмечено как заходящее в вершину 1 и существует альтернатива перехода к вершине 5. Следовательно, переходим к вершине 5. Отмечаем направление перехода (рис. 8).

Рис. 7	Рис. 8

1. Из вершины 5 переходим к вершине 2, так как она имеет наименьший номер среди всех возможных вариантов перехода (рис. 9).

1. Из вершины 2 переходим к вершине 1, так как ребро, связывающее эти вершины, отмечено как заходящее в вершину 2, а не отмеченных ребер при рассматриваемой вершине нет. Отмечаем направление перехода (рис. 10).

Рис. 9	Рис. 10

1. Из вершины 1 можно перейти только к вершине 3 (рис. 11).

1. Из вершины 3 осуществляем переход к вершине 4, так как она имеет наименьший номер среди всех альтернативных вариантов (рис. 12). Поиск маршрута окончен.

Рис. 11	Рис. 12

Маршрут из вершины 1 в вершину 4 в соответствии с алгоритмом Тэрри имеет вид:

1 – 2 – 3 – 1 – 5 – 2 – 1 – 3 – 4

Задания:

Определить путь обхода графов.

1. Обход в ширину из точки 3.

2. Обход в ширину из точки 1.

3. Обход в ширину из точки 5.

4. Обход в глубину из точки 1.

5. Обход в глубину из точки 2.

6. Обход в ширину из точки 2.

7. Обход в ширину из точки 4.

8. Обход в глубину из точки 1.

9. Обход в глубину из точки 3.

10. Обход в глубину из точки 5.

11. Обход в ширину из точки 1.

12. Обход в ширину из точки 4.

13. Обход в ширину из точки 5.

14. Обход в глубину из точки 2.

15. Обход в глубину из точки 6.

16. Обход в ширину из точки 2.

17. Обход в ширину из точки 6.

18. Обход в глубину из точки 3.

19. Обход в глубину из точки 5.

20. Обход в глубину из точки 1.

21. Обход в ширину из точки 1.

22. Обход в ширину из точки 3.

23. Обход в ширину из точки 4.

24. Обход в глубину из точки 6.

25. Обход в глубину из точки 2.

26. Обход в ширину из точки 2.

27. Обход в ширину из точки 5.

28. Обход в глубину из точки 1.

29. Обход в глубину из точки 3.

30. Обход в глубину из точки 4.

Матроиды. Жадные алгоритмы.

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

Описание алгоритма

Матроидом М = < E,  > называется конечное множество Е, число элементов которого равно n (E= n), и семейство его подмножеств , которое содержится в множестве всех подмножеств множества Е (  2^E ) такое, что выполняются следующие три аксиомы:

М₁: пустое множество принадлежит подмножеству  (    );

М₂: если множество А принадлежит подмножеству , то и множество В, которое содержится в множестве А, тоже принадлежит подмножеству .

(А    В  А  В  );

М₃: если множества А и В принадлежат подмножеству  и количество элементов множества А на один элемент меньше, чем в множестве В, то существует элемент, принадлежащий разности множеств В и А, такой, что объединение его с множеством А будет принадлежать подмножеству .

(А,В    В=А+1   е  В\А, А  е   )