Figure: A portion of the friendship graph
To demonstrate the importance of proper modeling, let us consider a graph where the vertices are people, and there is an edge between two people if and only if they are friends. This graph is well-defined on any set of people, be they the people in your neighborhood, at your school or place of business, or even the entire world. There are many interesting aspects of people that are best understood as properties of this friendship graph.
We use this opportunity to define important graph theory terminology. ``Talking the talk'' proves to be an important part of ``walking the walk''.
A graph is undirected if edge (x,y) always implies (y,x). Otherwise, the graph is said to be directed. The ``heard-of'' graph is directed, since many famous people who I have heard of have never heard of me! The ``had-sex-with'' graph is presumably undirected, since the critical operation always requires a partner. I'd like to think that the ``friendship'' graph is always an undirected graph.
An edge of the form (x,x) is said to be a loop. If x was y's friend several times over, we can model this relationship using multiedges, multiple edges between the same pair of vertices. A graph is said to be simple if it contains no loops and no multiple edges. Simple graphs really are often simpler to work with in practice. Therefore, we might be better off if no one was their own friend.
A graph is said to be weighted if each edge has an associated numerical attribute. We could model the strength of a friendship by associating each edge with an appropriate number, say from 0 (enemies) to 10 (blood brothers). The edges of a road network graph might be weighted with their length, drive-time, or speed limit, depending upon the application. A graph is said to be unweighted if all edges are assumed to be of equal weight.
A path is a sequence of edges connecting two vertices.
Since Mel Brooks is my father's sister's husband's cousin,
there is a path in the friendship graph between me and him,
shown in Figure 
.
This is true even though the two of us have never met.
If I were trying to impress you with how tight I am with Mel Brooks, I would be much better off saying that my Uncle Lenny grew up with him than to go into the details of how connected I am to Uncle Lenny. Through Uncle Lenny, I have a path of length 2 to Cousin Mel, while the path is of length 4 by blood and marriage. I could make the path even longer by linking in people who know both me and my father, or are friends of Aunt Eve and Uncle Lenny. This multiplicity of paths hints at why finding the shortest path between two nodes is important and instructive, even in non-transportation applications.
The ``six degrees of separation'' theory argues that there is always a short path linking every two people in the world. We say that a graph is connected if there is a path between any two vertices. A directed graph is strongly connected if there is always a directed path between any two vertices.
If a graph is not connected, we call each connected piece a connected
component.
If we envision tribes in remote parts of the world that have yet not been
encountered, each such tribe would form a connected component in the
friendship graph.
A remote hermit, or extremely unpleasant fellow (see Figure )
would represent a connected component of one vertex,
or an isolated vertex.
The degree of a vertex is the number of edges adjacent to it. The most popular person defines the vertex of highest degree in the friendship graph. Remote hermits will be associated with degree-zero vertices. In dense graphs, most vertices have high degree, as opposed to sparse graphs with relatively few edges. In regular graphs, each vertex has exactly the same degree. A regular friendship graph would truly be the ultimate in social-ism.
A social clique is a group of mutual friends who all hang around together. A graph-theoretic clique is a complete subgraph, where each vertex pair has an edge between them. Cliques are the densest possible subgraphs. Within the friendship graph, we would expect to see large cliques corresponding to workplaces, neighborhoods, religious organizations, and schools.
A cycle is a path where the last vertex is adjacent to the first. A cycle in which no vertex repeats (such as 1-2-3-1 verus 1-2-3-2-1) is said to be simple. The shortest cycle in the graph defines the graph's girth, while a simple cycle that passes through every vertex once is said to be a Hamiltonian cycle. An undirected graph with no cycles is said to be a tree if it is connected; otherwise it is a forest. A directed graph with no directed cycles is said to be a DAG, or directed acyclic graph.
