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

又用了遞歸的方法兰迫，把圖轉(zhuǎn)成樹更容易理解

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（）里加一個計數(shù)器紧卒，每遍歷一次source上岗，計數(shù)器加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結(jié)合的相關(guān)性質(zhì)

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（）刪除能夠遍歷到的點吃型，這些點構(gòu)成一個強連通分量
如果還有頂點沒有被刪除，回到3僚楞，否則結(jié)束

補充一個點勤晚，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復(fù)雜度為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為上標(biāo)）
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: (這個過程寫出來及其麻煩膜赃，其實只要畫個圖簡要說明一下應(yīng)該就可以：根據(jù)上面的算法可以知道,一個圖為二分的一個充要條件是對于每條 non-treeedge (u,v),有頂點u,v的顏色不相同,也即是在DFS樹上頂點u,v要間隔奇數(shù)層挺邀。而環(huán)的長度為間隔層數(shù)加 1,為偶數(shù)。于是得證)

?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就可以了，但是個人覺得這個證明答案跟沒說一樣悠夯，其實大部分證明都這畫風(fēng)的)
加一個詳細的解釋