CITE THIS NOTEBOOK: Working through exercises in Donald Knuth's Art of Computer Programming by Peter Burbery. Wolfram Community NOV 13 2022.
I decided to work through some exercises in Donald Knuth’s Art of Computer Programming Volume 4A Combinatorial Algorithms Part 1.
https://www.amazon.com/Computer-Programming-Volumes-1-4A-Boxed/dp/0321751043
https://www.amazon.com/Computer-Programming-Volumes-1-4A-Boxed/dp/0321751043
Exercise 41
Exercise 41
For what integers n do we have =? =?
K
n
P
n
K
n
C
n
In[]:=
Table[CompleteGraph[i],{i,9}]
Out[]=
,
,
,
,
,
,
,
,
In[]:=
Table[PathGraph[Range[i]],{i,9}]
Out[]=
,
,
,
,
,
,
,
,
I’ll use the new isomorphism functionality introduced in recent releases of Mathematica:
In[]:=
FindGraphIsomorphism
,
Out[]=
{11}
In[]:=
Names["*Isom*"]
Out[]=
{FindGraphIsomorphism,FindIsomers,FindIsomorphicSubgraph,FindSubgraphIsomorphism,IsomorphicGraphQ,IsomorphicSubgraphQ}
In[]:=
Information/@Names["*Isom*"]
Out[]=
,,,,,
In[]:=
Select[IsomorphicGraphQ[CompleteGraph[#],PathGraph[Range[#]]]&][Range[10]]
Out[]=
{1,2}
In[]:=
Select[IsomorphicGraphQ[CompleteGraph[#],CycleGraph[#]]&][Range[10]]
Out[]=
{3}
Donald Knuth lists 0 as an answer as well in addition to 3, but I don’t think the 0 graph exists or makes sense.
Exercise 43
Exercise 43
Are any of the following graphs the same as the Petersen graph?
I have a hard copy edition of the Art of Computer Programming that I am using to answer this exercise.
In[]:=
GraphData["PetersenGraph"]
Out[]=
Exercise 44
Exercise 44
How many symmetries does Chvàtal’s graph have?
There are 8 symmetries.
Exercise 45
Exercise 45
Find an easy way to 4-color the planar graph (17). Would 3 colors suffice?
The minimum number of colors possible is 4.
I can use a resource function I created to color a graph:
Exercise 46
Exercise 46
The graph data property I am looking for is “Triangulated” or “maximally planar”.
Prove that the diagram partitions the plane into regions that each have exactly three vertices on their boundary. (One of these regions is the set of all points that lie outside the diagram.)
Therefore G has exactly 3n-6 edges.
I think there’s a graph function that does something with a plane.
Select graphs with at least three vertices:
I was running this in 13.2 but I got an error so I had to evaluate it in 13.1.
This is the error in 13.2
This is the evaluation in 13.1
I am going to work on creating a function to make a planar coloring. I used the code from ColorGraphEdges to build a new function ColorPlanarGraphFaces.
Here is an example:
I can compare the number of vertices n with the number of edges which should be 3n-6.
This is true for all graphs.
Exercise 47
Exercise 47
Find the canonical graph:
Find the name of the graph data entry:
Verify the graphs are isomorphic:
The property apices is the list of vertices whose removal renders the graph planar:
Exercise 48
Exercise 48
Complete the proof of Theorem B by showing that the stated procedure never the same color to two adjacent vertices.
Theorem B: A graph is bipartite if and only if it contains no cycle of odd length.
I will use examples to demonstrate a case for this.
I will verify that all bipartite graphs have a chromatic number of two.
I can color the vertices of a random sample of bipartite graphs:
Exercise 49
Exercise 49
Draw diagrams of all the cubic graphs with at most 6 vertices:
Note
Note
A lot of the exercises are hard and involve proofs and higher mathematical thinking as can be seen in my difficulty with the previous problem with holonomic difference root objects and bipartite graphs, so I’m going to skip to the exercises I can use Mathematica on.
Exercise 83
Exercise 83
This is the graph complement of the line graph of the complete graph of 5.
Transform the graph into a simpler form:
I think this is isomorphic to the Petersen graph.
Exercise 84
Exercise 84
Find all known self-complementary graphs:
The book says the answer is true. I originally got this wrong because I compared the graph and its complement with == instead of IsomorphicGraphQ.
Exercise 87
Exercise 87
Is the Petersen graph (a) 3-colorable (b) 3-edge-colorable?
Yes to a, no to b.
Exercise 88
Exercise 88
Find all cycles of wheel graph 7.
Donald Knuth doesn’t give a particular answer for this.
Exercise 91
Exercise 91
The symbol □ represents the Cartesian graph product.
Later on the symbol ⊗ is also used for the conjunction or direct product. I’m not sure if this is implemented in Mathematica or not yet.
I’m going to move onto another exercise because I’m not sure which graph product to use.
Exercise 124
Exercise 124
What is the chromatic number of the Chvàtal graph, Fig. 2(f)?
Color the nodes:
Exercise 129
Exercise 129
Describe the maximal cliques of the 8x8 queen graph (37).
The book says 310 maximal cliques which is different from the answer from GraphData, so I’m confused.
Exercise 130
Exercise 130
How many maximal cliques are in a complete k-partite graph?
I will try FindSequenceFunction.
I looks like a complete graph has just one maximal clique.
Exercise 132
Exercise 132
I tried to finish entering a graph manually and it was taking too much time so I gave up.
There’s a picture of a graph and I’m asked to determine several properties.
I was trying to be careful as I entered the graph into Mathematica not to duplicate an edge, but then I realized that if I duplicated an edge I could just use SimpleGraph to get the underlying graph.
Order
Order
Conclusion
Conclusion
I was able to solve several exercises in TAOCP with Mathematica.