Chapter 3(Graphs)

As the title suggests, section 3.1 simply outlines the basic definitions that the book will use when discussing graphs.

When we want to keep track of asymmetrical relationships in a graph, we call this a directed graph. Directed graphs keep track of which edges lead to which nodes, but the nodes are not interchangeable. Thus, just because you can go from Node A to Node B, you can not necessarily go from Node B to Node A.

Undirected graphs, by contrast, imply that you can go both directions fro one node to the other. So, if you can move from Node A to Node B, you must always be able to move from Node B back to Node A.

The section then moves to defining connectivity. Connectivity is the property in which every node in a graph has a path to any other node. Thus, the graph cannot have any segment of the graph that is “floating” (i.e. not connected).

The concept of connectivity is important for the last section, which talks about tree structures. Trees are graphs that are fully connected, do not contain a cycle, and have n - 1 edges (n is the number of nodes in the graph). This serves to protect the structure of the tree. By making it be fully connected, we ensure that we can access every datum in the tree. By making sure there are no cycles, and that there are only n - 1 connections, we ensure each datum in the tree only has a parent-child relationship.

Thus, we can then arrange any graph that follows these three requirements into a tree shape.