# Study Properties of a Directed Graph

Mathematica 8 provides a broad range of functions for computing properties of directed graphs.
 In[1]:= Xg = \!\(\* 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]:= Xtext[s_] := Style[s, 11, FontFamily -> "Verdana"]
 In[3]:= XRow[{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]=