ГРАФЫ В MAPLE

Рис. 5.8

Отметим, что задача коммивояжера является одной из основных тестовых задач для различных алгоритмов. Кроме уже описанных способов, задача может быть решена методами целочисленного линейного программирования [12] и с помощью нейронных сетей Хопфилда [19].

5.27. Алгоритм отжига eqWorld.ipmnet.ru

Алгоритм отжига является одним из современных методов, применяемых в теории искусственного интеллекта. Его описание дано на с. 89 [7].

Приведем программу, которая решает методом отжига ту же задачу и при тех же условиях, что и предыдущая. Это позволит сопоставить методы. Операторы случайного задания координат городов и вычисления матрицы весов возьмем те же, что и в начале программы 36. Все операторы программы 37 идут после строки-метки ### программы 36.

Следует обратить внимание на несколько неожиданную операцию поэлементного умножения вектора на 1 V0:=map(‘*‘,Z,1). Вместо того, чтобы просто записать V0:=Z, пришлось пойти на такое присвоение для снятия зависимости между идентификаторами массивов и их содержимым. Дело в том, что в Maple после выполнения V0:=Z изменение массива Z повлечет немедленное изменение V0, что нежелательно, так как мы хотим запомнить расположение городов в оптимальном маршруте. Другой вариант решения проблемы — классический цикл for i to n do V0[i]:=Z[i] od поэлементного присваивания.

Первый маршрут задается случайным образом. Не намного дольше будет работать более простой вариант: Z[k]:=k. Поскольку городавершины занумерованы без определенного правила, такой маршрут тоже в каком-то смысле случаен.

В ответе вектор V0 транспонируется только для удобства вывода в строку.

eqWorld.ipmnet.ru

Программа 37

>for i to n do W[i,i]:=infinity: od: W;

Случайные числа для перестановок городов

>m:=rand(1..n):

Случайные числа для выбора решения

>p:=rand(1..100):

>L0:=infinity: T:=100.:

>alpha:=0.9:# Коэффициент снижения температуры

>Z0:=Z: # Начальный маршрут

>k:=0: # Счетчик снижений

>for i to 500 do # Основной цикл

>i1:=m(): i2:=m(): # Случайные города

>Z:=Z0:

Меняем местами в маршруте города i1 и i2

>z:=Z[i1]: Z[i1]:=Z[i2]: Z[i2]:=z:

Вычисляем длину получившегося маршрута

>L1:=add(W[Z[i],Z[i+1]],i=1..n-1)+W[Z[n],Z[1]]:

Если длина маршрута уменьшилась, выбираем этот маршрут

>if L1<L0 then L0:=L1: Z0:=Z: k:=k+1:TT[k]:=T:

>L[k]:=L1: V0:=map(‘*‘,Z,1);

Больший маршрут выбираем в зависимости от Р и p( )

>else P0:=p()/100.: # Случайное число

eqWorld.ipmnet.ru

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

62.44332567, [3, 5, 2, 6, 4, 1, 7]

и другой характер изменения температуры (риc. 5.9).

eqWorld.ipmnet.ru

Рис. 5.9

Найденное решение совпадает с одним из решений, полученных с помощью муравьиного алгоритма (см. риc. 5.6 на c. 150).

5.28. Основные функции пакета networks

•addedge([{1,2},[3,4]],G) — добавить в граф G ребраeqWorld.ipmnet.ruили дуги. Ребра в неографе задаются как множества — с вершинами в фигурных скобках, а дуги в орграфе — списком вершин в квадратных скобках. Если требуется задать вес дуги в орграфе, то дуги надо обозначать только квадратными скобками. Если вес можно не указывать, то для сокращения ввода две дуги, соединяющие вершины в разных направлениях, проще ввести как ребро;

•addvertex(seq(i,i=1..n),G) — добавить к графу G вершины 1,2 ,..., n. В опции weights можно в списке указать веса вершин. По умолчанию веса нулевые;

•adjacency(G) — матрица смежности графа G. Данный оператор правильно работает в случае мультиграфов, но для псевдографов он не пригоден. Главная диагональ этой матрицы нулевая;

•allpairs(G) — матрица пар расстояний между вершинами графа G;

•ancestor(n,T) — вершина-отец вершины n в ориентированном дереве T;

•arrivals(v,G) — множество ребер, входящих в вершину v орграфа G;основные

eqWorld.ipmnet.ru

•bicomponents(G) — выделение множеств ребер, составляющих блоки 1 неографа G. Мосты помещаются в отдельное множество впереди компонент;

•charpoly(G, x) — характеристический полином графа G (переменная x);

•chrompoly(G,x) — хроматический полином графа G (переменная x);

•complement(G) — дополнение графа G. Например, дополнением к графу на рис. 1.2 (см. с. 10) является граф на рис. 5.10;

1

•complete(n) — полный граф Kn; eqWorld.ipmnet.ru

•complete(n,m) — полный двудольный граф Kn,m;

•components(G) — список вершин в связных компонентах графа;

•connect({u,v},’weights’=L1,’names’=L2,’directed’,

G) — соединить две вершины — u и v. Можно указать вес, имя и выбрать орграф (directed) или неограф. Оператор позволяет соединить сразу несколько вершин с одной, например connect(1,{2,3,4},G);

•connectivity(G) — число λ(G) реберной связности (наименьшее число ребер графа G, удаление которых приводит к несвязному графу);

•contract(u,v,G) — совмещение вершин, или стягивание ребра, соединяющего вершины u и v графа G;

•counttrees(G) — вычисление количество остовов графа G;

1 Вершина называется точкой сочленения графа, если ее удаление приводит

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

eqWorld.ipmnet.ru

мер, для G:=cube(3) имеем следующее изображение: draw(Concentric([0,1,3,2],[4,5,7,6]),G);

•cycle(n) — циклический граф с n вершинами;

•cyclebase(G) — множество фундаментальных циклов графа G;

•daughter(n,T) — сын 1 вершины n в ориентированном дереве;

•degreeseq(G) — степенная последовательность графа G;

•delete(z,G) — удаление ребра или вершины z из графа G;

•departures(v,G) — множество ребер, выходящих из вершины v орграфа G;

•diameter(G) — диаметр графа G; eqWorld.ipmnet.ru

•dinic(G,1,2,eset,comp) — определение максимального потока в сети (см. flow);

•djspantree(G) — разбиение графа на реберно-непересекающиеся деревья, так, чтобы большинство из них было остовами (алгоритм Эдмондса 2 );

•dodecahedron() — создание додекаэдра, т.е. регулярного (однородного) графа порядка 20 степени 3;

•draw(G) — рисунок графа G;

•draw3d(G) — трехмерное изображение графа G. Координаты вершин принимаются в соответствии с собственными векторами матрицы смежности;

•duplicate() — создание копии графа. Изменение оригинала не влияет на копию;

•edges(G) — множество ребер графа G;

•ends(G) — множество пар концов ребер графа G (или ends(e1,G) — концы ребра e1);

1 Дословно — дочь.

2 Edmonds J.

eqWorld.ipmnet.ru

•flow(G, s, t, eset, comp, maxflow=f) — определение максимального потока в сети из вершины s (источник) в вершину t (сток) графа G. После выполнения процедуры список насыщенных дуг помещается в переменную eset, а в переменную comp помещаются вершины, входящие в насыщенную сеть. Необязательная опция maxflow=f ограничивает поток значением f. Замечена ошибка Maple: в переменную eset часто помещаются лишние дуги;

•fundcyc(e,G) — определение цикла из подмножества e ребер графа G. Предполагается, что e содержит только один цикл;

•getlabel(G) — определение порядкового номера графа;

•girth(G,scyc) — определение длины кратчайшего цикла в графе G или возвращение «бесконечности», если циклов нет. Номера ребер цикла помещаются в переменную scyc;

•graph(V,E) — граф, заданный списком вершин V и ребер eqWorld.ipmnet.ruE;

•graphical([sp] — проверка графичности степенной последовательности sp. Если заданной последовательности соответствует граф, то оператор создает список ребер. Можно задать мультиграф: graphical([sp],’MULTI’);

•gsimp(G) — создание простого графа из псевдографа или мультиграфа G. Удаление кратных ребер и петель;

•gunion(G,J,’SIMPLE’) — объединение двух графов. В полученном графе множество вершин является объединением множеств вершин графов G и J. Если опустить опцию SIMPLE, то в полученном графе допускаются кратные ребра (мультиграф);

•head(e1,G) — конец дуги e1 (направленного ребра) орграфа G;

•icosahedron — создание икосаэдра, т.е. регулярного (однородного) графа порядка 12 степени 5;

•incidence(G) — матрица инцидентности графа G (строки — вершины, столбцы — ребра);

•incident(v,G,In) — множество ребер, инцидентных вершине v. В орграфе можно уточнить: incident(v,G,In) — входящие дуги, incident(v,G,Out) — исходящие дуги;

•indegree(v,G) — полустепень захода вершины v;

•induce(Eset, G) — создание подграфа по данному множеству вершин или ребер графа G;

eqWorld.ipmnet.ru

•isplanar(G) — проверка планарности графа G;

•maxdegree(G) — максимальная степень вершин графа G;

•mincut(G, s, t, vf) — минимальный разрез, отделяющий вершины s и t. В переменной vf — величина потока;

•mindegree(G) — минимальная степень вершин графа G;

•neighbors(v,G) — множество вершин графа G, соседних с вершиной v;

•new(G) — создание нового графа G;

•nops(edges(G)) — число ребер графа;

•octahedron() — создание октаэдра, т.е. регулярного (однородного) графа порядка 6 степени 4;

•outdegree(v,G) — полустепень1 исхода вершины v; eqWorld.ipmnet.ru

•petersen() — граф Петерсена, т.е. регулярный (однородный) граф порядка 10 степени 3 (рис. 5.11);3

8

10

6 1

7

9

4

5

Рис. 5.11

•random(n) — создание случайного графа с n вершинами;

•rank(E1,G) — ранг подграфа G с подмножеством ребер E1, т.е. n −k, где n = |V | — порядок графа G(V,E), k — число компонент связности графа G(V,E1);

•rankpoly(G, x, y) — ранг-полином графа G с переменными x и y;

1 Petersen J.

eqWorld.ipmnet.ru

•shortpathtree(G,v) — выделение из графа G дерева минимальных путей из вершины v;

•show(G) — информация о графе: названия вершин, ребер, таблица весов ребер и т.д.;

•shrink(vset,G,u) — стягивание множества вершин vset графа G с образованием из них новой вершины (узла) u;

•span(eset,G) — определение множества ребер графа G, концы которых принадлежат множеству eset концов ребер графа G;

•spantree(G,s,w) — определение остова наименьшего веса графа G. Корень дерева — в вершине s, суммарный вес остова — в переменной w;

•tail(e1,G) — начало дуги e1 орграфа G;

•tetrahedron() — создание тетраэдра — регулярного (однородного) графа порядка 4 степени 3, или, что то же самое, полногоeqWorld.ipmnet.ru графа K4;

•tuttepoly(G,i,j) — создание полинома Татта по i и j;

•vdegree(v,G) — степень вершины;

•vertices(G) — множество вершин графа G;

•void(n) — создание пустого графа с n вершинами. Возможно обращение по списку вершин, например void({$1..n}) или void({a,b,c1,c2});

•vweight(G) — определение весов вершин графа. Возможно обращение по списку вершин, например vweight([1,2],G), или обращение к отдельной вершине. Здесь под весом вершины понимается число, введенное оператором addvertex в опции weights, а не вес вершины дерева при определении центроида (см. с. 40).

eqWorld.ipmnet.ru