6.2 Graphs
Drawing Graphs
Example 1
Here is a portion of a housing development from Missoula, Montana[1]. As part of her job, the development’s lawn inspector has to walk down every street in the development making sure homeowners’ landscaping conforms to the community requirements.
Show solution
Naturally, she wants to minimize the amount of walking she has to do. Is it possible for her to walk down every street in this development without having to do any backtracking? While you might be able to answer that question just by looking at the picture for a while, it would be ideal to be able to answer the question for any picture regardless of its complexity.
To do that, we first need to simplify the picture into a form that is easier to work with. We can do that by drawing a simple line for each street. Where streets intersect, we will place a dot.
This type of simplified picture is called a graph .
Note
Graphs, Vertices, and Edges
A graph consists of a set of dots, called vertices , and a set of edges connecting pairs of vertices.
While we drew our original graph to correspond with the picture we had, there is nothing particularly important about the layout when we analyze a graph. Both of the graphs below are equivalent to the one drawn above since they show the same edge connections between the same vertices as the original graph.
You probably already noticed that we are using the term graph differently than you may have used the term in the past to describe the graph of a mathematical function.
Example 2
th century in the Prussian city of Königsberg, a river ran through the city and seven bridges crossed the forks of the river. The river and the bridges are highlighted in the picture to the right[2].
As a weekend amusement, townsfolk would see if they could find a route that would take them across every bridge once and return them to where they started.
Show solution
Leonard Euler (pronounced OY-lur), one of the most prolific mathematicians ever, looked at this problem in 1735, laying the foundation for graph theory as a field in mathematics. To analyze this problem, Euler introduced edges representing the bridges:
Since the size of each land mass it is not relevant to the question of bridge crossings, each can be shrunk down to a vertex representing the location:
Notice that in this graph there are two edges connecting the north bank and island, corresponding to the two bridges in the original drawing. Depending upon the interpretation of edges and vertices appropriate to a scenario, it is entirely possible and reasonable to have more than one edge connecting two vertices.
While we haven’t answered the actual question yet of whether or not there is a route which crosses every bridge once and returns to the starting location, the graph provides the foundation for exploring this question.
Definitions
While we loosely defined some terminology earlier, we now will try to be more specific.
Note
Vertex
A vertex is a dot in the graph that could represent an intersection of streets, a land mass, or a general location, like “work” or “school”. Vertices are often connected by edges. Note that vertices only occur when a dot is explicitly placed, not whenever two edges cross. Imagine a freeway overpass – the freeway and side street cross, but it is not possible to change from the side street to the freeway at that point, so there is no intersection and no vertex would be placed.
Note
Edges
Edges connect pairs of vertices. An edge can represent a physical connection between locations, like a street, or simply that a route connecting the two locations exists, like an airline flight.
Note
Adjacency Table
An alternate way to represent a graph is with an adjacency table . This lists the vertices on the row and column headers of a table, and has a value in each cell if the vertices are connected with an edge. Later the value might represent something like the length or cost of the edge, but for now we will just put a 1 where there is an edge.
For example, this graph
could be represented with the adjacency table
Note
Loop
A loop is a special type of edge that connects a vertex to itself. Loops are not used much in street network graphs.
Note
Degree of a vertex
The degree of a vertex is the number of edges meeting at that vertex. It is possible for a vertex to have a degree of zero or larger.
Note
Path
A path is a sequence of vertices using the edges. Usually we are interested in a path between two vertices. For example, a path from vertex A to vertex M is shown below. It is one of many possible paths in this graph.
Note
Circuit
A circuit is a path that begins and ends at the same vertex. A circuit starting and ending at vertex A is shown below.
Note
Connected
A graph is connected if there is a path from any vertex to any other vertex. Every graph drawn so far has been connected. The graph below is disconnected ; there is no way to get from the vertices on the left to the vertices on the right.
Note
Weights
Depending upon the problem being solved, sometimes weights are assigned to the edges. The weights could represent the distance between two locations, the travel time, or the travel cost. It is important to note that the distance between vertices in a graph does not necessarily correspond to the weight of an edge.
Your Turn
Try it Now 1
The graph below shows 5 cities. The weights on the edges represent the airfare for a one-way flight between the cities.
# Ch 6.2 - a graph is nothing but a dict: vertex -> {neighbour: weight}.
# This is the book's 5-city air-fare graph (Try it Now 1).
G = {
"Seattle": {"Dallas": 120, "Atlanta": 140, "Chicago": 145, "LA": 70},
"Dallas": {"Seattle": 120, "Atlanta": 85, "Chicago": 165, "LA": 150},
"Atlanta": {"Seattle": 140, "Dallas": 85, "Chicago": 75, "LA": 170},
"Chicago": {"Seattle": 145, "Dallas": 165, "Atlanta": 75, "LA": 100},
"LA": {"Seattle": 70, "Dallas": 150, "Atlanta": 170, "Chicago": 100},
}
# TRY IT: cut the cheap flight - delete "LA": 70 from Seattle AND "Seattle": 70
# from LA, then re-run and watch the degree of LA and the circuit cost change.
names = list(G)
print("Adjacency table (one-way air fare)")
print(" " * 9 + "".join(f"{c:>9}" for c in names))
for row in names:
cells = "".join(f"{('$' + str(G[row][c])) if c in G[row] else '*':>9}" for c in names)
print(f"{row:<9}{cells}")
edges = {frozenset((u, v)) for u in G for v in G[u]}
print(f"\n{len(G)} vertices, {len(edges)} edges")
for v in names:
print(f" degree({v}) = {len(G[v])}")
def connected(g):
seen, stack = set(), [next(iter(g))]
while stack:
v = stack.pop()
if v in seen:
continue
seen.add(v)
stack += [w for w in g[v] if w not in seen]
return len(seen) == len(g)
print(f"connected? {connected(G)}")
def classify(seq):
for a, b in zip(seq, seq[1:]):
if b not in G[a]:
return f"{' - '.join(seq)}: not even a path, there is no edge {a}-{b}"
total = sum(G[a][b] for a, b in zip(seq, seq[1:]))
kind = "CIRCUIT" if seq[0] == seq[-1] else "path"
return f"{' - '.join(seq)}: {kind}, total fare ${total}"
print()
for trip in (["Seattle", "Dallas", "Atlanta"],
["LA", "Chicago", "Dallas", "LA"],
["Seattle", "Atlanta", "LA", "Chicago", "Dallas", "Seattle"]):
print(classify(trip))How many vertices and edges does the graph have? Is the graph connected? What is the degree of the vertex representing LA? If you fly from Seattle to Dallas to Atlanta, is that a path or a circuit? If you fly from LA to Chicago to Dallas to LA, is that a path or a circuit? Adjacency Table
Answer
a. 5 vertices, 10 edges
b. Yes, it is connected
c. The vertex is degree 4
d. A path
e. A circuit
[1] Sam Beebe. http://www.flickr.com/photos/sbeebe/2850476641/ , CC-BY
[2] Bogdan Giuşcă. http://en.Wikipedia.org/wiki/File:Ko...rg_bridges.png
Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0 .
