Representing Familiar Objects as Graphs
Many things that we commonly interact with can be thought of as a graph. For example in the module, we saw examples of how to define a route through a neighborhood as a graph with the intersections of streets represented as vertices, and the path between intersections represented as edges.
In the first part of this discussion, you will identify the vertices and edges of some familiar objects, then post your ideas to the discussion board. Disagreeing with a classmate is fine, but please be respectful in how you do it.
Define the edges and vertices of the following things:
- The World Wide Web
- A Chess Game
Additionally, present two well-known objects that you think can be represented as a graph, give the vertex and edges.
Maps as Graphs
The set of regions of a map can be represented more abstractly as a graph that has a vertex for each region and an edge for every pair of regions that share a boundary segment. For example in the “map” below there are four distinct regions that are colored. Each region contains a vertex that is connected to the vertex in each adjacent region by an edge. Adjacent regions share boundaries. Lastly, each region is a different color than the regions that share it’s boundaries.
In the next part of this discussion, we will present some situations (maps) that can be modeled abstractly as graphs. Your task is to decide which elements of the situation are edges, which are vertices, and which are regions. You will share your solutions with the class. Use examples as much as you can to support your ideas. If you disagree with a classmate, please be respectful.
The Situations (Maps)
Situation1: You are a teacher and you want to assign students to sit at certain tables in the room. There are some students who are disruptive when they sit together, so you want to make sure they are at different tables. What are the vertices, edges, and regions in this map?
Situation 2: What are the vertices, edges and regions of a sudoku game?
Your Turn: Share two situations that can be modeled as a map.
Follow the grading criteria below to inform your posts.
|Grading Criteria||Points Possible|