"The study of graphs brings with it a whole bevy of new terms which are important to use precisely:\n\nvertex. Every graph contains zero or more vertices. (These are also sometimes called nodes, concepts, or objects.)\n\nedge. Every graph contains zero or more edges. (These are also sometimes called links, connections, associations, or relationships.) Each edge connects exactly two vertices, unless the edge connects a vertex to itself, which is possible, believe it or not. An edge that connects a vertex to itself is called a loop.\n\npath. A path is a sequence of consecutive edges that takes you from one vertex to the other. In Figure 5.1, there is a path between Washington, DC and John Wilkes Booth (by means of Ford’s Theatre) even though there is no direct edge between the two. By contrast, no path exists between President and Civil War. Don’t confuse the two terms edge and path: the former is a single link between two nodes, while the second can be a whole step-by-step traversal. (A single edge does count as a path, though.)\n\ndirected/undirected. In some graphs, relationships between nodes are inherently bidirectional: if A is linked to B, then B is linked to A, and it doesn’t make sense otherwise. Think of Facebook: friendship always goes both ways. This kind of graph is called an undirected graph, and like the Abraham Lincoln example in Figure 5.1, the edges are shown as straight lines. In other situations, an edge from A to B doesn’t necessarily imply one in the reverse direction as well. In the World Wide Web, for instance, just because webpage A has a link on it to webpage B doesn’t mean the reverse is true (it usually isn’t). In this kind of directed graph, we draw arrowheads on the lines to indicate which way the link goes. It is possible for a pair of vertices to have edges in both directions — Muhammad Ali and Joe Frazier each defeated the other (in separate bouts, of course) — but this is not the norm, and certainly not the rule, with a directed graph.\n\nweighted. Some graphs, in addition to merely containing the presence (or absence) of an edge between each pair of vertices, also have a number on each edge, called the edge’s weight. Depending on the graph, this can indicate the distance, or cost, between vertices. A graph can be both directed and weighted, by the way. If a pair of vertices in such a graph is attached “both ways,” then each of the two edges will have its own weight.\n\nadjacent. If two vertices have an edge between them, they are said to be adjacent.\n\nconnected. The word connected has two meanings: it applies both to pairs of vertices and to entire graphs. We say that two vertices are connected if there is at least one path between them. Each vertex is therefore “reachable” from the other. In Figure 5.1, President and actor are connected, but Ford’s Theatre and Civil War are not. “Connected” is also used to describe entire graphs, if every node can be reached from all others. It’s easy to see that Figure 5.3 is a connected graph, whereas Figure 5.1 is not (because Civil War and Gettysburg are isolated from the other nodes). It’s not always trivial to determine whether a graph is connected, however: imagine a tangled morass of a million vertices, with ten million edges, and having to figure out whether or not every vertex is reachable from every other. (And if that seems unrealistically large, consider Facebook, which has over a billion nodes.)\n\ndegree. A vertex’s degree is simply the number of edges that connect to it. Virginia Beach has degree 2, and Fredericksburg 3. In the case of a directed graph, we sometimes distinguish between the number of incoming arrows a vertex has (called its in-degree) and the number of outgoing arrows (the out-degree). Muhammad Ali had a higher out-degree (3) than in-degree (1) since he won most of the time.\n\ncycle. A cycle is a path that begins and ends at the same vertex. In Figure 5.3, Richmond-to-Virginia Beach-to-Fredericksburg-to-Richmond is a cycle. Any loop is a cycle all by itself. For directed graphs, the entire loop must comprise edges in the “forward” direction: no fair going backwards. In Figure 5.2, Frazier-to-Ali-to-Foreman-to-Frazier is a cycle, as is the simpler Ali-to-Frazier-to-Ali. We’ll also say that a cycle can’t repeat any edges or vertices along the way, so that it can’t go back and forth repeatedly and pointlessly between two adjacent nodes. Some mathematicians call this a simple cycle to distinguish it from the more general cycle, but we’ll just say that no cycles can repeat like this."