Example: The “House of Nikolaus”

Deciding whether a graph can be drawn in one line and passing each edge only once is rather easy. One only needs to calculate the rank of each vertex and look whether there are at most two vertices with an odd rank.

Here we are going to determine all possible paths to draw such a figure. As an example we take the popular “House of Nikolaus”. This idea and an implementation can be found in the book of Michael Trott: “Mathematica Guidebook Programming”.

2016 Haus des Nikolaus_1.gif

2016 Haus des Nikolaus_2.gif

Preliminary remarks:

all the possible lines have to start at position A or E, since these are the vertices with an odd degree

The solution is going to be obtained in form of a list: {so far drawn line segements, not drawn line segments}

The line to be drawn next has to begin at the endpoint of the line segments drawn so far.

The lines are to be represented in form of (unoriented) pairs {start,end}.

So we get the line strokes of the house as the following pairs:

2016 Haus des Nikolaus_3.png

2016 Haus des Nikolaus_4.png

Using the pattern {u___,y_,v___} we can use unoriented lines segments in the lists of the drawn and not yet drawn parts (this is really tricky an a good example of pattern matching!)

Now a rule to ad a line to an already drawn segment:

2016 Haus des Nikolaus_5.png

The tricky part here is, that in the triple {y,u,v} , one of the variables u,v is empty, due to the pattern {u___,y_,v___} and the segments not jet drawn are represented in the form: {α,Line,γ}:

Let us look at the following start configuration, i.e. we start with the line {a,d}

2016 Haus des Nikolaus_6.png

Applying the rule at the start configuration we get:

2016 Haus des Nikolaus_7.png

2016 Haus des Nikolaus_8.png

To get all possibilities for the second stroke we use the command ReplaceList, this yields:

2016 Haus des Nikolaus_9.png

2016 Haus des Nikolaus_10.png

We get all the possibilities when repeating this process until all segments are drawn, i.e. we have to repeat seven times (we have eight edges and one drawn as our starting segment., so seven segments remain.

2016 Haus des Nikolaus_11.png

2016 Haus des Nikolaus_12.png

Flattening the result gives a list of possible strokes:

2016 Haus des Nikolaus_13.png

2016 Haus des Nikolaus_14.png

So this are 16 solutions:

2016 Haus des Nikolaus_15.png

2016 Haus des Nikolaus_16.png

Next we calculate all possibilities for the start configuration {a,b}:

2016 Haus des Nikolaus_17.png

2016 Haus des Nikolaus_18.png

2016 Haus des Nikolaus_19.png

2016 Haus des Nikolaus_20.png

2016 Haus des Nikolaus_21.png

2016 Haus des Nikolaus_22.png

For the last start configuration we get again 16 possible solutions:

2016 Haus des Nikolaus_23.png

2016 Haus des Nikolaus_24.png

2016 Haus des Nikolaus_25.png

2016 Haus des Nikolaus_26.png

2016 Haus des Nikolaus_27.png

Making the union of all the intermediate results (to eliminate duplicates) we get 44 (different) solutions

2016 Haus des Nikolaus_28.gif

2016 Haus des Nikolaus_29.png

2016 Haus des Nikolaus_30.gif

2016 Haus des Nikolaus_31.png

2016 Haus des Nikolaus_32.gif

To make the sequence of the strokes more visible we can define the colors in one special order, to be used for every house to be drawn:

2016 Haus des Nikolaus_33.png

2016 Haus des Nikolaus_34.gif

Then we make a slight modification to the drawing function to implement the sequence of colors:

2016 Haus des Nikolaus_35.gif


2016 Haus des Nikolaus_36.png

2016 Haus des Nikolaus_37.gif

Created with the Wolfram Language