Exercise 1 – Model A Real-Life Scenario

Graph theory has powerful applications in modeling real-world scenarios. You are expected to take a single (not both!) of the real-life scenarios, and model it using a graph:

• Case Study 1: Hospital Resource Management
  Context: A city has several hospitals, each with different specialties and resources. During a health crisis, patients need to be directed to hospitals based on the availability of resources and their health needs.

  Your Task: Model this healthcare network to optimize patient distribution and resource allocation.

• Case Study 2: School Course Prerequisites
  Context: In a university, certain courses need to be completed before others can be taken. This prerequisite structure can be complex.

  Your Task: Model the course structure to help students plan their academic journey.

  This will involve several key steps:

  1. Understanding the Context: Carefully read and understand the context of the problem. This understanding is crucial as it will guide your approach to modeling the scenario.

  2. Identifying Components for Graph Modeling:
     • Vertices: Determine what elements in the given scenario should be represented as vertices (or nodes) in your graph. Vertices typically represent entities or points of interest in your problem.

     • Edges: Identify the connections or relationships between these vertices. These will form the edges of your graph.

     • Weights (if applicable): In some cases, the edges of your graph may have weights. These weights can represent various factors such as cost, distance, time, or capacity, depending on the problem context. 
     

     3. Constructing the Graph: Using the identified vertices and edges, construct a graph that accurately represents the given scenario. This graph should be drawn with the aid of computer software (see the exercise “Model Your Own Graph” for information on graphviz).

     4. Analyzing the Graph: Once your graph is constructed, you will analyze it to solve a specific question. This may involve finding the shortest path, determining the most efficient route, analyzing connectivity, or other objectives based on graph theory concepts.

     For instance, in class, we saw how we might use graphs to model a railroad network, with vertices representing cities and edges representing the railroads between them, and weights representing the distance between cities. We then used this graph to find the shortest path between two cities. In this exercise, you will be modeling a real-world scenario of your choice using a graph, and then analyzing it to solve a specific question (of your choosing).
     
     

     Exercise 2 – Model Your Own Graph [ 3pts ]

     Pick any real world instance of a graph and draw it. For instance, here is a graph that represents the states in New England with edges between neighbouring states.
      You do not have to use graphviz, but if you have time and you like exploring software tools, this is an interesting tool since it does offer a ton of flexibility for building a graph.

     You do however, have to use some software for this question. No hand drawn and scanned graphs for this question.

     The only specifications are that your graph needs to have at least 5 vertices, it needs to represent some relationship and needs to be as close to the truth as possible.

     If you are struggling to come up with data, here are some suggestions

     • family tree
     • degrees of separation (look up Bacon number for instance) • results of a knockout tournament
     • facebook friends
     • celebrities following each other on twitter
     • map of the engineering school.
     • your own version of rock paper scissors!
     
     

     Graph Properties

     Exercise 3 – Graph Enumeration [ 3pts ]

     How many graphs can be formed with vertex set {v1, v2, . . . , vn}. The vertices are labeled. On a 4 vertex case, we would actually consider {(1, 2), (3, 4)} to be different from {(1, 4), (2, 3)}.

     This is the solution for simple undirected graphs - no self loops and no parallel edges.
     We do not consider an edge that starts and ends at the same vertex. There is a total of pairs of vertices. For making any graph, we can pick any subset of these edges. For a k element set, we know that we have 2k subsets. Therefore, the number of graphs will be 2(n2).
     
     

     Exercise 4 – Graph Paths and Properties [ 3pts ]

     What is the shortest path from g to d in the graph below? What is the longest path from g to d? Does this graph contain any cycles? If so, provide an example of a cycle.

     The numbers on each edge represent the weight of the edge (it this case, think of it as the distance). Take these weights into account when you talk about the shortest path/longest path.
     
     

     Exercise 5 – Handshake Problem [ 4pts ]

     Sohail and Seema are married. They invite 3 other married couples to a party at their house. Various people shake hands, but of course no one shakes hands with their spouse. At the end of the party, Seema asks everybody else how many hands they shook and receives seven different answers. How many hands did Sohail shake?
     
     

     Exercise 6 – Afterparty Handshakes [ 3pts ]

     Consider a party that has n people in it. During the course of the party people shake hands. Each person keeps track of the number of people they have shaken hands with. At the end of the night every person who has shaken an odd number of hands is invited to an after party (the others are not invited and will not crash this after party).

     Prove that regardless of what n is, there will be an even number of people in the afterparty.
     
     

     Exercise 7 – Comparing Shortest Paths in an Undirected Graph [ 6pts ]

     In graph theory, the shortest path between two vertices can be defined in various ways depending on the criteria used. One common criterion is the number of edges (hop count), and another is the total weight of the path. These two criteria do not always lead to the same path, especially in weighted graphs.

     Your goal is to create an undirected weighted graph where you will demonstrate (with a specific example path) that the shortest path in terms of the number of edges is not necessarily the shortest path when considering the total weight of the edges.

     Guiding Steps:
     1. Construct an Undirected Graph:

     • Create a graph with at least 5 vertices.
     

     • Connecttheseverticeswithedgesinsuchawaythattherearemultiplepathsbetweenatleastonepairofvertices. 2. Assign Weights to Edges:

     • Assign weights to each edge. Ensure that these weights are not uniform and vary significantly.

     • The variation in weights should be such that the shortest path (fewest edges) between two vertices is different from the path with the least total weight.

       3. Identify Vertices for Analysis:
       • Choose a pair of vertices in your graph that have more than one path connecting them.

       4. Analyze Shortest Paths:

     • First, find the shortest path between the chosen pair of vertices based on the number of edges alone. This is often

       referred to as the ”hop count.”

     • Next, find the shortest path between the same pair of vertices based on the total weight of the edges.

     • Clearly show that these paths are different.

       5. Discussion and Conclusion:

     • Discuss why the paths are different and how the weight of edges influences the shortest path in a graph.

     • Reflect on the implications of this in real-world scenarios, such as in network routing, where both distance and traffic (or other factors represented by weights) might influence the chosen path.

       Expected Outcome: You are expected to present a clearly drawn undirected graph with weighted edges, along with an explanation of the two different shortest paths identified. Your discussion should demonstrate an understanding of how different criteria for ”shortest path” can lead to different outcomes in graph theory. This exercise requires to generate an example that will require you to think carefully about the graph.
        

     0. Proofs

        Exercise 8 – Amazon’s Vegan Burgers [ 4pts ]

        Assume Amazon decides to sell frozen garbanzo bean vegan burgers, only in packs of 3 and packs of 10. Prove that you can actually purchase any number n ⩾ 18 of vegan burgers.

        Or from a more mathematical perspective, show that every number greater than or equal to 18 can be written as a × 3 + b × 10 where a and b are non-negative integers.