Euler circuits and trails

Alec Mihailovs

> with(networks):

> isconnected := G -> `if`(nops(components(G))=1, true, false):

> G:=random(12,20):

> draw(G);

[Maple Plot]

> isconnected(G);

true

> iseuler := G -> `if`(isconnected(G) and product(degreeseq(G)[k]-1,k=1..nops(vertices(G))) mod 2 = 1,true,false):

> iseuler(G);

false

> iseuler(complete(5));

true

> fleury:=proc (G) local e, i, k, n, c, s, H, isconnected, iseuler, isbridge; isconnected := G -> `if`(nops(components(G))<=1, true, false); iseuler := G -> `if`(isconnected(G) and product(degreeseq(G)[k]-1,k=1..nops(vertices(G))) mod 2 = 1,true,false);if iseuler(G) then continue else RETURN (print ("The graph does not have an Euler circuit")) fi; n:=nops(edges(G)); if n<=3 then RETURN ([op(vertices(G))]) else continue fi; e:=edges(G)[1]; c:=array(1..n); c[1]:=ends(e,G)[1]; c[2]:=ends(e,G)[2]; H:=G; isbridge:=(v,e,H)->`if`(isconnected(delete(e,duplicate(H))) or isconnected(delete(v,delete(e,duplicate(H)))) ,false,true); for k from 3 to n do H:=delete(e,H); if isconnected(H) then continue else delete(c[k-2],H) fi; s:=incident(c[k-1],H); i:=1; for i from 1 while isbridge(c[k-1],s[i],H) do od;e:=s[i];c[k]:=`if`(c[k-1]=ends(e,H)[1],ends(e,H)[2],ends(e,H)[1]) od; RETURN(print(c)) end:

> fleury(G);

> fleury(complete(3));

[1, 2, 3]

> fleury(complete(11));

vector([6, 7, 9, 6, 8, 7, 10, 6, 11, 8, 10, 11, 7, ...

> fleury(cycle(20));

vector([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...

> fleury(petersen());

> fleury(octahedron());

vector([0, 1, 5, 2, 1, 4, 0, 3, 5, 4, 3, 2])

> draw(octahedron());

[Maple Plot]

> iseulertrail:=proc (v,w,G) local H; H:=duplicate(G);addedge({v,w},H);iseuler(H) end:

> iseulertrail(0,5,octahedron());

false

> iseulertrail(1,2,complete(2));

true

> iseulertrail(1,2,complete(4));

false

> fleurytrail:=proc (v, w, G) local e, i, k, n, c, s, H, isconnected, iseuler, iseulertrail, isbridge; isconnected := G -> `if`(nops(components(G))<=1, true, false); iseuler := G -> `if`(isconnected(G) and product(degreeseq(G)[k]-1,k=1..nops(vertices(G))) mod 2 = 1,true,false); iseulertrail:=proc (v,w,G) local H; H:=duplicate(G);addedge({v,w},H);iseuler(H) end; if iseulertrail(v,w,G) then continue else RETURN (print ("The graph does not have an Euler trail between the given vertices")) fi; n:=nops(edges(G)); if n<=2 then RETURN ([v,w]) else continue fi; e:=incident(v,delete(w,duplicate(G)))[1]; c:=array(1..n); c[1]:=ends(e,G)[1]; c[2]:=ends(e,G)[2]; H:=G; isbridge:=(v,e,H)->`if`(isconnected(delete(e,duplicate(H))) or isconnected(delete(v,delete(e,duplicate(H)))) ,false,true); for k from 3 to n do H:=delete(e,H); if isconnected(H) then continue else delete(c[k-2],H) fi; s:=incident(c[k-1],H); i:=1; for i from 1 while isbridge(c[k-1],s[i],H) do od;e:=s[i];c[k]:=`if`(c[k-1]=ends(e,H)[1],ends(e,H)[2],ends(e,H)[1]) od; RETURN(print(c)) end:

> fleurytrail(1,2,complete(2));

[1, 2]

> ends(e1,octahedron());

{0, 1}

> fleurytrail(op(ends(e1,octahedron())),delete(e1,duplicate(octahedron())));

vector([0, 4, 1, 5, 2, 3, 5, 4, 3, 0, 2])

>