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.

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.

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.

  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

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.

  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.

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:

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)?

Implementing Graph Traversal Using Queues and Stacks In this chapter we discuss how to actually use lists and arrays to represent graphs. To represent a graph you can use either an adjacency matrix or an adjacency list. We implement the search algorithms in O(m+n) time which we refer to as linear. The adjacency matrix lets us check if there is a connection between a given edge in constant time BUT it takes up Θ(n<sup>2<\sup>) space and checking all the edges can take Θ(n) time. The adjacency list is better for more sparse graphs and requires only O(m+n) space.

Queues and Stacks In BFS and DFS it is important how each node is visited and in what order. BFS → Queue = LIFO. DFS → Stack = FIFO.

BFS doesn't matter whether you use a queue or a stack because the algorithm considered the nodes in a layer in any order. BFS can use a queue to process nodes in the way they were first discovered and can do this in O(m+n) time.

DFS uses a stack to implement the algorithm because the algorithm finds the farthest node and then retreats as soon as it has gone as far as it can. The implementation of the algorithm runs in O(m+n) time as well.

This chapter was not as easy to follow in class simply because we were following the algorithms step by step. I'm glad I read after the information was presented in class because it made it easier to understand. Readability 7.