Traceable Graph

Author

Eric W. Weisstein
October 30, 2017

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

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

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

Counts

All == Connected

A057864

1, 1, 2, 5, 18, 91, 734, 10030, 248427, 11482572, 1000231510

Total[Boole[Get[#]]]&/@FileNames["*.m",FileNameJoin[{$GraphDataDirectory,"Nodes","Traceable"}]]

Length/@Table[Select[Graphs[n],TraceableGraphQ],{n,8}]//Timing

Length/@Table[GraphData["Traceable",n],{n,10}]

Disconnected

0

Table[Total[Boole[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","Traceable","Traceable_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[DisconnectedGraphIndices[n]]]]],{n,10}]

Table[Total[Boole[TraceableGraphQ/@Graphs[n][[DisconnectedGraphIndices[n]]]]],{n,8}]//Timing

Table[Length@GraphData[{"Traceable","Disconnected"},n],{n,10}]

Figure

tr=Table[GraphData["Traceable",n],{n,5}]

GraphicsGrid[
Flatten[Partition[#,6,6,{1,1},{}]&/@Map[GraphPlot[path=If[GraphData[#,"V"]==1,{},Sort/@Partition[GraphData[#,"UndirectedHamiltonianPaths"][[1]],2,1]];GraphData[#],EdgeRenderingFunction:>Function[{r,v},{If[MemberQ[path,Sort@v],Orange,Black],Line[r]}],PlotLabel->TextCell[Style[StringReplace[GraphData[#,"Name"],"\[Hyphen]"->"-"],Italic,FontFamily->"Times"],PageWidth->600/6,TextAlignment->Center]]&,tr,{2}],1],Dividers->All,Alignment->Top,ImageSize->600
]

Parametrized classes

Grid m×n×...

Complement@@GraphData/@{"Grid","Traceable"}

Checks

$Version

SystemInformation["Small"]

Graphs.m TraceableQ

?TraceableGraphQ

AppendEdge

Select[GraphData[;;10],TraceableGraphQ[GraphData[#],Method->"AppendEdge"]=!=GraphData[#,"Traceable"]&]//Timing

Select[GraphData[;;15],TraceableGraphQ[GraphData[#],Method->"AppendEdge"]=!=GraphData[#,"Traceable"]&]//Timing

FindHamiltonianPath (===FindHamiltoinanPath directly)

Select[GraphData[;;10],TraceableGraphQ[GraphData[#],Method->"FindHamiltonianPath"]=!=GraphData[#,"Traceable"]&]//Timing

Select[GraphData[;;15],TraceableGraphQ[GraphData[#],Method->"FindHamiltonianPath"]=!=GraphData[#,"Traceable"]&]//Timing

FindHamiltonianPaths

Select[GraphData[;;10],TraceableGraphQ[GraphData[#],Method->"FindHamiltonianPaths"]=!=GraphData[#,"Traceable"]&]//Timing

Select[GraphData[;;15],TraceableGraphQ[GraphData[#],Method->"FindHamiltonianPaths"]=!=GraphData[#,"Traceable"]&]//Timing

FindPath

Select[GraphData[;;10],TraceableGraphQ[GraphData[#],Method->"FindPath"]=!=GraphData[#,"Traceable"]&]//Timing

Select[GraphData[;;15],TraceableGraphQ[GraphData[#],Method->"FindPath"]=!=GraphData[#,"Traceable"]&]//Timing