算法 | 图 - Graph

Graph

Basic Definitions and Applications

Undirected Graphs

Undirected graph. G = (V, E)

  • V = nodes.
  • E = edges between pairs of nodes.
  • Captures pairwise relationship between objects.
  • Graph size parameters: n = |V|, m = |E|.

Directed Graphs

Graph Representation

Adjacency matrix - 邻接矩阵

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 List - 邻接表

Adjacency list. Node indexed array of lists.

  • Two representations of each edge.
  • Space proportional to m + n.
  • Checking if (u, v) is an edge takes $O(deg(u))$ time.
  • Identifying all edges takes $\Theta(m + n)$ time

离散数学中图论部分补充的 关联矩阵

Definition

Paths and Connectivity

Path:

A path in an undirected graph G = (V, E) is a sequence P of nodes $v_1, v_2, …, v_{k-1}, v_k$ with the property that each consecutive pair $v_i, v_{i+1}$ is joined by an edge in E.

simple path:

A path is simple if all nodes are distinct.

没有回路,每个顶点只经过一次

connected

An undirected graph is connected if for every pair of nodes u and v, there is a path between u and v.

Cycles:

A cycle is a path $v_1, v_2, …, v_{k-1}, v_k$ in which $v_1 = v_k, k > 2$, and thef irst k-1 nodes are all distinct.

Tree

An undirected graph is a tree if it is connected and 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 tree:

Given a tree T, choose a root node r and orient each edge away from r.

Algorithm

Connectivity in Undirected Graph

  • s-t connectivity problem

Given two node s and t, is there a path between s and t?

  • s-t shortest path problem

Given two node s and t, what is the length of the shortest path between s and t?

Connectivity in Directed Graphs

  • Directed reachability

Given a node s, find all nodes reachable from s

  • Directed s-t shortest path problem

Given two node s and t, what is the length of the shortest path between s and t?

  • Graph search

BFS extends naturally to directed graphs.

Strong Connectivity

  • mutually reachable:

Node u and v are mutually reachable if there is a path from u to v and also a path from v to u.

  • strongly connected :

A graph is strongly connected if every pair of nodes is mutually reachable.

Lemma. Let s be any node. G is strongly connected iff every node is reachable from s, and s is reachable from every node

  • Pf. Follows from definition.
  • Pf. Path from u to v: concatenate u-s path with s-v path.Path from v to u: concatenate v-s path with s-u path.

Topological Ordering

  • Def. A topological order of a directed graph G = (V, E) is an ordering of its nodes as $v_1, v_2, …, v_n$so that for every edge $(v_i, v_j)$ we have i < j.
  • Lemma. If G has a topological order, then G is a DAG.

DAGs (Directed Acyclic Graphs) 有向无环图

Def. An DAG is a directed graph that contains no directed cycles

Ex. Precedence constraints: edge $(v_i, v_j)$ means $v_i$ must precede $v_j$.

Lemma. If G has a topological order, then G is a DAG.

Pf. (by contradiction)

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

Lemma. If G is a DAG, then G has a node with no incoming edges.

Pf. (by contradiction)

  • Suppose that G is a DAG and every node has at least one incomingedge. Let's see what happens.
  • Pick any node v, and begin following edges backward from v. Since vhas at least one incoming edge (u, v) we can walk backward to u.
  • Then, since u has at least one incoming edge (x, u), we can walkbackward 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.

Pf. (by induction on n)

  • Base case: true if n = 1.
  • Given DAG on n > 1 nodes, find a node v with no incoming edges.
  • G - { v } is a DAG, since deleting v cannot create cycles.
  • By inductive 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 incoming edges. ▪

不断地添加入度为0的节点并删除即可

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 level of x and y differ by at most 1.

L0 = {s}.
L1 = all neighbors of L0
L2 = all nodes that do not belong to L0 or L1, and that have an edge to a node in L1
Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li

Analysis:

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

Pf.

Easy to prove O(n2) running time:

  • at most n lists L[i]
  • each node occurs on at most one list; for loop runs  n times
  • when we consider node u, there are <= 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 deg(u) incident edges (u, v)
  • total time processing edges is $\sum_{u∈V}deg(u) = 2m$

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∈R and v∉R
	Add v to R
Endwhile

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

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

无向图的联通分量及并查集,

有向图的强连通分量需要更多的算法思考

包括图的翻转等,可以参考 DSAA

Bipartite Graphs

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

二分图,可以使用两种颜色完成染色,匹配问题

Applications:

  • Stable marriage: men = red, women = blue.
  • Scheduling: machines = red, jobs = blue.

Benefits:

If a giving graph is bipartite, then Many graph problems become

  • easier if the underlying graph is bipartite (matching)
  • tractable if the underlying graph is bipartite (independent set)

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

Pf. Not possible to 2-color the odd cycle, let alone G.


Lemma. Let G be a connected graph, and let $L_0, …, L_k$ be the layersproduced 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) An edge of G joins two nodes of the same layer, and G contains an odd-length cycle (and hence is not bipartite).

使用 BFS 检测二分,可结合下图理解

Pf. (1)

  • Suppose no edge joins two nodes on same layer.
  • By previous property on page 19, this implies every edge join two nodes in adjacent layers.
  • Give nodes on odd levels = red, nodes on even levels = blue -> Bipartition.

Pf. (ii)

Suppose (x, y) is an edge with x, y in same level $L_j$.

Let $z = lca(x, y)$ = lowest common ancestor.

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

Its length is 1 + (j-i) + (j-i), which is odd.

​ (x, y) y->z z->x


Corollary. A graph G is bipartite iff it contain no odd length cycle.


Strong Connectivity

Theorem: Can determine if G is strongly connected in $O(m + n)$ time.

Pf.

  • Pick any node s.
  • Run BFS from s in G. ($O(m+n)$)
  • Run BFS from s in $G^{rev}$. (s->v $G^{rev}$ become v->s in G)
  • Return true iff all nodes reached in both BFS executions.
  • Correctness follows immediately from previous lemma.

Tpological ordering.

不断地添加入度为0的节点,并从图中删除该节点及与它相连的边即可

The algorithm finds a topological order in $O(m + n)$ time.

Pf.

  • 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: to delete v
  • remove v from S
  • decrement count[w] for all edges from v to w, and add w to S if count[w] hits 0
  • this is O(1) per edge ▪

Dijkstra's Shortest Path Algorithm

每次添加 能够到已经遍历过节点的最近节点即可