Chapter 3

A graph is a structure that represents relationships between two elements. They consists of nodes or vertices V and edges E which join the nodes to one another. An edge can be represented as a two-element subset of V: e = {u,v} where u and v are nodes at either end of e. The edges of some graphs have an order, meaning that the relationship moves in one direction but not the other. The edges in such a graph are represented by and ordered pair (u,v) where u is the head and v is the tail.

Graphs serve as important models for lots of different types of networks. Some examples from the book are listed below:

• Transportation networks with airports as nodes and non-stop flights as edges
• Lan networks with computers as nodes and physical links as edges
• Networks with all the machines using one ISP as nodes and ISPs with peering relationships as edges
• The internet, with webpages as nodes and hyperlinks as edges
• Social networks with people as nodes and relationships between them as edges

Essential to the concept of graphs is the idea of paths and connectivity. A path is a sequence of connected nodes from one vertex to another. A cycle is a special case of a path that occurs when the path begins and ends at the same vertex. An undirected graph is connected if there is a path from every vertex u to v. A directed graph is strongly connected if for every node u and v there is an edge (u,v) and an edge (v,u). The distance of a path is the number of edges in the path. A tree is a special case of a graph that occurs when the undirected graph is connected and there are no cycles. Since there are no cycles in a tree, it is a good way to represent a hierarchy. Additionally, since there are no cycles, each vertex is only connected to its parent and therefore in a tree with n nodes, there are n-1 edges.

This chapter was a breeze to read since it was mostly just term definitions and little uppper-level conceptual analysis.