Undirected Graphs

Notation: $G = (V, E)$ where

• $V$ = nodes (or vertices)
• $E$ = edges (or arcs) between pairs of nodes

Captures the pairwise relationship between objects Graph size parameters: $n = |V|$, $m = |E|$

Example: communcation, circuit, mechanical, financial, transportation...

Graph Representation

Adjacency matrix is a n-by-n matrix with $A_{uv} = 1$ if $(u,v)$ is an edge.

• two representations of each edge
• space proportional to $n^2$.
• Checking if $(u,v)$ is an edge takes $\Theta(1)$ time.
• identifying all edges takes $\Theta(n^2)$ time.

Adjacency Lists is a node-indexed array of lists.

• two representations of each edge.
• space is $\Theta(M=n)$.
• Check if $(u,v)$ is an edge takes $O(degree(u))$ (degree = neighbors)
• Identifying all edges takes $\Theta(m+n)$ time.

Paths, Connectivity, Cycles, and Trees

Definitions for paths and connectivity

• A path in an undirected graph $G=(V,E)$ is a sequence of nodes $v_1,v_2,\dots,v_k$ with the property that each consecutive pair $v_{i-1}, v_i$ is joined by a different edge in E.
• A path is simple if all the nodes are distinct
• An undirected graph is connected if for every pair of nodes $u$ and $v$, there is a path between $u$ and $v$.

Definitions for cycles:

• A cycle is a path $v_1,v_2,\dots,v_k$ in which $v_1=v_k$ and $k\geq2$
• A cycle is simple if all nodes are distinct (except for $v_1$ and $v_k$).

Definition for trees

• An undirected graph is a tree if it is (1) connected and (2) does not contain a cycle.
• Theorem: Let $G$ be an undirected graph on $n$ nodes. Any two of the following statements imply the third: $G$ is connected, $G$ does not contain a cycle, $G$ has $n-1$ edges.

Rooted trees: given a tree $T$, choose a root node $r$ and orient each edge away from $r$. This models a hierarchical structure.

Graph Connectivity and Traversal

Connectivity

s-t connectivity problem: given two nodes $s$ and $t$, is there a path between $s$ and $t$?

s-t shortest path problem: given two nodes $s$ and $t$, what is the length of a shortest path between $s$ and $t$?

Applications: friendster, maze traversal, kevin bacon number, fewest hops in a communcation network

Breadth-first Search

BFS intuition is to explore outward from $s$ in all possibel directions, adding nodes one "layer" at a time.

The algorithm:

• $L_0={s}$
• $L_1 =$ all neighbors of $L_0$
• $L_2 =$ all nodes that do not belong to $L_0$ or $L_1$, and that have an edge to a node in $L_1$.
• $L_{i+1}=$ all nodes that do not belong to an earlier layer, and that have an edge to a node in $L_i$.

Theorem: For each $i$, $L_i$ consists of all nodes at distance exactly $i$ from $s$. There is a path from $s$ to $t$ iff $t$ appears in some layer.

Property: let $T$ be a BFS tree of $G=(V,E)$, and let $(x,y)$ be an edge of $G$. Then, the levels of $x$ and $y$ differ by at most 1.

The above implementation of BFS runs in $O(m+n)$ time if the graph is given by its adjacency representation. Proof:

• Easy to prove $O(n^2)$ time:
  • at most $n$ lists $L[i]$
  • each node occurs on at most one list; for loop runs $\leq n$ times
  • when we consider node $u$, there are $\leq n$ incident edges $(u,v)$, and we spend $O(1)$ processing each edge.
• Actually runs in $O(m+n)$ time:
  • when we consider node $u$, there are $degree(u)$ incident edges $(u,v)$
  • total time processing edges is $\sum_{u \in V} degree(u) = 2m$. Each edge $(u,v)$ is counted exactly twice in sum, once in degree(u) and once in degree (v).

Use cases:

• Connected component: find all nodes 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 in R and v not in R,
	Add v to R
Endwhile

Theorem: Upon termination, R is the connected component containing s.

• Flood fill: given a lime green pixel in an image, change color of entire blob of nieghboring lime pixels to blue. Node=pixel, edge=two neighboring lime pixels, blob=connected component of lime pixels.

BFS is used to explore in order of distance from s DFS is to explore in a different way.

Depth First Search

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

Bartiteness

An undirected graph $G=(V,E)$ is bipartite if the node can be colored blue or white such that every edge has one white and one blue end (if it is possible)

Applications:

• stable matching where med-school residents are one color and hospitals are white
• scheduling: machine are blue and jobs are white.

Many graph probelms become easier if the underlying graph is bipartite (matching). Or, tractable if the underlying graph is bipartite (independent set).

Lemma: if a graph $G$ is bipartite, it cannot contain an odd-length cycle. Proof: it is not possibel to 2-color the odd-length cycle.

Lemma: Let $G$ be a connected graph, and let $L_0,\dots, L_k$ be the layers produced by BFS starting at node $s$. Exactly one of the following holds:

• (i) no edge of $G$ joins two nodes of the same layer, and $G$ is bipartite
• (ii) no edge of $G$ joins two nodes of the same layer, and $G$ contains an odd-length cycle (and hence is not bipartite).

Proof of (i):

• suppose no edge joins two nodes in the same layer.
• by BFS property, each edge joins two nodes in adjacent levels
• bipartition: white = nodes on odd levels, blue = nodes on even levels.

Proof of (ii):

• suppose $(x,y)$ is an edge with $x,y$ in same level $L_j$.
• let $z = lca(x,y)$ = lowest common ancestor
• let $L_i$ be level containing $z$.
• consider cycle that takes edge from $x$ to $y$, then path from $y$ to $z$, then path from $z to x$ exists.
• the length is $1$ (x,y) $+ (j-i)$ (path from y to z) $+ (j-i)$ (path from z to x) which is odd.

Collorary: a graph $G$ is bipartite iff it contains no odd-length cycle.

Connectivity in Directed Graphs

$G=(V,E)$

• edge $(u,v)$ leaves node $u$ and enters node $v$.
• e.g., web graph: hyperlink points from one page to another. the orientation of edges is crucial. modern web search engines exploit hyperlink strucutre to rank web pages by importance.

Examples

• Web graph: node = webpage, edge=hyperlink from one page to another (orientation is crucial), modern search engine exploit hyperlink structure to rank web pages by importance.
• Road network: node-intersection; edge = one-way street
• Political pblogosphere graph: node = political blog; edge = link
• Ecological food web: node = species, edge= from prey to predator

In a graph search

• directed reachability: give a node $s$, find all nodes reachable from $s$.
• directed s -> t shortest path problem: given two nodes $s$ and $t$, what is the length of the shortest path from $s$ to $t$.
• graph search: bfs extends naturally to direted graphs
• web crawler: start from web page $s$. Frind all the web pages linked from $s$, either directly or indirectly.

Nodes $u$ and $v$ are mutually reachable if there is both a path from $u$ to $v$ and also a path from $v$ to $u$.

Strong connectivity: a graph is strongly connected if every pair of nodes is mutually reachable.

Lemma: let $s$ by any node. $G$ is strongly connected iff every node is reachable from $s$, and $s$ is rechable from every node. The proof is as follows:

• => follows from definition
• <= path from u to v: concatenate $u\leadsto s$ path with $s\leadsto v$ path. Path from $v$ to $u$: concatenate $v\leadsto s$ path with $s \leadsto u$ path (or if paths overlap)/

Theorem: can determine $G$ is strongly connected in $O(m+n)$ time. Proof is as follows:

• pick any node in $s$
• run BFS from $s$ in $G$
• run BFS from $s$ in $G^{reverse}$ (reverse orientation of every edge of $G$).
• return true iff all nodes reached in both BFS executions
• correctness follows immediately from previous lemma.

A strong component is a maximal subset of mutually reachable nodes.

Theorem: you can find all strong components in $O(m+n)$ time.

DAGs and Topological Ordering

A DAG is a directed graph that contains no directed cycles

A topological order of a directed graph $G=(V,E)$ is an ordering of its nodes as $v_1, v_2, \cdots, v_n$ so that for every edge $(v_i,v_j)$ we have $i < j$.

Precedence constraints: edge $(v_i, v_j)$ means task $v_i$ must occur before $v_j$. Applications:

• application prerequuisite graph: course $v_i$ must be taken before $v_j$
• compilation: module $v_i$ must be compiled before $v_j$
• pipeline of computing jobs: output of job $v_j$ needed to determine input of job $v_j$

If $G$ has a topolgical order, then $G$ is a DAG. Proof by contradiction:

• suppose that $G$ has a topological order $v_1, v_2, \cdots, v_n$ and that $G$ also has a directed cycle $C$
• Let $v_i$ be the lowest-indexed node in $C$, and let $v_j$ be the node just before $v_i$; thus $(v_i, v_j)$ is an edge
• By our choice of $i$, we have that $i<j$
• On the other hand, since $(v_i, v_j)$ is an edge and $v_1, v_2, \cdots, v_n$ is a topogical order, we must have $j < i$, a contradiction.

If $G$ is a DAG, then $G$ has a node with no entering edges. Proof:

• Suppose that $G$ has a DAG and every node has at least one entering edge. Let's see what happens.
• Pick any node $v$, and begin following edges backwards from $v$. Since $v$ has at least one entering edge $(u,v)$ we can walk backward to $u$.
• Then, since $u$ has at least one entering edge $(x,u)$, we can walk backward to $x$
• Repeat until we visit a node, say $w$, twice.
• Let $C$ denote the sequence of nodes encountered between successive visits to $w$. $C$ is a cycle.

Lemma: if $G$ is a DAG, then $G$ has a topological ordering. Proof by induction on $n$:

• Base case: true if $n=1$.
• Given DAG on $n>1$ nodes, find a node $v$ with no entering edges.
• $G - {v}$ is a DAG, since deleting $v$ cannot create cycles.
• By induction hypothesis, $G-{v}$ has a topological ordering.
• Place $v$ first in topological ordering; then append nodes of $G-{v}$ in topological order. This is valid since $v$ has no entering edges, hence it is a topological ordering.

to compute a topogical ordering of G:
find a node v with no incoming edge and order it first 
Delete v from G
Recursively compute a topologial ordering of G - {v} and append this order after v. 

Theorem: algorithm finds a topological order in $O(m+n)$ time. Proof:

• maintain the following information: $count(w)$ = remaining number of incoming edges, $S$ = set of remaining nodes with no incoming edges.
• initialization: $O(m+n)$ via single scan through graph.
• Update: delete $v$: remove $v$ from $S$, decrement $count(w)$ hits $0$, this is $O(1)$ per edge. 3