Skip to main content

graphs and networks - House of Santa Claus


The house of Santa Claus is an old German drawing game for small children. You have to draw a house in one line.  You must not lift your pencil while drawing. $\color{red}{\text{You must not repeat a line.}}$


A possible solution for drawing such a house is:


enter image description here


The drawings sequence is here: 1->2->4->1->3->4->5->3->2


How can one find out all existing drawing sequences using Mathematica?


UPDATE:



Each starting position should be possible and the last line should end at the starting position.



Answer



Full solution


Outline of solution


The OP asks for a path which contais all vertices and all egdes but must not go through any egde twice. This kind of path is called Eulerian path (EP). It was first discussed by Leonhard Euler in his famous "Königsberger Brückenproblem".


Euler also proved that for a closed Eulerian path, called Eulerian circle (EC), to exist, all vertices must have an even number of edges (even vertex), and furthermore than an open EP exist if and only if there are exactly two vertices with an odd number of edges (odd vertex), all others must be even. The path then has to start at one of the odd vertices and end on the other.


In our house the two odd vertices are 1 and 2 on the floor of the house.


In order to find all EP we shall use the standard function FindEulerianCycle[]. But as our house has no EC we apply a trick, we add an auxiliary vertex no. 6 which is connected to 1 and 2. Then we let Mathematica calculate the ECs, and finally delete the connections {1,6} and {6,2} from the results.


We find 44 Eulerian paths.


Solution



The undirected edges of the auxiliary graph are


edges = {{1, 6}, {6, 2}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {3, 
   5}, {4, 5}}; (* undirected edges *)

Nor we find all ECs


ec = FindEulerianCycle[edges, All];
Short[%] (* not displayed here *)

Length[ec]


Out[128]= 44

The removal of the two auxiliary edges is easily done here by dropping the first two entries


ep1 = Drop[#, 2] & /@ ec;
Short[%] (* not displayed here *)

In List form this becomes


ep2 = (# /. UndirectedEdge -> List & /@ #) & /@ ep1;
Short[%] (* not displayed here *)


In vertex form the paths are


ep3 = Join[(#[[1]] &) /@ #, {#[[-1, 2]]}] & /@ ep2;
Short[%] (* not displayed here *)

Hence we have found


{Length[ep3], Length[Union[ep3]]}

(* Out[149]= {44, 44} *)

different Eulerian paths.



These can be attributed to one of the the three starting sequences {2->1},{2->3}, and {2->4}:


ep21 = Select[ep3, #[[2]] == 1 &]

(* Out[151]= {
{2, 1, 4, 5, 3, 4, 2, 3, 1}, {2, 1, 4, 5, 3, 2, 4, 3, 1}, 
{2, 1, 4, 3, 5, 4, 2, 3, 1}, {2, 1, 4, 3, 2, 4, 5, 3, 1}, 
{2, 1, 4, 2, 3, 5, 4, 3, 1}, {2, 1, 4, 2, 3, 4, 5, 3, 1}, 
{2, 1, 3, 5, 4, 3, 2, 4, 1}, {2, 1, 3, 5, 4, 2, 3, 4, 1}, 
{2, 1, 3, 4, 5, 3, 2, 4, 1}, {2, 1, 3, 4, 2, 3, 5, 4, 1}, 
{2, 1, 3, 2, 4, 5, 3, 4, 1}, {2, 1, 3, 2, 4, 3, 5, 4, 1}}

*)

Length[ep21]

(* Out[156]= 12 *)

This confirms my previous manual finding.


ep23 = Select[ep3, #[[2]] == 3 &]

(* Out[153]= {

{2, 3, 5, 4, 3, 1, 4, 2, 1}, {2, 3, 5, 4, 3, 1, 2, 4, 1}, 
{2, 3, 5, 4, 2, 1, 4, 3, 1}, {2, 3, 5, 4, 2, 1, 3, 4, 1}, 
{2, 3, 5, 4, 1, 3, 4, 2, 1}, {2, 3, 5, 4, 1, 2, 4, 3, 1}, 
{2, 3, 4, 5, 3, 1, 4, 2, 1}, {2, 3, 4, 5, 3, 1, 2, 4, 1}, 
{2, 3, 4, 2, 1, 4, 5, 3, 1}, {2, 3, 4, 2, 1, 3, 5, 4, 1}, 
{2, 3, 4, 1, 3, 5, 4, 2, 1}, {2, 3, 4, 1, 2, 4, 5, 3, 1}, 
{2, 3, 1, 4, 5, 3, 4, 2, 1}, {2, 3, 1, 4, 3, 5, 4, 2, 1}, 
{2, 3, 1, 2, 4, 5, 3, 4, 1}, {2, 3, 1, 2, 4, 3, 5, 4, 1}}
*)


Length[ep23]

(* Out[154]= 16 *)

ep24 = Select[ep3, #[[2]] == 4 &]

(* Out[152]= {
{2, 4, 5, 3, 4, 1, 3, 2, 1}, {2, 4, 5, 3, 4, 1, 2, 3, 1}, 
{2, 4, 5, 3, 2, 1, 4, 3, 1}, {2, 4, 5, 3, 2, 1, 3, 4, 1}, 
{2, 4, 5, 3, 1, 4, 3, 2, 1}, {2, 4, 5, 3, 1, 2, 3, 4, 1}, 

{2, 4, 3, 5, 4, 1, 3, 2, 1}, {2, 4, 3, 5, 4, 1, 2, 3, 1}, 
{2, 4, 3, 2, 1, 4, 5, 3, 1}, {2, 4, 3, 2, 1, 3, 5, 4, 1}, 
{2, 4, 3, 1, 4, 5, 3, 2, 1}, {2, 4, 3, 1, 2, 3, 5, 4, 1}, 
{2, 4, 1, 3, 5, 4, 3, 2, 1}, {2, 4, 1, 3, 4, 5, 3, 2, 1}, 
{2, 4, 1, 2, 3, 5, 4, 3, 1}, {2, 4, 1, 2, 3, 4, 5, 3, 1}}
*)

Length[ep24]

(* Out[155]= 16 *)


Graphically these are


pnts = {{0, 0}, {1, 0}, {1, 1}, {0, 1}, {1/2, 1 + Sqrt[3]/2}};

GraphicsGrid[
 Partition[Table[
   Show[Graphics[
     Line[Table[{Random[]/5, Random[]/5} + pnts[[ep21[[k, i]]]], {i, 1, 
        9}]]]], {k, 1, Length[ep21]}], 6], ImageSize -> 800]


enter image description here


GraphicsGrid[
 Partition[
  Table[Show[
    Graphics[
     Line[Table[{Random[]/5, Random[]/5} + pnts[[ep23[[k, i]]]], {i, 
        1, 9}]]]], {k, 1, Length[ep23]}], 8], ImageSize -> 800]

enter image description here


GraphicsGrid[

 Partition[
  Table[Show[
    Graphics[
     Line[Table[{Random[]/5, Random[]/5} + pnts[[ep24[[k, i]]]], {i, 
        1, 9}]]]], {k, 1, Length[ep24]}], 8], ImageSize -> 800]

enter image description here


Original solution


I found manually that there are the following 12 tours (sequences of vertices) beginning with 1->2


tv = {{1, 2, 3, 1, 4, 3, 5, 4, 2}, {1, 2, 3, 1, 4, 5, 3, 4, 2}, {1, 2, 3, 4, 

    1, 3, 5, 4, 2}, {1, 2, 3, 4, 5, 3, 1, 4, 2}, {1, 2, 3, 5, 4, 1, 3, 4, 
    2}, {1, 2, 3, 5, 4, 3, 1, 4, 2}, {1, 2, 4, 1, 3, 4, 5, 3, 2}, {1, 2, 4, 1,
     3, 5, 4, 3, 2}, {1, 2, 4, 3, 1, 4, 5, 3, 2}, {1, 2, 4, 3, 5, 4, 1, 3, 
    2}, {1, 2, 4, 5, 3, 1, 4, 3, 2}, {1, 2, 4, 5, 3, 4, 1, 3, 2}};

The evoluton of the drawings can be followed in this picture


pnts = {{0, 0}, {1, 0}, {1, 1}, {0, 1}, {1/2, 1 + Sqrt[3]/2}};
GraphicsGrid[
 Partition[Table[
   Show[Graphics[

     Line[Table[{Random[]/5, Random[]/5} + pnts[[tv[[k, i]]]], {i, 1, 
        9}]]]], {k, 1, 12}], 6], ImageSize -> 800]

enter image description here


Comments

Post a Comment

Popular posts from this blog

front end - keyboard shortcut to invoke Insert new matrix

I frequently need to type in some matrices, and the menu command Insert > Table/Matrix > New... allows matrices with lines drawn between columns and rows, which is very helpful. I would like to make a keyboard shortcut for it, but cannot find the relevant frontend token command (4209405) for it. Since the FullForm[] and InputForm[] of matrices with lines drawn between rows and columns is the same as those without lines, it's hard to do this via 3rd party system-wide text expanders (e.g. autohotkey or atext on mac). How does one assign a keyboard shortcut for the menu item Insert > Table/Matrix > New... , preferably using only mathematica? Thanks! Answer In the MenuSetup.tr (for linux located in the $InstallationDirectory/SystemFiles/FrontEnd/TextResources/X/ directory), I changed the line MenuItem["&New...", "CreateGridBoxDialog"] to read MenuItem["&New...", "CreateGridBoxDialog", MenuKey["m", Modifiers-...
Post a Comment
Read more

How to thread a list

I have data in format data = {{a1, a2}, {b1, b2}, {c1, c2}, {d1, d2}} Tableform: I want to thread it to : tdata = {{{a1, b1}, {a2, b2}}, {{a1, c1}, {a2, c2}}, {{a1, d1}, {a2, d2}}} Tableform: And I would like to do better then pseudofunction[n_] := Transpose[{data2[[1]], data2[[n]]}]; SetAttributes[pseudofunction, Listable]; Range[2, 4] // pseudofunction Here is my benchmark data, where data3 is normal sample of real data. data3 = Drop[ExcelWorkBook[[Column1 ;; Column4]], None, 1]; data2 = {a #, b #, c #, d #} & /@ Range[1, 10^5]; data = RandomReal[{0, 1}, {10^6, 4}]; Here is my benchmark code kptnw[list_] := Transpose[{Table[First@#, {Length@# - 1}], Rest@#}, {3, 1, 2}] &@list kptnw2[list_] := Transpose[{ConstantArray[First@#, Length@# - 1], Rest@#}, {3, 1, 2}] &@list OleksandrR[list_] := Flatten[Outer[List, List@First[list], Rest[list], 1], {{2}, {1, 4}}] paradox2[list_] := Partition[Riffle[list[[1]], #], 2] & /@ Drop[list, 1] RM[list_] := FoldList[Transpose[{First@li...
Post a Comment
Read more

plotting - How to draw lines between specified dots on ListPlot?

I would like to create a plot where I have unconnected dots and some connected. So far, I have figured out how to draw the dots. My code is the following: ListPlot[{{1, 1}, {2, 2}, {3, 3}, {4, 4}, {1, 4}, {2, 5}, {3, 6}, {4, 7}, {1, 7}, {2, 8}, {3, 9}, {4, 10}, {1, 10}, {2, 11}, {3, 12}, {4,13}, {2.5, 7}}, Ticks -> {{1, 2, 3, 4}, None}, AxesStyle -> Thin, TicksStyle -> Directive[Black, Bold, 12], Mesh -> Full] I have thought using ListLinePlot command, but I don't know how to specify to the command to draw only selected lines between the dots. Do have any suggestions/hints on how to do that? Thank you. Answer One possibility would be to use Epilog with Line : ListPlot[ {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {1, 4}, {2, 5}, {3, 6}, {4, 7}, {1, 7}, {2, 8}, {3, 9}, {4, 10}, {1, 10}, {2, 11}, {3, 12}, {4, 13}, {2.5, 7}}, Ticks -> {{1, 2, 3, 4}, None}, AxesStyle -> Thin, TicksStyle -> Directive[Black, Bold, 12], Mesh -> Full, Epilog -> { Line[ ...
Post a Comment
Read more