Пакет дискретной математики DiscreteMath
Пакет DiscreteMath задает набор функций дискретной математики. Это прежде всего функции комбинаторики и работы с графами (более 230 функций). Мы вынуждены рассмотреть их только выборочно.
Комбинаторика и ее функции — Combinatorica и CombinatorialFunctions
Несколько функций комбинаторики (Factorial, Factorial2, Binomial, Multinomial, Pochhammer и Fibonacci) могут использоваться без загрузки пакетов расширения. Рисунок 11.5 демонстрирует работу подпакета Combinatorial-Functions (функции комбинаторики). Определения функций этого пакета есть в справочной базе данных.
Рис. 11.5. Примеры работы с подпакетом функций комбинаторики
Подпакет Combinatorica задает определение ряда функций комбинаторики и теории графов. Ниже представлены имена функций комбинаторики.|
Функции перестановок и сочетаний |
|
|
Backtrack |
BinarySearch |
|
Binary Subsets |
DerangementQ |
|
Derangements |
Distinct Permutations |
|
EquivalenceClasses |
EquivalenceRelationQ |
|
Equivalences |
Eulerian |
|
FromCycles |
FromlnversionVector |
|
GrayCode |
HeapSort |
|
Heapify |
HideCycles |
|
Index |
InversePermutation |
|
Inversions |
InvolutionQ |
|
Josephus |
Ksubsets |
|
Lexicographic Permutations |
LexicographicSubsets |
|
MinimumChangePermutations |
MultiplicationTable |
|
NextKSubset |
Next Permutation |
|
NextSubset |
NthPermutation |
|
NthSubset |
NumberOf Derangements |
|
NumberOf Involutions |
NumberOf Permu tat ion sByCycles |
|
PermutationGroupQ |
PermutationQ |
|
Permute |
Polya |
|
RandomHeap |
RandomKSubset |
|
RandomPermutation |
RandomPermutationl |
|
RandomPermutation2 |
RandomSubset |
|
RankPermutation |
RankSubset |
|
RevealCycles |
Runs |
|
SamenessRelation |
SelectionSort |
|
SignaturePermutation |
StirlingFirst |
|
StirlingSecond |
Strings |
|
Subsets |
ToCycles |
|
ToInversionVector |
TransitiveQ |
<<DiscreteMath`Combinatorica` ?Permute Permute[l, p] permutes list 1 according to permutation p. ?KSubsets KSubsets[l, k] gives all subsets of set 1 containing exactly k elements, ordered lexicographically. KSubsets[{l, 2, 3, 4, 5}, 2] {{1, 2}, {1, 3), {1, 4}, {1, 5}, {2, 3), {2, 4}, {2, 5}, {3, 4}, {3, 5}, (4, 5}} << DiscreteMath`Combinatorica` MinimumChangePermutations[{1,2,3}] {{1, 2, 3}, {2, 1, 3}, {3, 1, 2}, {1, 3, 2}, {2, 3, 1}, {3, 2, 1}} Map[RankPermutation, Permutations[{1,2,3,4}]] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23} InversePermutation[{4,8,5,2,1,3,7,6}] (5, 4, 6, 1, 3, 8, 7, 2} Polya[Table[ RotateRight[Range[8],i], {i,8}], m] 1/8 (4m+2m2 +m4 +m8) Table[NthSubset[n,a,b,c,d], {n,0,15}] {{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}, {d}, (a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}}Вторая группа функций комбинаторики представлена следующими функциями.
|
Функции разделения, композиции и картин Янга |
|
|
CatalanNumber |
Compositions |
|
ConstructTableau |
DeleteFromTableau |
|
DurfeeSquare |
EncroachingListSet |
|
FerrersDiagram |
FirstLexicographicTableau |
|
. Insert IntoTableau |
LastLexicographicTableau |
|
Longest IncreasingSubsequence |
NextComposition |
|
Next Part it ion |
NextTableau |
|
NumberOf Compos it ions |
NumberOf Partitions |
|
NumberOf Tableaux |
PartitionQ |
|
Partitions |
RandomComposition |
|
RandomPartition |
RandomTableau |
|
TableauClasses |
TableauQ |
|
TableauxToPermutation |
Tableaux |
|
TransposePartition |
TransposeTableau |
Рис. 11.6. Примеры работы с функциями разделения, композиции и картин Янга
Этих примеров достаточно, чтобы заинтересованный читатель по их образцу и подобию изучил свойства и возможности нужных ему функций комбинаторики. Mathematica имеет самые обширные возможности решения задач, связанных с графами. Задание графов и манипуляции с ними также включены в пакет комбинаторики. Они представлены четырьмя группами функций.|
Представление графов |
||
|
AddEdge |
AddVertex |
Breadth'FirstTraversal |
|
ChangeEdges |
ChangeVertices |
CircularVertices |
|
CompleteQ |
Contract |
DeleteEdge |
|
DeieteVertex |
DepthFirstTr aversal |
Diameter |
|
DilateVertices |
Distribution |
Eccentricity |
|
Edges |
EmptyQ |
FromAd j acencyLists |
|
FromOrderedPairs |
FromUnorderedPairs |
GraphCenter |
|
GraphComplement |
InduceSubgraph |
M |
|
MakeSimple |
MakeUndirected |
Normal! zeVerticesPointsAndLines |
|
Pseudograph |
RadialEmbedding |
Radius |
|
RankGraph |
RankedEmbedding |
ReadGraph |
|
RemoveSelf Loops |
RootedEmbedding |
RotateVertices |
|
ShakeGraph |
ShowGraph |
ShowLabe 1 edGr aph |
|
SimpleQ |
Spectrum |
SpringErrbedding |
|
ToAdjacencyLists |
ToOrderedPairs |
ToUnorderedPairs |
|
TranslateVertices |
UndirectedQ |
UnweightedQ |
|
Vertices |
WriteGraph |
Рис. 11.7. Пример построения полного графа и его таблицы
Рис. 11.8. Построение графа звезды и подграфа
Рис. 11.9. Примеры построения графов с помощью функций Contractn GridGraph
Приведенный выше набор функций позволяет строить практически любые виды графов и обеспечивает высокую степень их визуализации.|
Создание графов |
||
|
CartesianProduct |
CirculantGraph |
CodeToLabeledTree |
|
CompleteGraph |
Cycle |
DegreeSequence |
|
EmptyGraph |
ExactRandomGraph |
ExpandGraph |
|
Functional-Graph |
GraphDif ference |
Graphlnter section |
|
GraphJoin |
GraphPower |
GraphProduct |
|
GraphSum |
GraphUnion |
GraphicQ |
|
GridGraph |
Hypercube |
IncidenceMatrix |
|
IntervalGraph |
LabeledTreeToCode |
LineGraph |
|
MakeGraph |
NthPair |
Path |
|
RandomGraph |
RandomTree |
RandomVertices |
|
RealizeDegreeSequence |
RegularGraph |
RegularQ |
|
Turan |
Wheel |
- |
Рис. 11.10. Создание графов с помощью функций GraphUnion и GraphProduct С действием других функций нетрудно ознакомиться самостоятельно.
|
Свойства графов |
||
|
ArticulationVertices |
Automorphisms |
Bi Connected Components |
|
BiconnectedQ |
BipartiteQ |
Bridges |
|
ChromaticNumber |
Chromatic Polynomial |
CliqueQ |
|
Connected Components |
ConnectedQ |
DeBruijnSequence |
|
DeleteCycle |
EdgeChromatic Number |
EdgeColoring |
|
EdgeConnectivity |
Element |
EulerianCycle |
|
EulerianQ |
ExtractCycles |
FindCycle |
|
Girth |
GraphPower |
HamiltonianCycle |
|
HamiltonianQ |
Harary |
HasseDiagram |
|
IdenticalQ |
Independent SetQ |
IsomorphicQ |
|
Isomorphism |
IsomorphismQ |
MaximumClique |
|
Maximum lndependentSet |
Minimum VertexCover |
OrientGraph |
|
PartialOrderQ |
PerfectQ |
SelfComplementaryQ |
|
StronglyConnected Components |
TopologicalSort |
TransitiveClosure |
|
TransitiveReduction |
TravelingSalesman |
TravelingSalesman Bounds |
|
TreeQ |
Trianglelnequality |
TwoColoring |
|
VertexColoring |
VertexConnectivity |
VertexCoverQ |
|
WeaklyConnected Components |
Рис. 11.11. Построение графов — ориентированного (сверху) и с маркированными вершинами (снизу)
Построение широко используемой в теории графов диаграммы Хассе (Hasse) иллюстрирует рис. 11.12.|
Алгоритмическая теория графов |
||
|
AllPairsShor test Path |
BipartiteMatchin |
Cofactor |
| Dijkstra | FindSet | GraphPower |
| InitializeUnionFind | Maxima IMatching | MaximumAntichain |
| MaximumSpanningTree | MinimumChainPartition | MinimumSpanningTree |
| NetworkFlowEdges | Networks' low | NumberOfSpanningTrees |
| PathConditionGraph | PlanarQ | Shortest PathSpanningTree |
| ShortestPath | StableMarriage | UnionSet |
Риc. 11.12. Построение диаграммы Хассе
Риc. 11.13. Пример применения функции MinimumSpanningTree
В целом следует отметить, что набор функций в области создания, визуализации и теории графов весьма представителен, так что специалисты в области графов могут найти в этом наборе как типовые, так и уникальные средства.Функции вычислительной геометрии — ComputationalGeometry
В подпакете ComputationalGeometry заданы следующие функции, относящиеся к геометрическим поверхностям:- ConvexHull [ { {xl, yl...}, {х2, у2,...},...] — вычисляет выпуклость оболочки в точках плоскости;
- DelaunayTriangulation[ {{xl,yl...}, {х2, у2,...},...] — вычисляет триангуляцию Делоне (разбивку на выпуклые треугольники) в точках плоскости;
- DelaunayTriangulationQ [ {{xl, yl...}, {х2, у2,...},...}, trival] — тестирует триангуляцию Делоне в точках плоскости; ,
- DiagramPlot [ {{xl, yl...}, {х2, у2,...},...] — построение диаграммы по заданным точкам (после списка параметров возможны спецификации в виде списков diagvert, diagval);
- PlanarGraphPlot [{ {xl, yl...}, {x2, y2,...},...] — построение планарного графа по заданным точкам (после списка параметров возможна спецификация в виде списка indexlist или vals);
- TriangularSurfacePlot [ {{xl,yl, zl}, {x2,y2, z2 },...] — строит поверхность из треугольников по заданным точкам;
- VoronoiDiagramm[ {{xl, yl...}, {х2, у2,...},...] — вычисляет данные для построения диаграммы Вороного.
<<DiscreteMath`ComputationalGeometry` ConvexHull[{{0,2}, {1,1}, {0,0}, {2,0}, {1,2}}] {4, 5, 1, 3} delval = (DelaunayTriangulation[{{l,2J, {0,3}, {1,1}}]) // Short[#,2]& {{1, {2, 3}}, {2, {3, 1}}, {3, {1, 2}}} VoronoiDiagram[{{l,2}, {0,3}, {1,1}}] {{{-0.50000000000000, 1.5000000000000}, Ray [{- 0.50000000000000, 1.5000000000000}, {1.5000000000000, 3.5000000000000}], Ray [ {- 0.50000000000000, 1.5000000000000}, {2.0000000000000,1.50000000000000}], Ray[ {- 0.50000000000000, 1.5000000000000}, {-2.5000000000000, 0.50000000000000} ]}, {{1, {1, 3, 2}}, {2, {1, 2, 4}}, {3, {1, 4, 3}}}}Рисунок 11.14 показывает задание на плоскости массива точек data2D, построение планарного графа и его выпуклой огибающей с помощью функции Convex-Hull.
Рис. 11.14. Пример построения планарного графа и его выпуклой огибающей Выполнение триангуляции Делоне иллюстрирует рис. 11.15.
Рис. 11.15. Выполнение триангуляции Делоне
Наконец, на рис. 11.16 показаны результаты действия еще двух функций — построение диаграммы и триангуляция в пространстве.
Рис. 11.16. Построение диаграммы (сверху) и триангуляция в пространстве (снизу)
Дискретные функции единичного скачка и импульса — KroneckerDelta
В подпакете KroneckerDelta системы Mathematica 3 заданы дискретные функции единичного скачка и единичного импульса:- DiscreteStep [n] — возвращает единичный скачок при целом n=0;
- DiscreteStep [n1, n2,...] — функция многомерного единичного скачка;
- KroneckerDelta [n] — возвращает 1 при целом n=0 и 0 во всех других случаях;
- KroneckerDelta [n1, n2,...] — многомерная функция Кронекера.
<<DiscreteMath` KroneckerDelta` Table[DiscreteStep[n], {n, -3, 3}] {0, 0, 0, 1, 1, 1, 1} Table[DiscreteStep[n], {n, -3, 3, 1/2}] {0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1} Table[KroneckerDelta[n], {n, -2, 2, 1/2}] {0, 0, 0, 0, 1, 0, 0, 0, 0} Sum[KroneckerDelta[n— a]f[n], {n, -Infinity, Infinity}] f[a] Sum[( (KroneckerDelta[n]— KroneckerDelta[n-1]) - (KroneckerDelta[n-1]— KroneckerDelta[n-2]) ) f[n], {n, -Infinity, Infinity}] f[0]-2f[l] +f[2]Рисунок 11.17 иллюстрирует применение функции единичного скачка в двумерном случае.
Рис. 11.17. Пример применения функции скачка в двумерном случае
В системе Mathematica 4 функция KroneckerDelta стала встроенной. В данный подпакет входят еще две функции:- SimplifyDiscreteStep [ехрr] — упрощение выражения ехрг с функциями дискретного скачка;
- SimplifyKroneckerDelta [ехрг] — упрощение выражения ехрг с дельта-функцией Кронекера.
DiscreteStep[n - 1] (KroneckerDelta[n - 2] + DiscreteStep[n, m] DiscreteStep[m - 1]) // SimplifyDiscreteStep DiscreteStep[-1+m] DiscreteStep[-l+m] + KroneckerDelta[-2+n] (f[n] + KroneckerDelta[n]) DiscreteStep[n-l] // SimplifyKroneckerDelta DiscreteStep [ -1 + n] f [ n]
Дискретные перестановки — Permutations
В подпакете Permutations определен ряд функций дискретных перестановок:- RandomPermutation [n] — случайные перестановки из n элементов;
- Ordering [list] — дает перестановки в установленном списком list порядке;
- ToCycles [perm] — дает циклическую декомпозицию для списка list;
- FromCycles [ {cicl, cic2,...}] — возвращает перестановки из циклических декомпозиций cic1, cic2, ...;
- PermutationQ [list] — возвращает True, если список list представляет перестановки, и False в ином случае.
<<DiscreteMath`Permutations` RandomPermutation[16] {16, 12, 11, 5, 3, 4, 9, 14, 2, 8, 15, I, 13, 7, 10, 6} ToCycles[%] {{16, 6, 4, 5, 3, 11, 15, 10, 8, 14, 7, 9, 2, 12, 1}, {13}} FromCycles[%] {16, 12, 11, 5, 3, 4, 9, 14, 2, 8, 15, 1, 13, 7, 10, 6} Ordering[%] {12, 9, 5, 6, 4, 16, 14, 10, 7, 15, 3, 2, 13, 8, 11, 1}
Решение рекуррентных разностных уравнений — RSolve
Для решения рекуррентных разностных уравнений в подпакет RSolve введены следующие функции:- RSolve [eqn, a [n] , n] — решает рекуррентное уравнение для а [n];
- RSolve [eqn, a, n] — решает рекуррентное уравнение для функции а;
- RSolvet {eqnl, eqn2,...}, {al, a2,...},n] — решает систему рекуррентных уравнений, представленных списками.
<<DiscreteMath` RSolve` RSolve[a[n+l] == 2 a[n], a[n], n] {{a[n] -> 2nC[l]}} RSolve[a[n] == a[n-l] + a[n-2], a[0] == a[l] == 1, a[n], n] RSolve[ a[0] == a[l] == 2, (n+1) (n+2) a[n+2]- 2 (n+1) a[n+l]- 3 a[n] == 0, a[n], n]Подпакет Tree содержит функции создания и применения древовидных структур, именуемых деревьями. Вот эти функции:
- MakeTree [list] — создает дерево по информации, представленной в списке list;
- TreeFind [tree, x] — возвращает позицию наименьшего элемента, превосходящего х в списке list, представляющем дерево.
<<DiscreteMath` Tree` MakeTree[{el, e2, е3, е4}] {{e2, 2), {{el, 1}, {}, {}}, {{e3, 3}, {}, {{e4, 4}, {}, {}}}} tree = MakeTree[{8.5, 1.2, 9.1, 3.4, 5., 7.6 ,6.4}] {{6.4, 4}, {{3.4, 2}, {{1.2, 1}, {}, {}}, {{5., 3}, {}, {}}}, {{8.5, 6}, {{7.6, 5}, {}, {}}, {{9.1, 7}, {},{}}}} TreeFind[tree, 1.2] 1 . . TreeFind[tree, 1] 0Для визуализации деревьев служат следующие функции:
- TreePlot [tree] — строит график дерева tree;
- ExprPlot [expr] — строит график, представляющий ехрг в виде дерева.
Рис. 11.18. Примеры визуализации деревьев
Рис. 11.19 . Построение графиков деревьев с помощью функции ExprPlot
|