Discussion: Graph Theory

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:

  1. Facebook
  2. The World Wide Web
  3. 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.

rectanlge divided into four regions each colored with a different color. Each region has a vertex, and each vertex is connected by an edge.

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
Post 1:

  • Did you define the edges and vertices of the three given items correctly without looking at a classmates answers?
  • Did you choose two more real-life items to define as a graph with vertices and edges?
  • Are your items unique instead of a copy of a classmate’s posting?
  • Are your graphs explained well?
  • Did you use appropriate terminology?
 10
Post 2:

  • Did you define the edges, vertices, and regions of the two given items correctly without looking at a classmates answers?
  • Did you choose two more real-life items to define as a graph with vertices, edges, and regions?
  • Are your items unique instead of a copy of a classmate’s posting?
  • Are your graphs explained well?
  • Did you use appropriate terminology?
 10