Chapter 3: Graphs

This chapter was very easy to read, and I would score it about a 7 on a scale from 1-10 on readability. This section defined graphs and outlined some common uses for them. A graph is made up of a collection V of nodes and a collection E of edges, which “joins” two of the nodes. Edges represent a symmetric relationship between their ends. Directed graphs are used for asymmetric relationships and contain a set of nodes V and a set of directed edges E'. Each element n E' is an ordered pair, (u, v). u is the tail of the edge and v is the head of the edge. Edge e' leaves node u and enters node v. If a graph is not directed, it is considered an undirected graph, and it is written as a set of nodes {u, v}.

There countless applications of graphs. The book lists five useful applications of graphs and what they can represent: transportation networks, communication networks, information networks, social networks, and dependency networks.

There are several other terms regarding graphs that were defined in this chapter. A path is a sequence P of nodes where each consecutive pair is joined by an edge in G. A path is simple if all of its vertices are distinct from one another. A cycle is a path where the sequence of nodes “cycles back” to where it began. The sequence of nodes in the path or cycle must respect the directionality of edges. A connected graph is a graph where every pair of nodes u and v has a path from u to v. It is strongly connected if, for every, two nodes u and v, there is a path from u to v and a path from v to u. Furthermore, an undirected graph is considered a tree if it is connected and does not contain a cycle and is the simplest kind of connected graph. Trees can be used to represent a hierarchy.