Пакет функций теории графов networks
Набор функций пакета networks
Графы широко используются при решении многих прикладных и фундаментальных задач. Пользователей, занятых решением таких задач, наверняка порадует пакет networks, содержащий весьма представительный набор функций:
> with(networks); Warning, the names diameter, draw and vertices have been redefined [acycpoly, addedge, addvertex, adjacency, allpairs, ancestor, arrivals, bicomponents, charpoly, chrompoly, complement, complete, components, connect, connectivity, contract, countcuts, counttrees, cube, cycle, cyclebase, daughter, degreeseq, delete, departures, diameter, dinic, djspantree, dodecahedron, draw, duplicate, edges, ends, eweight, flow, flowpoly, fundcyc, getlabel, girth, graph, graphical, gsimp, gunion, head, icosahedron, incidence, incident, indegree, induce, isplanar, maxdegree, mincut, mindegree, neighbors, new, octahedron, outdegree, path, petersen, random, rank, rankpoly, shortpathtree, show, shrink, span, spanpoly, spantree, tail, tetrahedron, tuttepoly, vdegree,vertices, void, vweight]
Объективности ради надо отметить, что в Maple 7 из этого пакета удалено несколько второстепенных функций, которые были в версии Maple V R5. Теория графов используется достаточно широко даже при решении прикладных задач – например, для вычисления оптимальных маршрутов движения железнодорожных составов, наиболее целесообразной раскройки тканей и листов из различных материалов и т. д.
Примеры применения пакета networks
Рассмотрим некоторые избранные функции этого пакета, которые наиболее часто используются при работе с графами. Детали синтаксиса функций можно найти в справочной базе данных Maple 7.
Функции создания графов:
- new – создает пустой граф (без ребер и узлов);
- void – создает пустой граф (без ребер);
- duplicate – создает копию графа;
- complete – создает полный граф;
- random – возвращает случайный граф;
- petersen – создает граф Петерсена. Функции модификации графов:
- addedges – добавляет в граф ребро;
- addvertex – добавляет в граф вершины;
- connect – соединяет одни заданные вершины с другими;
- delete – удаляет из графа ребро или вершину.
Функции контроля структуры графов:
- draw – рисует граф;
- edges – возвращает список ребер графа;
- vertices – возвращает список узлов графа;
- show – возвращает таблицу с полной информацией о графе;.
- ends – возвращает имена вершин графа;
- head – возвращает имя вершины, которая является головой ребер;
- tail – возвращает ими вершины, которая является хвостом ребер;
- incidence – возвращает матрицу инцидентности;
- adjacency – возвращает матрицу смежности;
- eweight – возвращает веса ребер;
- weight – возвращает веса вершин;
- isplanar – упрощает граф, удаляя циклы и повторяющиеся ребра, и проверяет его на планарность (возвращает true, если граф оказался планарным, и false – в противном случае).
Функции с типовыми возможностями графов:
- flow – находит максимальный поток в сети от одной заданной вершины к другой;
- shortpathtree – находит кратчайший путь в графе с помощью алгоритма Дейкстры.