Прикладные области

Изучение свойств ориентированного графа

Система Mathematica 8 предоставляет широкий набор функций для нахождения свойств ориентированных графов.

In[1]:=

g = \!\(\*

GraphicsBox[

NamespaceBox["NetworkGraphics",

DynamicModuleBox[{Typeset`graph = HoldComplete[

Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,

19, 20}, {{{1, 8}, {5, 8}, {8, 11}, {7, 4}, {2, 9}, {12,

1}, {3, 10}, {6, 13}, {1, 12}, {9, 20}, {12, 9}, {17, 14}, {

8, 1}, {5, 14}, {15, 4}, {8, 5}, {18, 11}, {2, 11}, {20,

13}, {7, 14}, {14, 3}, {8, 19}, {4, 13}, {20, 9}, {7, 16}},

Null}, {EdgeShapeFunction -> {"Arrow"}, EdgeStyle -> {

Directive[

Thickness[Large],

Arrowheads[Medium]]}, VertexSize -> {Medium},

VertexCoordinates -> CompressedData["

1:eJxTTMoPSmViYGAQAWIQjR98sEcTcEDlcqDxBRyw64Px0WkGNPUcaHyYeej2

outjQFfngOY+B1Tz0N2Nbi+6Pg4ctIADALZTEnE=

"]}]], Typeset`boxes = GraphicsGroupBox[{{

Directive[

Hue[0.6, 0.2, 0.8],

EdgeForm[

Directive[

GrayLevel[0],

Opacity[0.7]]]],

TagBox[

DiskBox[{0., 0.}, 0.1], "DynamicName", BoxID -> "VertexID$1"],

TagBox[

DiskBox[{0., 1.}, 0.1], "DynamicName", BoxID -> "VertexID$2"],

TagBox[

DiskBox[{0., 2.}, 0.1], "DynamicName", BoxID -> "VertexID$3"],

TagBox[

DiskBox[{0., 3.}, 0.1], "DynamicName", BoxID -> "VertexID$4"],

TagBox[

DiskBox[{0., 4.}, 0.1], "DynamicName", BoxID -> "VertexID$5"],

TagBox[

DiskBox[{1., 0.}, 0.1], "DynamicName", BoxID -> "VertexID$6"],

TagBox[

DiskBox[{1., 1.}, 0.1], "DynamicName", BoxID -> "VertexID$7"],

TagBox[

DiskBox[{1., 2.}, 0.1], "DynamicName", BoxID -> "VertexID$8"],

TagBox[

DiskBox[{1., 3.}, 0.1], "DynamicName", BoxID -> "VertexID$9"],

TagBox[

DiskBox[{1., 4.}, 0.1], "DynamicName", BoxID -> "VertexID$10"],

TagBox[

DiskBox[{2., 0.}, 0.1], "DynamicName", BoxID -> "VertexID$11"],

TagBox[

DiskBox[{2., 1.}, 0.1], "DynamicName", BoxID -> "VertexID$12"],

TagBox[

DiskBox[{2., 2.}, 0.1], "DynamicName", BoxID -> "VertexID$13"],

TagBox[

DiskBox[{2., 3.}, 0.1], "DynamicName", BoxID -> "VertexID$14"],

TagBox[

DiskBox[{2., 4.}, 0.1], "DynamicName", BoxID -> "VertexID$15"],

TagBox[

DiskBox[{3., 0.}, 0.1], "DynamicName", BoxID -> "VertexID$16"],

TagBox[

DiskBox[{3., 1.}, 0.1], "DynamicName", BoxID -> "VertexID$17"],

TagBox[

DiskBox[{3., 2.}, 0.1], "DynamicName", BoxID -> "VertexID$18"],

TagBox[

DiskBox[{3., 3.}, 0.1], "DynamicName", BoxID -> "VertexID$19"],

TagBox[

DiskBox[{3., 4.}, 0.1], "DynamicName", BoxID -> "VertexID$20"]}, {

Directive[

Opacity[0.7],

Hue[0.6, 0.7, 0.5]],

Directive[

Thickness[Large],

Arrowheads[Medium]],

StyleBox[{

ArrowBox[

BSplineCurveBox[{

DynamicLocation["VertexID$1", Automatic, Center], {

0.031684249309019474`, 0.248193286253986}, {

0.04120411217155184, 0.31075000944454617`}, {

0.05372055966059497, 0.37277669682599374`}, {

0.06920464351033351, 0.4341298919554739}, {

0.08762055185197792, 0.49466769605517624`}, {

0.10892569204010161`, 0.5542500961983914}, {

0.13307078916168003`, 0.6127392891339357}, {

0.16000000000000014`, 0.6700000000000007}, {0.56,

1.4700000000000002`}, {0.58965104218986,

1.5258997951902953`}, {0.6219553382653484,

1.5803093886488848`}, {0.6568381742670464,

1.6331029408853128`}, {0.6942188725418217,

1.6841583500184498`}, {0.7340109783355626,

1.7333575341759286`}, {0.7761224597472949,

1.7805867045960317`}, {0.8204559205822237,

1.8257366288003936`},

DynamicLocation["VertexID$8", Automatic, Center]}]]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[

BSplineCurveBox[{

DynamicLocation["VertexID$1", Automatic, Center], {

0.17426337119960722`, 0.17954407941777717`}, {

0.21941329540396914`, 0.2238775402527058}, {

0.26664246582407225`, 0.26598902166443805`}, {

0.31584164998155106`, 0.3057811274581791}, {

0.3668970591146882, 0.3431618257329542}, {

0.41969061135111596`, 0.3780446617346521}, {

0.4741002048097056, 0.4103489578101406}, {

0.5300000000000007, 0.4400000000000005}, {1.33,

0.8400000000000003}, {1.3872607108660653`,

0.8669292108383204}, {1.4457499038016093`,

0.8910743079598988}, {1.505332303944825,

0.9123794481480224}, {1.5658701080445274`,

0.9307953564896668}, {1.627223303174007,

0.9462794403394053}, {1.6892499905554548`,

0.9587958878284484}, {1.751806713746015,

0.9683157506909807},

DynamicLocation["VertexID$12", Automatic, Center]}]]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$2", Automatic, Center],

DynamicLocation["VertexID$9", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$2", Automatic, Center],

DynamicLocation["VertexID$11", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$3", Automatic, Center],

DynamicLocation["VertexID$10", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$4", Automatic, Center],

DynamicLocation["VertexID$13", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[

BSplineCurveBox[{

DynamicLocation["VertexID$5", Automatic, Center], {

0.17954407941777717`, 3.825736628800393}, {

0.2238775402527058, 3.7805867045960313`}, {

0.26598902166443805`, 3.733357534175928}, {

0.3057811274581791, 3.684158350018449}, {

0.3431618257329542, 3.6331029408853124`}, {

0.3780446617346521, 3.5803093886488844`}, {

0.4103489578101406, 3.525899795190295}, {

0.4400000000000005, 3.4699999999999998`}, {

0.8400000000000003, 2.670000000000001}, {

0.8669292108383204, 2.612739289133936}, {

0.8910743079598988, 2.554250096198391}, {

0.9123794481480224, 2.494667696055176}, {

0.9307953564896668, 2.4341298919554735`}, {

0.9462794403394053, 2.3727766968259933`}, {

0.9587958878284484, 2.310750009444546}, {

0.9683157506909807, 2.2481932862539855`},

DynamicLocation["VertexID$8", Automatic, Center]}]]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$5", Automatic, Center],

DynamicLocation["VertexID$14", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$6", Automatic, Center],

DynamicLocation["VertexID$13", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$7", Automatic, Center],

DynamicLocation["VertexID$4", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$7", Automatic, Center],

DynamicLocation["VertexID$14", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$7", Automatic, Center],

DynamicLocation["VertexID$16", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$8", Automatic, Center],

DynamicLocation["VertexID$11", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[

BSplineCurveBox[{

DynamicLocation["VertexID$8", Automatic, Center], {0.9683157506909806,

1.7518067137460145`}, {0.9587958878284483,

1.6892499905554539`}, {0.9462794403394051,

1.6272233031740067`}, {0.9307953564896667,

1.5658701080445263`}, {0.9123794481480221,

1.505332303944824}, {0.8910743079598986,

1.4457499038016088`}, {0.86692921083832,

1.3872607108660644`}, {0.8399999999999999,

1.3299999999999994`}, {0.44000000000000017`, 0.53}, {

0.41034895781014025`, 0.47410020480970494`}, {

0.3780446617346518, 0.4196906113511153}, {

0.34316182573295384`, 0.3668970591146875}, {

0.30578112745817854`, 0.3158416499815505}, {

0.2659890216644375, 0.2666424658240717}, {

0.22387754025270534`, 0.2194132954039687}, {

0.17954407941777661`, 0.17426337119960666`},

DynamicLocation["VertexID$1", Automatic, Center]}]]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[

BSplineCurveBox[{

DynamicLocation["VertexID$8", Automatic, Center], {0.820455920582223,

2.1742633711996078`}, {0.7761224597472944,

2.2194132954039696`}, {0.7340109783355622,

2.2666424658240727`}, {0.6942188725418212,

2.315841649981552}, {0.6568381742670462,

2.3668970591146885`}, {0.621955338265348,

2.4196906113511165`}, {0.5896510421898598,

2.474100204809706}, {0.5599999999999998,

2.530000000000001}, {0.15999999999999992`, 3.33}, {

0.1330707891616798, 3.387260710866065}, {

0.10892569204010116`, 3.4457499038016097`}, {

0.0876205518519777, 3.5053323039448254`}, {

0.06920464351033329, 3.5658701080445274`}, {

0.05372055966059475, 3.6272233031740075`}, {

0.04120411217155184, 3.6892499905554548`}, {

0.03168424930901925, 3.751806713746015},

DynamicLocation["VertexID$5", Automatic, Center]}]]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$8", Automatic, Center],

DynamicLocation["VertexID$19", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[

BSplineCurveBox[{

DynamicLocation["VertexID$9", Automatic, Center], {

1.1742633711996073`, 3.179544079417777}, {

1.2194132954039691`, 3.223877540252706}, {

1.2666424658240723`, 3.265989021664438}, {

1.315841649981551, 3.305781127458179}, {

1.366897059114688, 3.3431618257329543`}, {

1.419690611351116, 3.378044661734652}, {

1.4741002048097054`, 3.410348957810141}, {

1.5300000000000005`, 3.440000000000001}, {2.33,

3.8400000000000003`}, {2.387260710866065,

3.8669292108383204`}, {2.4457499038016097`,

3.891074307959899}, {2.505332303944825,

3.9123794481480223`}, {2.5658701080445274`,

3.930795356489667}, {2.6272233031740075`,

3.9462794403394055`}, {2.6892499905554548`,

3.9587958878284484`}, {2.7518067137460154`,

3.968315750690981},

DynamicLocation["VertexID$20", Automatic, Center]}]]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[

BSplineCurveBox[{

DynamicLocation["VertexID$12", Automatic, Center], {

1.8257366288003931`, 0.820455920582223}, {

1.780586704596031, 0.7761224597472944}, {

1.733357534175928, 0.7340109783355622}, {

1.6841583500184492`, 0.6942188725418212}, {

1.633102940885312, 0.6568381742670462}, {

1.5803093886488844`, 0.621955338265348}, {

1.5258997951902948`, 0.5896510421898598}, {

1.4699999999999998`, 0.5599999999999998}, {0.67,

0.15999999999999992`}, {0.612739289133935,

0.1330707891616798}, {0.5542500961983907,

0.10892569204010116`}, {0.4946676960551756,

0.0876205518519777}, {0.43412989195547314`,

0.06920464351033329}, {0.372776696825993,

0.05372055966059475}, {0.31075000944454545`,

0.04120411217155184}, {0.24819328625398523`,

0.03168424930901925},

DynamicLocation["VertexID$1", Automatic, Center]}]]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$12", Automatic, Center],

DynamicLocation["VertexID$9", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$14", Automatic, Center],

DynamicLocation["VertexID$3", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$15", Automatic, Center],

DynamicLocation["VertexID$4", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$17", Automatic, Center],

DynamicLocation["VertexID$14", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$18", Automatic, Center],

DynamicLocation["VertexID$11", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[{

DynamicLocation["VertexID$20", Automatic, Center],

DynamicLocation["VertexID$13", Automatic, Center]}]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False],

StyleBox[{

ArrowBox[

BSplineCurveBox[{

DynamicLocation["VertexID$20", Automatic, Center], {2.825736628800393,

3.8204559205822237`}, {2.7805867045960313`,

3.7761224597472944`}, {2.733357534175928,

3.7340109783355624`}, {2.684158350018449,

3.694218872541821}, {2.6331029408853124`,

3.6568381742670466`}, {2.5803093886488844`,

3.621955338265348}, {2.525899795190295,

3.58965104218986}, {2.4699999999999998`, 3.56}, {

1.6700000000000002`, 3.1599999999999997`}, {

1.6127392891339352`, 3.1330707891616796`}, {

1.5542500961983907`, 3.108925692040101}, {

1.4946676960551755`, 3.0876205518519777`}, {

1.434129891955473, 3.069204643510333}, {

1.372776696825993, 3.0537205596605945`}, {

1.3107500094445454`, 3.0412041121715516`}, {

1.2481932862539853`, 3.031684249309019},

DynamicLocation["VertexID$9", Automatic, Center]}]]},

Directive[

Thickness[Large],

Arrowheads[Medium]], StripOnInput -> False]}}]},

DynamicBox[GraphComputation`NetworkGraphicsBox[

1, Typeset`graph, Typeset`boxes], {

CachedValue :> Typeset`boxes, SingleEvaluation -> True,

SynchronousUpdating -> False, TrackedSymbols :> {}},

ImageSizeCache->{{2.348182378311768,

165.0609365372766}, {-108.78574491682073`,

104.14974491682071`}}]]],

DefaultBaseStyle->{

"NetworkGraphics",

FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]},

FrameTicks->None,

ImageSize->{168.40911891558844`, Automatic}]\);

In[2]:=

In[3]:=

Row[{g, Grid[{

{text["Vertex count: "],

ToString[VertexCount[g]]}, {text["Edge count: "],

ToString[EdgeCount[g]]},

{text["Directed: "],

ToString[DirectedGraphQ[g]]}, {text["Simple: "],

ToString[SimpleGraphQ[g]]}, {text["Weighted: "],

ToString[WeightedGraphQ[g]]}, {text["Acyclic: "],

ToString[AcyclicGraphQ[g]]},

{text["Weakly connected: "],

ToString[ConnectedGraphQ[UndirectedGraph[g]]]},

{text["Strongly connected: "], ToString[ConnectedGraphQ[g]]},

{text["Number of strong components: "],

ToString@Length[ConnectedComponents[g]]},

{text["Number of weak components: "],

ToString@Length[ConnectedComponents[UndirectedGraph@g]]},

{text["Bipartite: "],

ToString[BipartiteGraphQ[g]]}, {text["Eulerian: "],

ToString[EulerianGraphQ[g]]}, {text["Clique number: "],

ToString[Length@FindClique[g][[1]]]},

{text["Matching number: "],

ToString[Length@FindIndependentEdgeSet[g]]},

{text["Edge cover number: "], ToString[Length@FindEdgeCover[g]]},

{text["Size of maximum independent set: "],

ToString[Length@FindIndependentVertexSet[g]]},

{text["Vertex cover number: "],

ToString[Length@FindVertexCover[g]]}}, Alignment -> Left]},

Spacer[20]]

Out[3]=