The assignment below is due BEFORE CLASS on Thursday, October 10th (it is essential that you complete it before class, as we will be doing a class activity building on the assignment).
We are going to play a game creating walking tours of cities with bridges. We begin in the city of King’s Mountain, which is built on four land masses – both shores of a river and two islands in midstream – connected by a total of seven bridges (shown in green).
EXAMPLE 1: Can you create a walking tour of the city that crosses every bridge exactly once? You can begin anywhere you like, and end anywhere you like, as long as you cross each bridge just once.
Background – Graph Theory
We can simplify the picture of King’s Mountain to make it easier to deal with:
The key elements of the map are the four land masses (let’s label them A, B, C, and D) and the seven bridges (p,q,r,s,t,u and v) (thanks to mathisfun.com for the images):
For the purposes of our problem, we can simply think about each land mass as a point (A, B, C, and D), and the bridges as lines connecting the points (p,q,r,s,t,u and v) – like this:
We call this kind of picture a graph – the points are called vertices and the the lines are called edges. Our goal of finding “a walking tour that crosses each bridge once” is now matter of tracing out all the edges without lifting our pencil (and without repeating any edge).
Assignment, Due Thursday 10/10 (beginning of class)
Warm up (This Warm Up is just for practice – you do NOT need to submit your answers – see below for the three-part Assignment to be submitted). The following examples build on the example above.
EXAMPLE 2: If you are given the freedom to build one new bridge in King’s Mountain (“make one new edge in the graph”), can you do it in such a way the walking tour becomes possible? Do it!
EXAMPLE 3: If you are given the freedom to destroy one bridge (“erase one edge”), can you do it in such a way that the walking tour becomes possible? Do it!
EXAMPLE 4: Construct walking tours for each of the following graphs (or decide if it is impossible).
Assignment. Your assignment has 4 parts.
PART 1. For each of the four graphs below (G1 – G4), decide whether it is possible to create a walking tour crossing each bridge exactly once. Post your solutions here (TO POST A SOLUTION, JUST LIST THE POINTS OF YOUR WALKING TOUR IN ORDER). If it is not possible to create a create a solution, say so!
PART 2. Challenge your friends: Now it’s up to you to build your own graph, and challenge your classmates to construct a walking tour (or to determine if it is impossible). It can consist of as many points as you wish, and as many bridges (edges) connecting them. You MUST label your points “A, B, C…” etc. When you’re finished, decide for yourself if a walking tour crossing each bridge exactly once is possible. Remember, the most challenging puzzles are the ones where the answer is difficult to determine. Post two puzzles in the comments. See the note “POSTING YOUR PUZZLE ONLINE” below for instructions on how to draw and share graphs online.
PART 3. Solve a friend’s puzzle. Leave a response to a friend’s posted puzzle, giving a solution. TO POST A SOLUTION, JUST LIST THE POINTS OF YOUR WALKING TOUR IN ORDER.
Example:
Here is a puzzle: http://sketchtoy.com/67467551
Here is a solution: (start at A) – A, B, D, A, E, B, C, E
PART 4. The third part of your assignment is to write a short paragraph (at least 3 sentences) responding to the following prompt. Be sure to respond to each part:
Writing Prompt: Did you enjoy this assignment? Why or why not? Describe a connection between this assignment and our work in the class. (If you don’t believe there is a connection, try to imagine why we are doing this). Leave your response in the comments.
POSTING YOUR PUZZLE ONLINE. I recommend the site sketchtoy.com – it allows you to draw something, then click “SAVE” and get a link to your drawing. You can post the link in a comment, and we’ll be able to click on it and view your drawing. Don’t worry if it’s not pretty! For example, here is a graph that I drew (can you find a walking tour that crosses all edges?): http://sketchtoy.com/67467556
Part 1:
G1: E,G,D,F,G,H,I,A,B,I,C,H,B,C,D,E,F
G2: C,F,B,E,D,C,B,A,F,E
G3: G,F,E,H,D,G,E,D,C,J,B,I,C,B,A,J,I,H,G
G4: No solution
Part 2:
http://sketchtoy.com/69030896
http://sketchtoy.com/69031461
Part 4:
This assignment was very different from our previous assignments. I found it enjoyable as I personally like puzzles, however, not being able to know whether a graph has a solution or not made it difficult. While I am unable to determine a connection between this assignment and the current material we are learning, I imagine it may be related to the counting topic we are currently studying. I am interested to know what the exact connection is.
http://sketchtoy.com/69030896 Your answer is A, D, C, B, A, C, E, F, G, H, E
The solution of( http://sketchtoy.com/69030896) is A(start from A), D,C,B,A,C,E,F,G,H,E
The solution of http://sketchtoy.com/69031461 is A(start from A), O,N,K,I,T,K,L,N,M,O,B,A,C,D,E,F,G,H,I
https://sketchtoy.com/69031461
AONKIJKLNMOBACDEFGHI
Part 1:
G1: E,G,D,F,G,H,I,A,B,I,C,H,B,C,D,E,F
G2: C,F,B,E,D,C,B,A,F,E
G3: G,F,E,H,D,G,E,D,C,J,B,I,C,B,A,J,I,H,G
G4: No solution
Part 2:
http://sketchtoy.com/69037748
http://sketchtoy.com/69037750
Part 3: Ysukraj’s puzzles
A,B,C,A,D,C,E,F,G,H,E
A,O,N,K,I,J,K,L,N,M,O,B,A,C,D,E,F,G,H,I
Part 4: I didn’t like this assignment. It doesn’t seem to have any relevance to what we were doing in class.
The solution of https://sketchtoy.com/69037748 (start at A) A,B,C,A,D,C.
Part1:
G1: F, G, E, F, D, G, H, I, C, H, B, I, A, B, C, D, E
G2: E, D, C, B, A, F, B, E, F, C
G3: G, H, E, G, D, H, I, J, C, I, B, J, A, B, C, D, E, F, G
G4: Not possible
Part 2:
http://sketchtoy.com/69038023
http://sketchtoy.com/69038029
Part 4:
I didn’t enjoy this because I had to try. A connect this has from our class work is that there are a lot of possibilities but not all of them are needed (don’t solve the puzzle). It’s like a counting problem to get the answers (figuring out can two points have the same amount of edges).
For your puzzle Prof. R (http://sketchtoy.com/67467556) the answer is: C, D, A, B, E, A, C, B, D
Part 1:
G1: E,F,D,G,E,D,C,H,B,I,C,B,A,I,H,G,F
G2: E,F,A,B,C,F,B,E,D,C
G3:G,F,E,D,H,E,D,C,I,B,J,C,B,A,J,I,H,G,
G4: no solution
Part 2:
http://sketchtoy.com/69038129
http://sketchtoy.com/69038130
Part 4:
Yes, I enjoy doing this assignment and it is different than other assignments we did before; we are not sharing our opinion or ideas. This assignment is more like a math problem. I cannot directly describe a connection between this assignment and our work in class. I think there is a connection between this assignment and counting.
The solution of http://sketchtoy.com/69038129 (start at A) A,F,G,E,H,I,B,J,F,D,G,H,C,I,J,A.
Part 1:
G1: EGDFGHBICHIABCDEF
G2: EDCFABEFBC
G3: GFEHDGHIBICHIABCDEF
G: No solution? I have no clue lol
part2:
http://sketchtoy.com/69038190
http://sketchtoy.com/69038191
part4:
This assignment was very entertaining for my brain at 12 in the morning. I just woke up from a nap so my brain was nice and fresh to tackle this challenge. I feel like the connection to this assignment and our classwork is based on no repetition when crossing paths and when we made lists in class.