Chapter 3

Chapter 3 delves into the world of graphs, and this section lays down the framework for more advanced discussion and uses. As defined previously, a graph is a means of encoding relationships between pairs of elements. It does this by tracking vertices, elements, and edges, connections between pairs of elements. Edges typically denote a symmetric relationship, but directed graphs denote one way relationships. Transportation networks, communications networks, information networks, social networks, and dependency networks are given as some example use cases of a graph. A particularly important aspect of a graph is determining paths, where a path is a way to get from one node to another by means of following edges of the graph. From this, we can go into a connected graph, which is a graph where a path exists between any two nodes. Additionally, with paths there is a concept of distance between two nodes, which is defined as the fewest number of edges needed to get from one node to another. Next, trees are discussed. A graph is defined to be a tree if it is connected and without cycles. Trees are often rooted by a specific element and appropriately oriented around it. This is where the idea of child and parent nodes of a tree arise.

These definitions and explanations give us the tools needed to delve into one of the many algorithmic aspects of a graph, that is, traversing. Efficient traversal of a graph allows for a number of important implementations of graphs, which are, presumably, discussed in the next section.

I like graphs as I have studied them previously in math classes, and I even went to a talk on them today. As such, this section earns a whopping 8/10.