Warning: include(/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/wp-cache-base.php): failed to open stream: No such file or directory in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 65

Warning: include(): Failed opening '/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/wp-cache-base.php' for inclusion (include_path='.:/opt/alt/php55/usr/share/pear:/opt/alt/php55/usr/share/php') in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 65

Warning: include_once(/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/ossdl-cdn.php): failed to open stream: No such file or directory in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 82

Warning: include_once(): Failed opening '/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/ossdl-cdn.php' for inclusion (include_path='.:/opt/alt/php55/usr/share/pear:/opt/alt/php55/usr/share/php') in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 82
Графы и их функции | Учебники

Главная > Mathematica 8 > Графы и их функции


Графы и их функции

Графы и их функции
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

Одной из самых важных функций этой группы является функция ShowGraph (показать граф). Она обеспечивает визуальное представление графа, заданного аргументом функции. Покажем работу избранных функций этой группы на нескольких примерах.
На показано построение полного графа и его таблицы. Параметром графа является число 6, характеризующее число узловых точек графа, соединенных друг с другом.
Изменяя значение параметра графа, можно получить множество других графов. На показан вид двух разных графов. Верхний граф — многолучевая звезда с добавленным отрезком, полученная с помощью функции AddEdge. Первый аргумент задает исходный граф (в нашем случае — звезду с 11 узлами), а второй — соединяемые отрезком прямой точки. Нижний рисунок иллюстрирует построение подграфа.
Еще пара графов представлена на. Этот рисунок иллюстрирует применение функций Contract и 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

Рисунок показывает применение функций 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

Рисунок (сверху) показывает применение функции OrientGraph для построения ориентированного графа, который представляется стрелками. Там же (снизу) показано применение функции ShowLabeledGraph для построения графа с маркированными числами вершинами. Напомним, что функция ShowGraph позволяет наблюдать графы без маркировки вершин.
Построение широко используемой в теории графов диаграммы Хассе (Hasse) иллюстрирует2.

Алгоритмическая теория графов

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

Рисунок показывает действие функции 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}}}}
Рисунок показывает задание на плоскости массива точек data2D, построение планарного графа и его выпуклой огибающей с помощью функции Convex-Hull.
Наконец, на6 показаны результаты действия еще двух функций — построение диаграммы и триангуляция в пространстве.
Дискретные функции единичного скачка и импульса — 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]
Рисунок иллюстрирует применение функции единичного скачка в двумерном случае.
В системе Mathematica 8 функция 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]

Статьи по теме

Комментарии запрещены.