algorithms-ch3-Decompositions of graphs

3.1 Graphs

Represent a graph by

Adjacency matrix -- sparse graph

n = |V | vertices v1, . . . , vn, this is an n × n array whose (i, j)th entry is aij

(For undirected graphs, the matrix is symmetric since an edge {u,v} can be taken in either direction.)
Adjacency list -- dense graph

3.2 DFS -- O(n)

3.2.1Pseudocode

Find all nodes reachable from a particular code

procedure explore(G,v)
Input: G = (V,E) is a graph, v ∈ V
Output: visited(u) is set to true for all nodes u reachable from v

visited(v) = true
previsit(v)    // first time we visit v
for each edge(u,v)∈E;
  if not visited(u): explore(u)
postvisit(v)    // last time we visit v, since all node reachable from v have been visted

procedure dfs(G)
for all  v ∈ V:
  visited(v) = false
for all  v ∈ V:
  if not visisited(v): explore(v)

procedure previsit(v)
pre[v] = clock
clock = clock + 1

procedure postvisit(v)
post[v] = clock
clock = clock + 1

又用了递归的方法，把图转成树更容易理解

Algorithm analysis: procedure explore explore each edge once(|E|), procedure dfs check each vertex once(|V|)，so the time complexity: O(|V| + |E|)

3.2.3Connectivity in undirected graphs

可以在previsit（）里加一个计数器，每遍历一次source，计数器加1，表示有几个cc

Property For any nodes u and v, the two intervals [pre(u), post(u)] and [pre(v), post(v)] are either disjoint or one is contained within the other.

pre/post

3.3 directed graph

For undirected graphs we distinguished between tree edges and nontree edges. In the directed case, there is a slightly more elaborate taxonomy:

Tree edges are actually part of the DFS forest.
Forward edges lead from a node to a nonchild descendant
in the DFS tree.
Back edges lead to an ancestor in the DFS tree.
Cross edges lead to neither descendant nor ancestor; they therefore lead to a node that has already been completely explored (that is, already postvisited).

edges

3.3.2Directed acyclic graphs

A graph without cycles is acyclic
(类比tree：undirected connected graph without cycles)

Property A: directed graph has a cycle if and only if its depth-first search reveals a backedge.

All DAGs can be linearized.
两种方法线性化：

DFS；: simply perform tasks in decreasing order of their postnumbers. After all, the only edges (u, v) in a graph for which post(u) <post(v) are backedges

Property: In a dag, every edge leads to a vertex with a lower post number.

找到source，输出并从图中删除; 直到图空
the vertex with the smallest postnumber comes last in this linearization, and it must be a sink—no outgoing edges.
Symmetrically, the one with the highest post is a source, a node with no incoming edges.

Property: Every dag has at least one source and at least one sink. ( remove a source or sink, still a DAG)

3.4 SCC(Strongly connected components)

Undirected graph
DFS--trees in the forest = connected component
Directed graph:
Two nodes u and v of a directed graph are connected if there is a path from u to v and a path from v to u.
This relation partitions V into disjoint sets that we call **strongly connected components. **

Every directed graph is a dag of its strongly connected components. (acyclic graph can be linearized)

和DFS结合的相关性质

Property 1 : If the explore subroutine is started at node u, then it will terminate precisely when all nodes reachable from u have been visited.

Property 2 : The node that receives the highest post number in a depth-first search must liein a source strongly connected component.

Property 3 : If C and C′ are strongly connected components, and there is an edge from a node

The resulting algorithm is this.

Run depth-first search on GR.
Run the undirected connected components algorithm (from Section 3.2.3) on G, and during the depth-first search, process the vertices in decreasing order of their post numbers from step 1.

找出有向图的强连通分量：

在G reverse上dfs，
找到最大的postvisit（）删除能够遍历到的点，这些点构成一个强连通分量
如果还有顶点没有被删除，回到3，否则结束

补充一个点，CLRS上的

拓扑排序算法：
topological sort(G)

call DFS(G) to compute finishing time postvisit(v) for each vertex v
as each vertex is finish, insert it onto the front of a linked list
return the linked list of vertices

Time complexity:T(n) = Θ（V+E）
dfs复杂度为V+E ，插入链表 O（1）

exercise

这章exercise 1-13都值得看一下，28，31 是很重要的两个问题
画图的不写了，随便挑几道放上来供玩赏┑(￣Д ￣)┍

3.5 The reverse of a directed graph G = (V,E) is another directed graph GR = (V,ER) on the same vertex set, but with all edges reversed; that is, ER = {(v, u) : (u, v) ∈ E}.Give a linear-time algorithm for computing the reverse of a graph in adjacency list format.（GR,ER R为上标）
sol

function find-reverse(G)
Input: Graph G = (V,E) in adjacency list
Output G reverse


 for each edge (v, u) ∈ E
   do reverse (v, u) to get (u, v)

Algorithm analysis

(i) The algorithm terminates because it considers each edge once
(ii) The algorithm is correct because it reverses each edge. Thus, we have the new
graph GR = (V, ER) where V is the original vertex set and E
R is the set of
reversed edges
(iii) The algorithm runs in time O (m) because it does a constant amount of work
for each of the O (m) edges. We simply look at each element of the edge list in
our adjacency list representation and swap the vertices.

3.6 In an undirected graph, the degree d(u) of a vertex u is the number of neighbors u has, or equivalently, the number of edges incident upon it. In a directed graph, we distinguish between the indegree din(u), which is the number of edges into u, and the outdegree dout(u), the number of edges leaving u.
a. Show that in an undirected graph,

Paste_Image.png

b. Use part (a) to show that in an undirected graph, there must be an even number of vertices whose degree is odd.
c. Does a similar statement hold for the number of vertices with odd indegree in a directed graph?
sol

(a)this formula states that for an undirected graph if we sum all the degrees of each vertex, then this will equal 2 times the number of edges.
Since each edge must start at a vertex and end at a vertex, we see that for each edge that we add to the graph we are increasing the total sum of degrees by 2 for an undirected graph, thus the formula is correct

(b) This also makes sense since the total sum of degrees in an undirected graph must be an even number, if there were an odd number of vertices whose degree were odd, then the total degrees for the graph would be odd which violates the equality stated above

3.7 A bipartite graph is a graph G = (V,E) whose vertices can be partitioned into two sets (V = V1 U V2) and V1 int V2 = 0 such that there are no edges between vertices in the same set (for instance, if u, v is an element of V1, then there is no edge between u and v).

(a) Give a linear-time algorithm to determine whether an undirected graph is bipartite.

(b) There are many other ways to formulate this property. For instance, an undirected graph is bipartite if and only if it can be colored with just two colors.Prove the following formulation: an undirected graph is bipartite if and only if it contains no cycles of odd length.

(a) Perform a DFS on the undirected graph. The root node will belong to the set V1, once we visit a node we will mark it set V2, if its parent is V1, or set V1 if its parent is V2. When we visit a node we will look at its neighbors to determine if any of the sets are equal to the current node, if they are then this is not a bipartite graph, otherwise, if the graph is strongly connected then it is a bipartite graph
用b中的coloring角度来看

function graph-coloring(g)
Input: Graph G
Output: if the graph is bipartite, return true, otherwise, return false

//initialize
for all v∈V
  visited(v) = false
  color(v) = GREY

while ∃s ∈ V && visit(s) = false
  visited(s) = true
  color(s) = WHITE
  S = [s] //Stack S contains vertices
  while S is not empty
    u = pop(S)
    for all edges (u,v) ∈ E:
      if visited(v) = false:
        visited[v] = true
        push(S,v)

      if color(v) = GREY
//it has not been visited, set color
        if color(u) = BLACK:
          color(v) = WHITE
        if color(u) = WHITE:
          color(v) = BLACK
      else if color(v) = WHITE:
//if has been visited, compare color
        if color(u) != BLACK:
          return false
       else if color(v) = BLACK:
         if color(u) != WHITE:
            return false
return true

(b)An undirected graph is bipartite if and only if it contains no cyles of
odd length
Proof: (这个过程写出来及其麻烦，其实只要画个图简要说明一下应该就可以：根据上面的算法可以知道,一个图为二分的一个充要条件是对于每条 non-treeedge (u,v),有顶点u,v的颜色不相同,也即是在DFS树上顶点u,v要间隔奇数层。而环的长度为间隔层数加 1,为偶数。于是得证)

⇒Consider a path P whose start vertex is s, end vertex is t and it passes
through vertices u1, u2, ..., un and the associated edges are (s, u1),(u1, u2), ...,(un, t).
Now if P is a cycle, then s and t are the same vertices. Without loss of generality
assume s is in V1. Each edge (ui
, ui+1) goes from one vertex set to other.
Therefore a path must have 2·i edges to come back into the same vertex set
where i ∈ N. Since s and t are in same vertex set, so the length of the cycle
formed must be 2·i which is even.
⇐Suppose the graph has a cycle of odd length. Let the cycle be C and it passes through vertices u1, u2, ..., un where u1 = un. The associated edges are
(u1, u2), ...,(un−1, un). We start coloring edges of using two colors WHITE and
BLACK. Without any loss of generality u1 is colored WHITE while un−1 is
colored BLACK since n is odd and therefore n − 1 is even. Choosing color of
un as WHITE conflicts with the color of un−1 while choosing color as BLACK
conflicts with the color of u1. Therefore it is not possible to color an odd cycle
with 2 colors which implies that the graph is not bipartite

3.13. Undirected vs. directed connectivity.
(a) Prove that in any connected undirected graph G = (V,E) there is a vertex v ∈ V whose
removal leaves G connected. (Hint: Consider the DFS search tree for G.)
sol

Consider the DFS tree at any vertex, if we remove a leaf(v) from this tree, we still get a tree which is a subgraph of the graph obtained by remaining v. Hence the graph remain connected.
(虽然这个证明确实很简单, 注意是conected undirect graph就可以了，但是个人觉得这个证明答案跟没说一样，其实大部分证明都这画风的)
加一个详细的解释