When Euler was young he visited Königsberg and saw seven magnificent bridges. He came up with a game that we investigated in class, can you find a way to cross every bridge only once? We saw that in Königsberg this could not be done, however an interesting note is that in modern day Kaliningrad it can be due to some "remodeling" that took place. In this problem we will get practice with "Euler's Game" on these "cities" and their "bridges"! Below, give the path that uses every edge only once or state why it is impossible.
Graph:
Loading graph...
Graph:
Loading graph...
Loading graph...
When two graphs are "structurally" similar we say they are isomorphic to one another. This means that the two graphs have the same number of vertices and edges, and the edges are connected in the same way. This is done via a labelling argument that models pair-making. In the following sub-problems, investigate whether the two graphs are isomorphic to one another.
Graph 1:
Loading graph...
Graph 2:
Loading graph...
Graph 1:
Loading graph...
Graph 2:
Loading graph...
Graph:
Loading graph...
Connected and disconnected graphs are those that are defined by the ability to express them as a Graph Union or not. Formally, graphs are an ordered pair of sets and to display a graph as disconnected more clearly, we write them in terms of their connected components. Express the following graphs formally as a union of two graphs or as normal.
Example:
Graph:
Loading graph...
Answer:
Graph:
Loading graph...
Graph:
Loading graph...
Graph:
Loading graph...
We saw a number of Graph operations in class that can be used to create new graphs from old ones. In the following problem, you are given a graph and are asked to perform a number of operations on it. Draw the resulting graph.
Graph:
Loading graph...
Perform the following operations on the graph above:
Graph:
Loading graph...
NOTE: Graph G is made up of "a" through "e" and graph L "x" through "z". Perform the following operations on the graph above:
Graph:
Loading graph...
Perform the following operations on the graph above:
Graphs can take on different properties and characteristics that can alter there visual representation. These "special" graphs can be complete, bipartite, tripartite, n-partite, etc. In the following problem you are asked to draw a graph the adheres to the given properties.
Draw
Draw
Draw
Draw a Hamiltonian Graph of order and size 8
Trees and forests are special types of graphs that are cycle free. In the following problem you will be asked to argue in your own words why certain statements are true or false.
There is a tree of order 8 and size 10.
There is a forrest with 3 connected components comprised of the following:
For all trees of order n and size n-1, there is a way to add an edge that leaves the tree acyclic.
Trees are sometimes investigated as the way to span an area minimally (or equivalently, the way to connect all the vertices with the fewest edges). This leads to a very important problem known as the "Minimum Spanning Tree" problem. Describe the problem in your own words and then solve a small example to illustrate your description.
Your repository will contain the following files:
CMSI-2820-HW6/
├── .gitignore
├── README.md
├── cycles.py
├── prim.py
├── kruskal.py
├── boruvka.py
└── test_rangers.py
As a refresher, here is the helper video that goes from complete start to finish for the process of receiving, setting up, and turning in your programming portion of the HW:
As with the other creative endeavors from the previous Optional HW's, integrate your learning into a real world event/experience/memory! (However always remember that you can work out an alternate creative endeavour if you want to involve your hobbies! You can make creative works in any form such as games, drawings, paintings, dioramas, sculptures, videos, fake blogs, memes, anything!) (Just make sure to talk to me first!)
The study of combinatorics, while not defined explicitly, is about counting. Whether its counting permutations, combinations, choices, or anything else, combinatorics is about understanding the large breadth of options before us. In this optional, I would like you to examine the combinatorics of your hobby! Part of what makes our hobbies so engaging and interesting is the number of options to explore. Wether its how many things we can construct, the number of experiences that are possible, or even just how often we can engage with it.
With this in mind, I would like you to find the direct number that represents the number of combinations/permutations for something in your hobby. Just how expressive is that element of your hobby? For instance:
The first example stems from a story driven video game I played about a year ago called Detroit Become Human. This game involves a very complex net of interconnected/branching story lines and decisions to make. The game has such an extensive number of choices that it uses trees to display the possible outcomes of the game. An interesting investigation would be to solve the following problem: Given that I only take "pacifist" actions the entire game, how many choices can be considered "pacifist"? How many different story ending do I still have access to? This optional is fulfilled by providing an explanation of the process I followed to solve this problem. This would include:
The second example is about wardrobes. Do you ever wake up feeling like you "have nothing to wear"? Trying to make "fashionable" outfits for the day is a very complex problem and is very personal! An interesting investigation would be to find the number of outfits I can actually make. By altering, or removing all together, the "fashionable" requirements, how does your number of outfits change? This optional is fulfilled by providing an explanation of completing this investigation. This would include:
You will not be graded on how high of a number you get, but rather the quality of your explanation and the clarity of your process.
Once you have completed your investigation, you can turn it in via brightspace! If you have any questions about this optional feel free to ask me!
This optional project can be submitted until one week after the homework due date.
Here's an example of an editable graph where you can add/remove nodes and edges. Try it out!
Loading graph...
Note: The interactive graph above allows for editing capabilities. You can drag nodes to reposition them, add new nodes by clicking the "+" button, connect nodes by drawing edges, and delete elements. Feel free to use this for your homework problems!
| Component | Points | Description |
|---|---|---|
| Q1 | 10 | Euler's Game and Eulerian paths |
| Q2 | 10 | Graph isomorphism |
| Q3 | 10 | Connected and disconnected graphs |
| Q4 | 10 | Graph operations |
| Q5 | 10 | Special graphs |
| Q6 | 10 | Trees and forests |
| Q7 | 10 | Minimum Spanning Tree problem |
| Programming | 30 | Graph algorithms implementation in Python |
| Optional Section | 20 | Combinatorics investigation in your hobby (Points For S5 Only) |
| Total | 100 |