Notes and Terminology re Graphs
Much of this material is adapted from the excellent Skiena reference in the Annotated Book List under General Reference Links.
A graph G = (V, E) consists of a set of vertices (also called nodes) denoted by V (or V(G)), together with a set of edges (also called arcs or branches) denoted by E (or E(G)). The edges, conceptually and practically, vertex pairs, i.e., pairs of vertices taken from V.
A tree may be viewed as a special kind of graph, or, conversely, a graph may be viewed as a generalization of a tree.
Graphs are very important because of the wide variety of situations they can model, among which are these:
When working with graphs, we are usually not trying to come up with some new graph algorithm, since this is, in general, a very difficult task. What we are often doing instead is trying to cast our problem into some standard graph-theoretic form so that we can take advantage of existing graph algorithms. In that sense it more useful to become familiar with a broad selection of graph algorithmic problems than to understand the details of any particular graph algorithm, although (as usual) we should understand some of the basic ideas. Thus it is helpful to remember that
The friendship graph is the graph consisting of all the individuals (vertices) in some group of people (in the world, in your class, in your building, in your neighborhood, wherever), with an edge between two people if and only if they are friends. We can introduce quite a bit of terminology, and start to get a sense of how to deal with graph structures, by asking, and trying to answer, some questions about this graph.
If I am your friend, does that mean you are my friend? If so, then essentially we agree that x is a friend of y if and only if y is a friend of x. More generally, a graph is undirected if the existence in the graph of the edge (x, y) always implies the existence of the edge (y, x) in the graph as well. Otherwise the graph is said to be directed. A directed graph is also called a digraph. We'd like to think that the "friendship graph" is always undirected, right? Unlike the "heard-of" graph, which is directed since you may have heard of Barack Obama, for example, but he may not have heard of you. Two vertices of a graph that are connected by an edge are said to be adjacent, or neighbors.
Are you your own friend? An edge of the form (x, x) in a graph is called a loop, or a self-loop. It is an edge that connects a vertex to itself. If x is y's friend several times over (i.e., the edge (x, y) appears several times in the graph), then we say that the graph contains multiedges, i.e., multiple edges between the same pair of vertices. A graph is said to be simple if it contains no loops and no multiple edges. That is, in a simple graph each vertex occurs only once. From a practical standpoint, simple graphs are generally simpler to work with. So, life might be simpler if you are not your own friend.
Just how close a friend are you? A graph is said to be weighted if each edge has an associated numerical value. We can model the strength of a friendship by associating each edge with an appropriate number (from 0 for enemies to 10 for blood brothers, for example). A network of roads modeled as a graph might have its edges weighted with the distance between cities, the speed limits, or the drive times, depending on the needs of the application using the model. A graph is said to be unweighted if all edges have no weights, or if all edges are assumed to have the same weight (often simply a weight of 1, for example).
Am I linked by some chain of friends to Nicole Kidman? A path in a graph is a sequence of edges connecting two vertices. The length of the path is the number of edges connecting the two vertices. I think my friend Tim knows a guy named Joe who's married to a girl named Alice whose sister Jane's college roommate lived across the street from Nicole when they were kids.
But how close is my link to Nicole, really? So far, you're probably not too impressed with my "connection" to Nicole. On the other hand, did I mention that my brother is her hairdresser? In a graph there is often a multiplicity of paths between two given vertices, and it is often important to know which of the many paths between two vertices is the shortest path. This idea of a shortest path between two vertices in a graph is often important and instructive, even in applications that have nothing to do with transportation.
Is there a path of friends between every two people in the world? There is a theory called "Six Degrees of Separation" which argues that there is a "path of acquaintanceship" (if not a path of friendship) between any two people in the world that contains no more than six people. In general, we say that a graph is connected if there is a path between any two vertices, and otherwise is disjoint. A complete graph is a connected graph in which each pair of vertices is linked by an edge (or, equivalently, in which any pair of vertices are neighbors). A directed graph is strongly connected if there is always a directed path (a path in which each edge is directed) from any vertex to any other vertex. A directed graph is weakly connected if for any two vertices v1 and v2 there is either a directed path v1 to v2 or a directed path from v2 to v1. A subgraph is any subset of the vertices and edges. If a graph is not connected, we call each connected subgraph a connected component of the graph. A tribe in some remote part of the world that has not yet been encountered by the rest of humanity would be a connected component of the friendship graph. A remote hermit might represent a connected component of one vertex, or an isolated vertex.
Who has the most friends? Who has the fewest friends? The degree of a vertex is the number of vertices adjacent to it. The vertex of highest degree in the friendship graph is, of course, the most popular person. Remote hermits, on the other hand, will be associated with degree-zero vertices. In dense graphs, most vertices have high degree, as opposed to sparse graphs, which have relatively few edges.
What is the largest clique? A social clique is a group of mutual friends who hang out together. A graph-theoretic clique is a complete subgraph, where each vertex pair has an edge between them. A clique is the densest possible subgraph. In the friendship graph we would expect to find large cliques corresponding to workplaces, schools and neighborhoods.
How long will it take my gossip to get back to me? A cycle in a graph is a path in which the last vertex is the same as the first. A simple cycle that passes through every vertex once is said to be a Hamiltonian cycle. A directed graph with no directed cycles is said to be a DAG, which is the acronym for directed acyclic graph. An undirected graph with no cycles is said to be a tree if it is connected, and a forest otherwise.