Where I Draw The Line Meme

Remember this shape? I bet you could tell me the reply without me asking the question. Most of us solved this puzzle million times when we were at primary school.

Let me ask the question once again: how tin can you describe this shape without tracing the aforementioned line twice and without taking the pencil off the newspaper?

I volition talk nigh the mathematical approach to this problem in this postal service, which includes graph theory (so it would be very dainty if you lot go and read the nuts of graph theory before continuing, although it is not that necessary since I assume you will understand the general concept).

For this shape, you probably memorized the answer by doing it then many times. You know where to start and where to stop. However, suppose you come across a shape similar this:

main-qimg-29f049440bad4571da709d94211bcaf3 — Shape 2

Now we accept to alter our question a little: can y'all draw this?

Nosotros can convert the shape into a graph by assigning vertices to intersections and assigning edges to the lines betwixt the vertices. Allow's try this with our popular shape:

envelope

(There are ten edges in this graph: 1-ii, 1-3, 2-3, 2-4, two-v, 3-iv, three-vi, 4-5, 4-half dozen and 5-6.)

Now we are looking for a path (or a cycle) in the graph that visits every edge exactly once. This problem was solved by the famous mathematician Euler in 1736 and is considered to be the outset of the graph theory. The problem is ofttimes referred as an Euler path or Euler circuit problem. An Euler path starts and ends at different vertices, whereas an Euler excursion starts and ends at the same vertex.

For an Euler path P, for every vertex v other than the endpoints, the path enters v the same number of times information technology leaves v (what goes in must come out). Then, there should exist twice this number of edges having 5 as an endpoint (attempt to visualize this: -*-, where asterisk is a vertex which has one archway = i exit, and to which one times two edges are continued). Therefore, every five should accept an even degree (even number of edges should exist continued to 5).

At present suppose P starts at vertex p and ends at vertex q. And then P should get out p one more time than information technology enters, and enter q one more time than it leaves. This makes degrees of p and q even caste minus 1, therefore, the endpoints of P should have odd degrees (odd number edges should be connected to five).

Then the determination for P is this:

"If a graph has an Euler path, and so it must take exactly ii odd vertices."

For an Euler circuit C, the starting bespeak must be the aforementioned with the endpoint, and so C enters the endpoint the aforementioned number of times it leaves it, which makes it a vertex of even degree.

And then the conclusion for C is this:

"If a graph has an Euler circuit, so all of its vertices must exist even vertices."

Let's use these on our examples. In shape ane, vertices i, 2, 3 and 4 all have even degrees of two, four, four and iv, respectively. Vertices 5 and half-dozen both have odd degrees of three. Then, this graph has at to the lowest degree one Euler path only it does non have whatever Euler circuit. In shape two, at that place are four vertices of odd degree and i vertex of even caste, and so it does non have any Euler path or Euler circuit.

Question: Is it possible for a graph to have both an Euler path and an Euler circuit?
Answer: No. (I think you lot can effigy this out by yourself. I trust you!)

Now nosotros have to focus on our main question: if a path/circuit exists, how do we find it?

For small graphs, you could try every possibility, of course, but in real life applications in that location will surely be graphs with thousands or millions of vertices and trial-and-mistake method will accept so much fourth dimension even with a computer program.

A systematic approach would be Fleury'south Algorithm. In this algorithm, our motto is this one-time proverb: Don't burn your bridges behind you (it besides exists in Turkish: Gectigin kopruleri yakma. I like the English version ameliorate though). In graph theory, bridge is the merely edge which connects 2 separate sections of the graph. Removing this edge from the graph would make information technology disconnected.

Bridges_800

To notice an Euler path/circuit in a graph:

Brand sure it has one.
If y'all are looking for an Euler path, start from any odd vertex. Else, start from any vertex.
A non-bridge ALWAYS has priority over a bridge. ALWAYS Choose THE NON-Span.
Delete the edge that you have traversed.
If you do non have any edges left, stop.

Let's see an instance (I am ever taking the images from the other sites in this mail service but I will get-go with a unlike vertex, I hope).

In this graph, vertices A, B, C, D, East and F are all fifty-fifty, then we will find an Euler circuit. We could offset with whatsoever vertex, say B. (1) Then nosotros would continue over again with whatever one of them, say A. From A, there is no bridge so we can safely (2) travel to D. Then from D, we would either (3) travel to F or C (say C) BUT DEFINITELY NOT B since we would go stuck at B, nosotros would fire the span (…ne gemiler yaktim). And so nosotros could proceed with (4) A or Eastward (say A) (not F!), and so with (v) E, then (6) C, (7) F, (8) D, (9) B, and since at that place is no edge left we would finally terminate.

(Notice that we started and ended with vertex B, as we were supposed to do.)

If nosotros get back to shape 1, it does not matter if you start from v or 6 since the solutions are mirror images of each other. There are 44 possible solutions if you start from vertex five and at that place are only 10 ways to lose.

HausVomNikolaus.svg.png — Means to win this game (Do not forget to saydas ist das Haus vom Ni-ko-laus while trying these at abode!)

Since there are so many solutions to this, let's see an example of a failure. If we follow the path six-v-4-iii-half-dozen-4-2 and delete all the edges that nosotros travel, the final graph would look like this:

envelope

If we continue with vertex five, which is a bridge, we would become stuck in that location, and then we would take to elevator our pencil to draw this shape.

I hope you are not bored nonetheless. If you lot are, though, here is a small exercise for you lot. The question is this: can yous draw the shape beneath without tracing the aforementioned line twice and without taking the pencil off the paper?

path