Wolfram Cloud Document

Introduction

I was reading the Wikipedia article about dynamic programming and I stumbled along a complex-looking diagram by User:Dcoatzee.

Image credit: User:Dcoatzee [2] [3]

I decided to write a quick program in Wolfram Language to take advantage of the builtin graph visualization tools.
The program computes the edges recursively, then makes a graph from them.

I should note that the Fibonacci algorithm uses multiple recursion and is defined as:

In[]:=

TraditionalForm[HoldForm[ F[0] == constant ]]TraditionalForm[HoldForm[ F[1] == F[0] + constant ]]TraditionalForm[HoldForm[ F[n] == F[n-1] + F[n-2] ]]

Out[]//TraditionalForm=

F(0)constant

Out[]//TraditionalForm=

F(1)F(0)+constant

Out[]//TraditionalForm=

F(n)F(n-1)+F(n-2)

In[]:=

ClearAll["Global`*"]fibEdges[n_?((#1<0)&)]:={}fibEdges[n_?((#1==0)&)]:={}(*ed[n_?((#1==1)&)]:={10}*)(*ed[n_?((#1>=2)&)]:=Union[{n(n-1)},{n(n-2)},ed[n-1],ed[n-2]]*)fibEdges[n_?((#1==1)&)]:={10}fibEdges[n_?((#1≥2)&)]:=Union[{n(n-1)},{n(n-2)},fibEdges[n-1],fibEdges[n-2]]fibGraph[n_]:=Graph[Table[i-1,{i,1,n+1}],fibEdges[n](*VertexLabels"Name"*)](*Table[ed[i-1],{i,1,9+1}]*)Table[fibGraph[i-1],{i,1,9+1}]

Out[]=





It turned out the pattern was pretty simple: each new edge is connected to the two previous, as should have been obvious by the way the Fibonacci algorithm was designed.
It’s also interesting to look at the graph distance matrix for one of the bigger Fibonacci subproblem dependency graphs. Although I didn’t include a legend, it’s easy to see that the minimum distance from a vertex to itself is 0, to its two closest neighbors is 1, to its two next-closest neighbors is 2, and so on!

In[]:=