Graphs

Captures pairwise relationship between objects

Definition (Graph)

Graph $G=(V,E)$ where

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

As a shorthand, $n=|V|$, $m=|E|$

A graph is simple if there is at most one edge between two vertices

Basic Definitions

Definition (Path)

A path is 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 jointed by a different edge in $E$.

A path is simple if all nodes are distinct.

Definition (Connected)

An undirected graph is connected if for every pair of nodes $u$ and $v$ there is a bath between $u$ and $v$

Definition (Cycle)

A cycle is a path $v_1,v_2,\dots ,v_k$ in which $v_1=v_k$ and $k\ge 2$

A cycle is simple if all nodes are distinct (except for $v_1$ and $v_k$).

Definition (Tree)

An undirected graph is a tree if it is connected and does not contain a cycle.

Given a tree, you can choose a root node $r$ and orient each edge away from $r$ to model a hierarchical structure

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

Implementations

	Edge List	Adjacency Matrix	Adjacency List
Connectedness	$\Theta (m)$	$\Theta (1)$	$\Theta (\text{degree}(v))$
Adjacency	$\Theta (m)$	$\Theta (n)$	$\Theta (\text{degree}(v))$
Space	$\Theta (m)$	$\Theta (n^2)$	$\Theta (n+m)$

• Edge List
  • Good for particular algorithms
• Adjacency Matrix
  • Good for dense graphs
• Adjacency List
  • Good for sparse graphs

Traversals

Time complexity: $O(n+m)$

Breadth-First Search

Intuition: Explore outward from $s$ is all possible directions, adding nodes one “layer” at a time

Implementation

Take an arbitrary start vertex, mark it as visited, and place it in a queue
while the queue is not empty 
	take a vertex, u out of the queue
	visit u
	for all vertices, v, adjacent to u
		if v has not been visited
			mark v as visited
			insert vertex v into the queue
 

s-t Connectivity Problem

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 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.

Proof: $(⟹)$ Follows from the definition of a path

$(⟸)$ Base Case: $L_1$ has a path of length 1 from $s$ since $L_1$ is neighbors of $s$ Inductive Hypothesis: For any vertex $u\in L_k$, there is a path from $s$ to $u$ of length $k$ Inductive Step: For any vertex $u\in L_{k+1}$, there is an edge to a vertex in $L_k$, so there is a path from $s$ to $u$ of length $k+1$. $\square$

BFS Tree

Definition (Breadth First Search Tree)

A tree formed from a graph by adding only vertices and edges traversed during a BFS

Claim

Let $T$ be a BFS tree of $G=(V,E)$ and let $(x,y)\in E$. Then the levels of $x$ and $y$ differ by at most 1.

Depth-First Search

Intuition: Explores child before sibling until reaching dead and and backtracking until a new path can be traversed

Implementation: Same as breadth first but with a stack instead of a queue

Connected Component

Definition (Connected Component)

All nodes reachable from $s$

Algorithm:

R will constist 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

Theorem

Upon termination, $R$ is the connected component containing $s$.

• BFS = explore order of distance from $s$
• DFS = explore in a different way

Bipartite Graphs

Definition (Bipartite graphs)

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

Applications

• Stable Matching
• Scheduler

Lemma

If a graph $G$ is bipartite, it cannot contain an odd-length cycle.

Proof: Not possible to 2-color an odd-length cycle. $\square$

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:

1. No edge of $G$ joins two nodes of the same layer, and $G$ is bipartite.
2. An edge of $G$ joint two nodes of the same layer, and $G$ contains an odd-length cycle (and hence is not bipartite).

Proof: (1) Suppose no edge joins two nodes in the same layer. By BFS property, each edge joints two nodes in adjacent levels. Bipartition: white nodes on odd levels, blue nodes on even level.

(2) Suppose $(x,y)$ is an edge with $x,y$ in the same level $L_j$ Let $z=\text{lca}(x,y)=$ lowest common ancestor Let $L_i$ be the level containing $z$ Consider cycle that takes edge from $x$ to $y$, then path from $y$ to $z$, then path from $z$ to $x$. Its length is $1+(j-i)+(j-i)=1+2(j-i)$ which is odd $\square$

Corollary

A graph $G$ is bipartite iff it contains no odd-length cycle

Proof: $(⟹)$ The contrapositive of case 2 of the previous lemma

$(⟸)$ TODO $\square$

Directed Graphs

Graphs where an individual edge only goes in one direction

Definition (Strong Component)

A strong component is a maximal subset of mutually reachable nodes

Weighted graphs assigns lengths to edges (an unweighted graph is essentially a weighted graph with every edge having a weight of 1)

Shorted path in a weighted directed graph: Dijkstra’s Algorithm

Types

• Directed (Digraph) vs Undirected
• Weighted vs Unweighted
• Connected vs Unconnected
• Cyclic vs Acyclic
• Dense vs Sparse
  • The density of a graph is the ratio of $|E|$ to $|V{|}^2$
  • We can assume that $|E|$ is
    • $\sim |V{|}^2$ for a dense graph (density ~ 1)
    • $\sim |V|$ for a dense sparse (density ~ 0)
  • Directed Graphs: $0\le |E|\le |V|(|V|-1)$
    • Because every node can be connected to $V-1$ vertices
  • Undirected Graphs: $0\le |E|\le |V|(|V|-1)/2$

Algorithms

• S-T Path Problem
  • Checking if there is a path between two vertices
  • Solutions
    • Do a traversal and start at the first vertex
    • If during the traversal you encounter the other node, there is a path between the two
• Shortest Path
• Spanning Tree
• Cycle Detection
• Topological Sort