Basic Definitions and Applications

In this section, we learn about the basic elements and characteristics of graphs.

A graph consists of V (nodes or vertex) and E (edges) which are represented as a two-eement subset of V: e={u,v}. A directed graph is a specific type of graph that has directed edges and ordered pairs of nodes to represent asymmetric relationships. We use the words tail and head to describe the nodes and to show that they are not interchangeable. We assume that a graph is NOT directed unless it is explicitly specified by saying “directed graph.” The book describes many specify contexts in which graphs are used effectively in the real world. A list of these examples:

• transportation networks
• communication networks
• information networks
• social networks
• dependency networks

An important function of the graph is to be able to traverse it and find all the paths you can travel through the graph and find the connections between different vertices. A path is a sequence, P, of nodes with the property that each consecutive pair is joined by an edge. A simple path is if all of the vertices are distinct and a cycle path is when the path cycles back to where it began. A graph is connected there is a path for every pair of nodes. A directed graph is strongly connected if for every two nodes u and v, there is a path from u to v and from v to u.

Trees

If an undirected graph is connected and non-cyclical, it is a tree. They are the simplest kind of graph!! A tree has a root node and the rest of the nodes hang down from that root. A node is a parent if it has a node that directly follows it and that node is a child. If the node has no children it is called a leaf. An important thing about trees….they show hierarchy.

Theorem

Every n-node tree has exactly n-1 edges

Another Theorem

Let G be an undirected graph on n nodes. Any two of the following statements implies the third.

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

I thought this chapter was overly simple to read after having learned about graphs in most computer science and math classes. That said, I love graphs and think they're interesting and pretty simple to understand. Readability: 10

Graph Connectivity and Graph Traversal

To answer if there is a path between two nodes in a graph is the problem of connectivity or the Maze-Solving Problem. In this chapter we explore the differences and similarities between Breadth-First Search and Depth-First Search.

This search is exploring the nodes outward in all possible directions, layer by layer. Layer L₁ has all nodes that are direct neighbors of S. Layer L_i+1 has all nodes that don't belong to an earlier layer and have an edge to a node and layer L_i. The layer number (j) is the distance exactly from a node in that layer to the target node, s.

Fact
For each i>=1, layer L_i produced by BFS consists of all nodes at a distance exactly j from s. There is a path from s to t iff t appears in some layer.

BFS produces a tree whose root is node s.

Theorem
Let T be a BFS tree, let x and y be nodes in T belonging to layers L_i and L_j respectively, an let (x,y) be an edge of G. Then i and j differ by at most 1.

To explore a connected component we refer to the set R of nodes that are reachable from s.

Algorithm

  R will consist of nodes to which s has a path
  Initially R = {s}
  While there is an edge (u,v) where u ∈ R and v ∉ R
    Add V to R
  Endwhile

Theorem 3.5 The set R produced at the end of the algorithm is precisely the connected component of G containing s.

This method of searching explores a graph by going as deeply as possible and only retreating when necessary.

Algorithm

  DFS(u):
     mark u as "Explored" and add u to R
     For each edge (u,v) incident to u
        If v is not marked "Explored" then
           Recursively invoke DFS(v)
        Endif
     Endfor

BFS is similar in that it builds the connected component containing s and they achieve the same level of efficiency. But DFS visits the same number of nodes in a completely different order. DFS trees have a greater height and are narrower.

Theorem For a given recessive call DFS(u), all nodes that are marked “Explored” between the invocation and end of the this recursive call are descendants of u in T.

with this we can prove:

Theorem 3.7 Let T be a depth first search tree, let x and y be nodes in T, and let (x,y) be an edge of G that is not an edge of T. Then one of x or y is an ancestor of the other.

This chapter was very readable: 9, but I feel like it did not talk about the run-time of the algorithms and the similarities and differences between the two different searches. One question I have is why is adding to the stack O(2m)?