Трассировка по алгоритму Краскала. Алгоритм Краскала заключается в следующей последовательности 1 Выписываем все возможные рёбра. 2 Упорядочиваем получившийся список рёбер по длинне. 3 Проводим связь первого ребра из списка. 4 Из списка рёбер выбираем следующее по очереди ребро. 5 Если обе вершины выбраного ребра уже есть в списке проведённых ребер, вычёркиваем это ребро из списка и возвращаемся к п. 4. Если же одна и только одна! из вершин выбраного ребра уже участвует в связи присутствует как вершина в списке проведённых рёбер, то проводим это ребро, иначе возвращаемся к п. 4. 6 Повторяем пункты 4-5 до тех пор, пока список рёбер не опустеет. Проведём трассировку цепи питания 5В. Выпишем список всех возможных рёбер, сразу откидывая ребро, если в списке уже есть ребро с такими же вершинами. 1-2 1-3 1-4 1-5 1-6 1-7 1-8 1-9 1-10 1-11 1-12 1-13 1-14 2-3 2-4 2-5 2-6 2-7 2-8 2-9 2-10 2-11 2-12 2-13 2-14 3-4 3-5 3-6 3-7 3-8 3-9 3-10 3-11 3-12 3-13 3-14 4-5 4-6 4-7 4-8 4-9 4-10 4-11 4-12 4-13 4-14 5-6 5-7 5-8 5-9 5-10 5-11 5-12 5-13 5-14 6-7 6-8 6-9 6-10 6-11 6-12 6-13 6-14 7-8 7-9 7-10 7-11 7-12 7-13 7-14 8-9 8-10 8-11 8-12 8-13 8-14 9-10 9-11 9-12 9-13 9-14 10-11 10-12 10-13 10-14 11-12 11-13 11-14 12-13 12-14 13-14 Упорядочим этот список в порядке увеличения длинны рёбер. Полученый список запишем построчно 5-6 6-11 11-12 4-7 7-10 10-13 3-8 8-9 9-14 1-2 2-3 3-4 4-5 7-8 6-7 9-10 10-11 12-13 13-14 5-11 6-12 4-7 7-13 3-9 8-14 2-4 3-5 6-8 9-11 12-14 1-8 1-9 1-14 3-7 5-7 4-6 4-8 6-10 7-11 9-7 8-10 11-13 10-12 10-14 9-13 2-8 2-7 3-6 5-8 8-11 6-9 9-12 11-14 5-10 6-13 4-9 7-14 7-12 4-11 3-10 8-13 2-9 2-14 3-13 4-14 4-12 5-13 1-4 1-7 1-10 1-13 1-5 1-6 2-13 3-11 5-9 8-12 6-14 2-5 2-6 2-11 3-12 5-14 2-12 Проводим первую связь 5-6. Следующее ребро имеющее общую точку - 6-11. Проводим и его. Проводим следующее ребро 11-12. Следующее проведённое нами ребро 4-5, затем 4-7, 7-10 и 10-13. Теперь 3-4 и 3-8, 8-9 и 9-14. Затем проводим рёбро 2-3 и наконец 1-8. Цепь разведена, поскольку все возможные вершины уже присутствуют в списке проведённых рёбер. Рисунок проведённых дорожек приведёна на рис.3.2. 5 6 11 12 DD10 DD11 DD13 DD12 4 7 10 13 DD9 DD8 DD6 DD7 3 8 9 14 DD5 DD2 DD3 DD4 2 DD1 Рис. 3.2 3.3