Chapter 3: Graphs

This section will focus, as the title suggests, on graphs and their uses. It will include the basic definitions about graphs and progress into algorithms where graphs “arise naturally”. It will finish off with discussion about connectivity and fundamental graph search techniques.

A graph consists of a collection V of nodes and a collection E of edges that join two nodes. As presented in the book, an edge e that is in E and u, v which are in V, we have V: e = {u, v} where u and v are ends of e. If we want to specify the order of these edges, we can make a directed graph where for each ordered pair (u, v), we will call u the tail and v the head, as the edge e will “leave node u and enter node v.” By default, a graph is undirected. Also, vertex and node are interchangeable.

To provide a deeper definition of graphs, the authors provided the following examples:

1. Transportation Networks: The routes of planes form a graph with the airports as nodes and the edges as the flight.
2. Communication Networks: Computers connected by a network form a graph with computers as nodes and the network forming the edges. These will often be thought of as directed because u cannot always hear v's signal.
3. Information Networks: The internet as websites are nodes and links form edges. This is definitely directed because links to one page usually don't have a link back on the next page.
4. Social Networks: This is easiest to describe with Professor Sprenkle's graph image she presented in class from her Facebook friends connections. Each friend was a node and the connections formed the edges.
5. Dependency Networks: The example given here is with prerequisites for classes offered by a university, with the classes being the nodes and the edges u and v being where u is a prerequisite for v.

A path in an undirected graph is described as a sequence of nodes where each pair of consecutive nodes is joined by an edge. A path is simple if all vertices are distinct. A cycle is a path where the nodes are distinct and the last node is connected to the first. These all apply to a directed graph, except that the direction matters in a directed graph.

Connectivity is apparent in an undirected graph if, for every pair of nodes u and v, there is a path from u to v. In a directed graph, it is strongly connected if there is a path from u to v and path from v to u.

A tree is a graph in which there is no cycle and it is connected. Every n-node tree will have exactly n - 1 edges. Also, if we have G, an undirected graph on n nodes, and any two of the following three statements is true, then so too is the third:

• G is connected.
• G does not contain a cycle.
• G has n - 1 edges.

Overall, this section was a very good overarching definition of graphs and I felt a lot more confident in my knowledge of them after reading it. I would like to see more code of how they are implemented to get a complete understanding of their uses in the real world, though, before I could say that I fully comprehend them. I would give this section an 8/10 for readability, as it was effective in its relating graphs to real world examples while providing through definitions of them.