Иллюстрированный самоучитель по Maple 6/7

Пакет функций теории графов 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 – находит кратчайший путь в графе с помощью алгоритма Дейкстры.
Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.