\[ \newcommand{\set}[1]{\{\, #1 \,\}} \newcommand{\card}[1]{|#1|} \newcommand{\pset}[1]{đť’«(#1)} \newcommand{\falling}[2]{(#1)_{#2}} \]
Problem: City Slickers
Imagine that you are writing a program that needs to model Lower Manhattan and its locations. You have identified that it is important to capture these locations in a graph somehow. For the purposes of this problem, let’s restrict the set of locations under consideration to be: the Guggenheim Museum, Central Park Zoo, the Lincoln Center for the Performing Arts, Rockefeller Center, and the Museum of Natural History.
Brainstorm three different ways that we can represent these locations in a graph. Think broadly about how these locations might be related by viewing them on Google Maps. For each approach, describe what nodes and edges represent in the resulting graph. Draw each graph.
For each of your modeling approaches, which of the following variations are applicable to your graph. If it is applicable, interpret the variation in the context of the relation implied by your graph design. If not, explain why.
- Directedness (in contrast to undirectedness).
- Self-loops.
- Multi-graphs.
Next, consider adding weights to each of your approach. For each approach, come up with a sensible interpretation for edge weights in the resulting graph. Add weights to each of your graph drawings.
A fundamental concept in graph theory is the notion of a path:
Definition (Path): a path in a graph \(G = (V, E)\) is a sequence of vertices \(v_1, \ldots, v_k\) drawn from \(V\) such that there exists edges \((v_1, v_2)\), \((v_2, v_3)\), , \((v_{k-1}, v_k)\) in \(E\).
For each of your approaches, interpret what a path means and give an example of a path.
Finally, a more advanced concept in graph theory is the notion of a connected component.
Definition (Connected Component): a connected component in a graph \(G = (V, E)\) is a subset \(V'\) of \(V\) such that for any two vertices \(v_1, v_2 \in V'\), there exists a path from \(v_1\) to \(v_2\).
For each of your approaches, interpret what a connected component means for your graph, and give an example of a connected component inside the graph.