Graphs!
Graphs aren't new to us. Remember that a graph is a set of vertices, and the edges that connect them. We remember this for two reasons. First, of course, we've been dealing with trees, and trees, as we learned, are just a special form of graph. Second, we did that word graph project last semester. Remember that (fondly)?
In the word graph, every word in the English dictionary had a vertex in the graph, and if the words were exactly one letter apart, then an edge was drawn between them. A portion of that graph is shown below.
This is far from the only thing we'll do with graphs, but it is an example. What are some other graphs? Here's the DC Metro system:
The map of the Metro is a graph where Metro stops are the vertices, and the routes the trains take are the edges.
We could also draw the friendships in a social network as a graph:
Finally, we have a drawing of the proposed ARPANET in the late 1960s:
There are a lot of questions we can ask about these types of relationships: What is a route between Suitland and Foggy Bottom (I think we can agree those are the two silliest Metro station names)? Does Jack know Jill? Does Jack know somebody who knows Jill?
All of these graphs are undirected, which means that the pathways run both ways: people are friends with each other, both words are one letter away from the other. But, they don't have to be. Here is a graphical representation of the lyrics of The Black Eyed Peas' magnum opus "My Humps."
In this graph, vertices have a directed edge between them if the lyrics move from one vertex to the other. "My humps" even has a directed edge to itself, as there is a fair amount of repetition.
Google also represents the internet this way: A directed edge between two pages P1 and P2 exists if P1 links to P2.
Simplistically speaking, Google calculates the probability of ending up at a certain page given random clicks (equating to a random walk around the graph). The higher the probability that you end up on a page, the more influential and important it is.
So those two graphs are directed, but they are all still unweighted. Consider this graph:
In this graph, the edges are weighted by the amount of time it takes to get between different places. If I'm home, and need to go to work, the grocery store, and the gas station, what's the fastest path?
So graph algorithms are really, really important, and we'll be spending some time on them.
Definitions
- Undirected Graph: Graph in which all edges are undirected.
- Directed Graph: Graph in which all edges are directed.
- Mixed Graph: Neither of the above.
- Adjacent Vertices: Vertices connected by an edge.
- Degree: The number of edges connected to a vertex is its degree. If there are \(m\) edges in a graph, \(\sum_{v\in G} deg(v) = 2m\) (because each edge is connected to two vertices).
- In degree and out degree: Number of directed edges coming into or going out of a vertex.
- Path: A sequence of vertices, such that each vertex is adjacent to the vertices preceding and succeeding it.
Representation
There are two different ways to represent a graph. First, you can use an adjacency list. In an adjacency list, a vertex has a list of edges incident to it, and an edge has pointers to the two vertices it connects.
The second is an adjacency matrix. In this, if we have \(n\) vertices, we construct a \(n \times n\) matrix. Each vertex has a row and a column dedicated to it. If location \((i,j)\) is null, no edge connects \(V_i\) and \(V_j\). If an edge does connect those two vertices, location \((i,j)\) will be a pointer to that edge. Alternatively, you could quit on creating Edge objects, and have the matrix be boolean, true if an edge exists, and false otherwise. For a weighted graph, the weight could be stored in that location.