Weakly Connected Digraph

Author

Eric W. Weisstein
June 3, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/WeaklyConnectedDigraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/WeaklyConnectedDigraph.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Enumeration

Length/@Table[Select[Digraphs[n],ConnectedQ[#,Weak]&],{n,4}]//Timing

Length/@Table[Select[Digraphs[n],ConnectedQ[#,Weak]&],{n,5}]//Timing

Show[GraphicsArray[partition[showGraph[#,Directed,PlotStyles->{PointSize[.1]}]&/@Select[Digraphs[3],ConnectedQ[#,Undirected]&],7]]]

Weakly and Not Strongly Connected Digraphs

<<Utilities`EISFormat`

Length/@Table[Select[Digraphs[n],ConnectedQ[#,Undirected]&&!ConnectedQ[#,Directed]&],{n,4}]

l1={1,2,13,199,9364,1530843,880471142,1792473955306,13026161682466252,341247400399400765678,32522568098548115377595264,11366712907233351006127136886487};l2={1,1,5,83,5048,1047008,705422362,1580348371788,12139024825260556,328160951349343885604,31831080872412589394328804};
n=Min@@(Length/@{l1,l2});
FormatSequence[Take[l1,n]-Take[l2,n],056988,1,
Name->"Number of weakly connected graphs on n nodes that are not strongly connected.",
html["ConnectedDigraph"],
Formula->"A003085(n)-A035512(n)",
Cross->{3085,35512}
]

Show[GraphicsArray[
showGraph[#,Directed,PlotStyles->{PointSize[.1]}]&/@Select[Digraphs[3],ConnectedQ[#,Undirected]&&!ConnectedQ[#,Directed]&]
]]