Graphs: Basic Traversal and Search Techniques

Graphs: Chapter 17

A graph consists of two sets, V and E

G = (V,E)

V is a finite, nonempty set of vertices

E is a set of pairs of vertices called edges

Directed Graphs (digraphs) -- the edges are ordered pairs of Vertices (arrows indicate direction) <u,v>: u is the tail and v is the head of the edge u --> v.

In an undirected graph, the pair of vertices representing any edge is unordered (i.e., (u,v) and (v,u) represent the same edge.)

Sample Graphs:

(a) G₁ and (b) G₂ are undirected

(c) G₃ is directed.

Terms:

Several kinds of undirected graphs are shown

Two vertices u and v in an undirected graph are called adjacent if there is an edge from the first to the second. The edge (u,v) is incident on vertices u and v.

In the undirected graph of panel (a), vertices 1 and 2 are adjacent, as are 3 and 4, but 1 and 4 are not adjacent.

A path is a sequence of distinct vertices, each adjacent to the next. Panel (b) shows a path.

A cycle is a path containing at least three vertices such that the last vertex on the path is adjacent to the first. Panel (c) shows a cycle.

An n-vertex undirected graph with n(n-1)/2 edges is a complete graph. Fig. 17.6

An undirected graph is connected if there is a path from any vertex to any other vertex; panels (a),(b), and (c) show connected graphs, and panel (d) shows a disconnected graph.

Panel (e) shows a connected graph with no cycles. You will notice that this graph is, in fact, a tree, and we take this property as the definition:
A Free Tree is defined as a connected undirected graph with no cycles (acyclic).

Directed Graphs (Digraphs):

Also see text figures

For directed graphs we can make similar definitions.

We require all edges in a path or a cycle to have the same direction, so that following a path or a cycle means always moving in the direction indicated by the arrows.

Such a path (cycle) is called a directed path (cycle). A directed graph is called strongly connected if there is a directed path from any vertex to any other vertex.

The directed graphs in panels (b) and (c) show pairs of vertices with directed edges going both ways between them.

Since directed edges are ordered pairs and the ordered pairs (v,w) and (w,v) are distinct if v != w, such pairs of edges are permissible in directed graphs. Since the corresponding unordered pairs are not distinct, however, in an undirected graph there can be at most one edged connecting a pair of vertices. Similarly, since the vertices on an edge are required to be distinct, there can be no edge from a vertex to itself (self-edges or loops <i,i>). [Although we shall not do so] sometimes these requirements are relaxed to allow multiple edges connecting a pair of vertices and self-loops connecting a vertex to itself. (page 656)

A complete graph on n vertices contains exactly n(n-1) directed edges. Fig. 17.7

Applications and More definitions

A connected component, H, of an undirected graph is a connected subgraph. (In an undirected graph the set C of vertices that are reachable from a vertex i, together with the edges that connect pairs of vertices in C) (figure)
Note: G4 is disconnected but it has two connected components H1 and H2.

(also Fig 17.1(b) as noted on page 693)

A strongly connected component is a subgraph that is strongly connected. (figure) Note here that G3 is not strongly connected, but it has two strongly connected components.

Applications: (see text)

• Path problems
• Spanning trees
• Interpreters

                            APPLICATIONS FOR GRAPHS

Application	Verticies	Edges
Circuit Networks	Points of Connection	Component Wires
Transport Networks	Stations	Routes
Maps	States/Regions	Adjacency Relations (e.g. Graph Coloring)
Program Flow Analysis	Procedures/Modules	Calls

Finding shortest paths, project planning, identification of chemical compounds, statistical mechanics, genetics, linguistics, street maps, interpreters etc.

Graph Implementations

class Graph Page 664.

Consider data structure of implementation: Keep in mind graphs on page 655 (Fig 17.1) for examples

FirstImplementation: Adjacency Matrix

Connected vertices on a graph are ordered pairs in a matrix. (for weighted these are values) Figure 17.9

Notice diagonal. Why?

Positive: easy to visualize

Negative: often sparse, waste time and space

How many edges? Is it connected? time of O(n²)

Figure 17.13 Cost Adjacency Matrices

Second Implementation: Adjacency Lists

For the n rows in the adjacency matrix, make them linked lists. There is one for each vertex in G.

Each node in the linked list has two fields: data and link. The data is the indices of the vertex adjacent to vertex i (in HeadNode). Figure 17.11 Linked Adjacency Lists

(If want a weighted edge, have a third field Figure 17.14)

Positive: easy to visualize

Negative: How many edges? O(n+e)

There are combinations of links and arrays ... and links and links, etc Figure 17.12 Array Adjacency Lists

Summary and more

Elementary Graph Operations

Breath-first search (BFS):

Roughly analogous to level-by-level traversal of an ordered tree. Consider visually (and for trees).

See algorithm and description on page 682. Also see analysis. O(n+e)

Scan for nodes with increasing radius

Also Figure 17.16

Roughly analogous to pre-order traversal of an ordered tree. Consider visually (and for trees).

See algorithm and description on page 687. Also see analysis. O(n+e)

include edges into simple path as long as possible. Back up and try again

Example of both

Connected components:

If G is an undirected graph, then one can determine whether or not a graph is connected by simply making a call to either DFS or BFS and then determining if there is any unvisited vertex.

The set of connected components of a graph can be obtained by making repeated calls to either DFS or BFS on vertices which are not in a connected component yet.

Spanning trees

When the graph G is connected, a depth-first or breath-first search starting at any vertex visits all the vertices in G. In this case the edges of G are partitioned into two sets T (for tree edges) and N (for nontree edges), where T is the set of edges used or traversed during the search and N the set of remaining edges.

The edges in N can be classified as cross edges or back edges

All edges will be either
1. forward edge: edge in T
2. back edge: one end point is an ancestor of other in the tree
3. cross edge: neither of above (for edge (u,v) not in T, u is not an ancestor of v and v is not an ancestor of u)

Any tree consisting solely of edges in G and including all vertices in G is called a spanning tree.Figure 17.3a.

See (DFS and BFS spanning)

Note: If a nontree edge is introduced into any spanning tree, then a cycle is formed. Hence we do not add them and call them back edges or cross edges.

Also see figures Figure 17.20 and Figure 17.21 (BF and DF spanning)

A connected graph and two of its spanning trees Figure 17.4

Some significant properties:

A spanning tree is a minimal subgraph, G', of G such that V(G') = V(G) and G' is connected. (A mimimal subgraph is one with the fewest number of edges.)

Finding minimal subgraphs is a very common type of problem. (e.g., communication networks, traveling salesperson problem)

Some significant properties:

Claim: depth-first spanning trees have no cross edges

A spanning tree is a minimal subgraph, G', of G such that V(G') = V(G) and G' is connected. (A mimimal subgraph is one with the fewest number of edges.)

Finding minimal subgraphs is a very common type of problem. (e.g., communication networks, traveling salesperson problem)

Communications Breakdown Analysis

Figure 6.6 is not biconnected, 6.7 is biconnected

Articulation points are undesirable in graphs that represent communication networks. Why?

A biconnected component of a connected graph G is a biconnected subgraph H of G. By maximal, we mean that no other subgraph that is both biconnected and properly contains H. ( Biconnected components of graph shown in Figure 6.6)

The biconnected components of a connected, undirected graph G can be found by using any depth-first spanning tree of G.

Articulation Points

Let Low(w) = smallest depth first number which can be reached from w using a path containing descendents of w and at most one back edge.
graph 9 with low

Now, someone smart looked at this and made a nice recurrence relation for you:

Mathematically: Low(w) = min{dfn(w), min{Low(x)|x is a child of w}, min{dfn(x)|(w,x) is a back edge} }

See Figure 6.9: (a) has dfn, (b) has DF Spanning tree, Low[1:10] = {1,1,1,1,6,8,6,6,5,4}

Node	1	2	3	4	5	6	7	8	9	10
Low:	1	1	1	1	6	8	6	6	5	4

U is an articulation point iff

1. u is either the root of the spanning tree that has two or more children

2. or u is not the root and u has a child w such that Low(w) > dfn(u).

Node vertex 2 is an articulation point as it has a child 5 such that Low(5) = 6 > 6 = dfn(2)

Node vertex 5 is an articulation point as it has a child 6 such that Low(6) = 8 > 7 = dfn(5)

Consider vertices 1,4,5
Node vertex 4 is not an articulation point since it is possible to reach an ancestor via a child of 4: descendent 3, descendent 2, and a back edge.

Function DFS is easily modified to compute dfn and low for each vertex of a connected graph. (pseudocode)

Once articulation points are determined, biconnected components can be found (pseudocode)