Теория графов в системе Maple
Теория графов в системе Maple 8,9
(76 функций и операторов)
  1. acycpoly(G,p) - ациклический полином графа G с переменной p
  2. addedge([{1,2},[3,4]],G) - добавить в граф G ребра или дуги. Ребра в неографе задаются как множества - с вершинами в фигурных скобках, дуги в орграфе списком вершин в квадратных скобках.
  3. addvertex(seq(i,i=1..n),G) - добавить к графу G вершины 1,2 ... n
  4. adjacency(G) - матрица смежности графа G
  5. allpairs(G) - матрица расстояний между вершинами графа G
  6. ancestor(n,T) - вершина-отец вершины n в ориентированном дереве T
  7. arrivals(v,G) - множество ребер, входящих в вершину v орграфа G
  8. charpoly(G, x) - характеристический полином графа (переменная x)
  9. chrompoly(G,x) - хроматический полином графа G (переменная x)
  10. complement(G) - дополнение графа G
  11. complete(n) - полный граф Kn
  12. complete(n,m) - полный двудольный граф Kn,m
  13. components(G) - список вершин в связных компонентах графа
  14. connect(u,v,'weights'=L1,'names'=L2,'directed', G) - соединить две вершины u, v. Можно указать вес, имя и выбрать орграф (directed) или неограф
  15. counttrees(G) - вычисление числа остовов графа G
  16. cycle(n) - циклический граф с n вершинами
  17. cyclebase(G) - множество фундаментальных циклов графа G
  18. daughter(n,T) - сын1 вершины n в ориентированном дереве T
  19. delete(z,G) - удаление ребра или вершины z из графа G
  20. degreeseq(G) - степенная последовательность графа G
  21. departures(v,G) - множество ребер, выходящих из вершины v орграфа G
  22. diameter(G) - диаметр графа G
  23. draw(G) - нарисовать граф G
  24. duplicate() - создание копии графа. Изменение оригинала не влияет на копию
  25. edges(G) - множество ребер графа G
  26. flow(G, s, t, eset, comp, maxflow=f) - определяет максимальный поток в сети из вершины s (источник) в вершину t (сток) графа G. После выполнения процедуры список насыщенных дуг помещается в переменную eset, а в переменную comp - вершины, входящие в насыщенную сеть. Необязательная опция maxflow=f ограничивает поток значением f. Замечена ошибка Maple. В переменную eset часто помещаются лишние дуги.
  27. fundcyc(e,G) - определяет цикл из подмножества e ребер графа G. Предполагается, что e содержит только один цикл
  28. getlabel(G) - определяет порядковый номер графа
  29. girth(G,scyc) - определяет длину кратчайшего цикла в графе G или возвращает "бесконечность", если циклов нет. Номера ребер цикла помещает в переменную scyc.
  30. graph(V,E) - граф, заданный списком вершин V и ребер E
  31. gsimp(G) - создает простой граф из псевдографа или мультиграфа G. Удаляет кратные ребра и петли
  32. head(e1,G) - конец дуги e1 (направленного ребра) орграфа G
  33. icosahedron - создает икосаэдр - регулярный (однородный) граф порядка 12 степени 5.
  34. incidence(G) - матрица инцидентности графа G (строки - вершины, столбцы - ребра)
  35. incident(v,G,In) - множество ребер, инцидентных вершине v. В орграфе можно уточнить incident(v,G,In) - входящие дуги, incident(v,G,Out) - исходящие дуги.
  36. indegree(v,G) - полустепень захода вершины v.
  37. induce(Eset, G) - по данному множеству вершин графа G или ребер создает подграф.
  38. isplanar(G) - проверяет планарность графа G
  39. maxdegree(G) - максимальная степень вершин графа G
  40. mindegree(G) - минимальная степень вершин графа G
  41. mincut(G, s, t, vf) - минимальный разрез, отделяющий вершины s и t. В переменной vf - величина потока
  42. neighbors(v,G) - множество вершин графа G, соседних с вершиной v
  43. new(G) - создать новый граф G
  44. nops(edges(G)) - число ребер графа
  45. outdegree(v,G) - полустепень исхода вершины v
  46. petersen() - граф Петерсена
  47. random(n) - создание случайного графа с n вершинами
  48. shortpathtree(G,v) - выделение из графа G дерева минимальных путей из вершины v
  49. show(G) - иннформация о графе: названия вершин, ребер, таблица весов ребер и др.
  50. spantree(G,s,w) - определение остова наименьшего веса графа G. Корень дерева в вершине s, суммарный вес в переменной w
  51. tail(e1,G) - начало дуги e1 орграфа G
  52. vdegree(v,G) - степень вершины
  53. vertices(G) - множество вершин графа G
  54. void(n) - создание пустого графа с n вершинами. Возможно обращение по списку вершин, например, void({$1..n})


    Программы из книги Кирсанова М.Н. Графы в Maple - М.:ФИЗМАТЛИТ, 2007.
    Графы в Maple


    File translated from TEX by TTH, version 3.64.
    19.8.2005