建于：20240407 22:33:00 Sunday 4600字 16分
Graph, Algorithm, and NOTE
CC BY 4.0（除特别声明或转载）
GraphAlgorithm
[!info]+ Def: Graph A graph is a pair of $G=(V, E)$ V is the collection of vertices E is the collection of edges
[!info]+ Def: Directed Graph (u, v) and (v, u) are distinct for some edges (u, v) $\in E$.
[!info]+ Def: Undirected Graph (u, v) and (v, u) are identical for all edges (u, v) $\in E$.
Graph Representation
Adjacency list Representation
 $adj[u]$ is a linked list of all v that (u, v) $\in E$.
 $adj[0] = {1, 3, 9}$ , $adj[1]= {0, 9, 2}, …$

In directed graphs, $dev^{+(v)} = adj[v] $ is the out degree of v
Adjacency matrix Representation
 $A=[a_{ij}]$ is a $n \times n$ matrix such that $a_{ij} = 1$ if $(v_{i,}v_{j}) \in E$.
DFS Algorithm
[!question]+ What does DFS do?
 Traverse all vertices in graph, and thereby
 Reveal properties of the graph.
Four array s are used to keep information gathered during traversal.
[!abstract]+ Four Arrays
 $color[u]$ : the color of each vertex visited
 white: undiscovered
 gray : discovered but not finished processing
 black: finished processing
 $pred[u]$ : the predecessor pointer pointing back to the vertex from which u was discovered
 $d[u]$ : the discovery time
 a counter indicating when vertex u is discovered
 $f[u]$: the finishing time
 a counter indicating when the processing of vertex $u$ ( and all its descendants ) is finished
\begin{algorithm}
\caption{DFS(G)}
\begin{algorithmic}
\State \textbf{Input}: Graph $G$
\State \textbf{Output}: Vertex traversal of graph $G$
\ForAll{vertex $u \in V(G)$}
\State $color[u] \gets \text{white}$ \Comment{Initialize}
\State $pred[u] \gets \text{NULL}$
\EndFor
\State $time \gets 0$
\ForAll{vertex $u \in V(G)$} \Comment{Start a new tree}
\If{$color[u] == \text{white}$}
\State \Call{DFSVisit}{$u$}
\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\caption{DFSVisit}
\begin{algorithmic}
\State $color[u] \gets \text{gray}$ \Comment{u is discovered}
\State $d[u] \gets ++$time \Comment{u's discovery time}
\ForAll{$v \in \text{adj}[u]$} \Comment{Visit undiscovered vertex}
\If{$color[v] == \text{white}$}
\State $pred[v] \gets u$
\State \Call{DFSVisit}{$v$}
\EndIf
\EndFor
\State $color[u] \gets \text{black}$ \Comment{u has finished}
\State $f[u] \gets ++$time \Comment{u finish time}
\end{algorithmic}
\end{algorithm}
[!tip]+ The output of DFS
 The time stamp arrays: d[v], f[v]
 The predecessor array: pred[v]
[!info]+ Def: DFS Forest Use $pred[v]$ to define a graph $F = (V, E_f)$ as follows: $E_{f}= {(pred[v],v) v \in V,\ pred[v] \neq NULL}$ It is a graph with no cycles, and a collection of trees.
[!abstract]+ HandShaking Theorem If G=(V, E) is an undirected graph \(2E = \sum_{u\in V}(deg(v))\) If G=(V, E) is an directed graph \(E = \sum_{u\in V} (deg^{}(v))= \sum_{u\in V} (deg^{+}(v))\)
DFS Time Analysisi
\(T_{DFS}(G)=O(n)+O(1)+T_v(G)\) \(= O(n) + \sum_{u \in V} (2deg^{+}(u)+ O(1))\) \(= O(n) + \sum_{u \in V} (2deg^{+}(u)\) \(= O(n + e)\)
DFS Properties
Time TimeStamp Structure
[!abstract]+ DFS Properties
 u is a descendant ( in DFS trees ) of v, if and only if $[d[u], f[u]]$ is a subinterval of $[d[v], f[v]]$.
 u is an ancestor of v, if and only if $[d[u], f[u]]$ contains $[d[v], f[v]]$ .
 u is unrelated to v, if and only if $[d[u], f[u]]$ and $[d[v], f[v]]$ are disjoint intervals.
[!abstract]+ Proof The idea is to consider every case. Assume $d[v] < d[u]$ wlog.
 If $f[v] > d[u]$ , then
 u is discovered when v is still not finished y et ( marked gray) $\Rightarrow$ u is a descendant of v ;
 u is discovered later than v $\Rightarrow$ u should finish before v;
 hence we have $[d[u], f[u]]$ is a subinterval of $[d[v] , f[v]]$.
 If $f[v] < d[u]$, then
 Obviously $[d[u], f[u]]$ and $[d[v] , f[v]] are disjoint;
 Which means that when u or v is discovered, the others are not marked gray;
 And hence neither vertex is a descendant of the other
Tree Structure
[!abstract]+ Theorem An edge in an undirected graph is either a tree edge or a back edge.
[!abstract]+ Proof Assume $d[u] < d[v]$. Then, v is be discovered while u is gray. Hence v is in the DFS subtree rooted at u.
 If $pred [v] = u$, $(u, v)$ is a tree edge.
 If $pred [v] \neq u$, $(u, v)$ is a back edge.
Application
Articulation
[!info]+ Def: Articulation Let G=(V, E) be a connected undirected graph. An articulation point (cut vertex) of G is a vertex whose removal disconnects G
[!question]+ Given a connected graph G, how to find all articulation points?
 Brute Force Solution
Brute Force Solution
 Remove a vertex and its corresponding edges one by one one from G.
 Test whether the resulting graph is still connected or not say by DFS.
The running time is O (n ∗(n + e)) .
Observations
 The root of the DFS tree is an articulation point if it has two or more children.
 A leaf of the DFS tree is not an articulation point.
 And for other internal vertex v in the DFS tree, v is an articulation point if if there is one subtree rooted at a child of v that does not have a back edge which climbs higher than v.
Tackle Observation 3
[!info]+ Def: Low and high Using the discovery time in the DFS tree to define low and high.
If there is a subtree rooted at a children of v which does not have a back edge connecting to a vertex with discovery time smaller than d[v] , then v is an articulation point.
 Let Low (w) be the smallest value that a descendant of w can climb up by a back edge.
 We use d[v] to express the “hight” of v.
 v is “higher” than u if v and u are on the same branch of the DFS tree and d[v] < d[u] .
 If v and u are on different branches, d[v] and d[u] are not compatible by the timestamp structure.