Graph

path

• a sequence P of nodes v1, v2, …, vk-1, vk with the property that each consecutive pair vi, vi+1 is joined by an edge in E.
• simple: path上沒有重複走過的點(distinct)
• cycle: path至少多於2個點，頭尾相連，中間的點distinct
• connected: 如果任意點到任意點之間都有path，則graph is connected
• distance: minimum number of edges in a u-v path

tree

• An undirected graph is a tree if it is connected and does not contain a cycle
• G若滿足兩個條件即為樹:
  • G is connected.
  • G does not contain a cycle.
  • G has n-1 edges.
• rooted tree: a tree with its root at r

BFS

• 從s(source)開始一層一層往外擴散直到visit所有可到達的點
• Layer
  $L_i$: i is the time that a node is reached.
  • $L_0$ = {s}
  • $L_{j+1}$ =
    $L_j$的鄰居中不屬於更上層layer的node
  • i: 從s到
    $L_i$的distance
• BFS Tree:
  • tree edge v.s. non tree edge
  • 一棵BFS tree中，若x屬於
    $L_i$，y屬於
    $L_j$，且(x,y)有edge連接(不一定是tree edge)，則i跟j最多差1
  • proof(by contradiction):
    1. 不失一般性，假設j>i，且j-i>1
    2. 根據定義，x屬於
       $L_i$，則x的鄰居不是屬於
       $L_{i+1}$就是屬於更上層的layer
    3. 因為(x,y)有edge連接，(x,y)必互為鄰居，且y屬於
       $L_j\to$ j ≤ i+1。
    4. $\to \leftarrow$
  • non tree edge: 跟自己同層(兄弟姊妹)或是差一層但不是父母(叔叔姪子…)

DFS

• 從s開始一直走，直到走到dead end，再回頭換別條路
• 一條edge會被檢查兩次(去跟回)
• DFS tree
  • tree edge必連接爸爸跟小孩，non tree edge必連接祖先子孫(跨層)
  • 一棵DFS tree中，若(x,y)之間為non tree edge，則x, y為祖先子孫關係
  • proof:
    • 不失一般性，假設x先被看到
    • (x,y)為non tree edge表示x看y時y已經被explored
    • 但是在剛看到x時y還沒explored
      $\to$ y是在剛呼叫DFS(x)跟DFS(x)的遞迴完全結束的過程中被發現的
    • y必存在由x往下的tree之中
      $\to$ y為x的子孫

connected component

• A connected component containing s is the set of nodes that are reachable from s.
• 通常取到最大
• Correctness:
  • 所有R裡面的node都reachable from s
    • 課本
  • 所有不屬於R的node都unreachable from s
    • 反證法

Implementation

• Graph representing
  • A graph G(V,E):
    • |V| = the number of nodes = n
    • |E| = the number of edges = m
  • n – 1 (lower bound of edges, tree) ≤ m ≤
    $(\genfrac{}{}{0ex}{}{n}{2})$ (upper bound of edges) ≤ n² for a connected graph
  • O(n) v.s O(n²)
  • Linear time (O(m+n)):
    • adjacency matrix:
      • graph G = (V, E) with n nodes, V = {1, …, n}
      • adjacency matrix of G is an nxn martix A where
        • A[u, v] = 1 if (u, v)
          $\in$ E;
        • A[u, v] = 0, otherwise.
      • time
        • O(1): check if (u, v)
          $\in$ E
        • O(n): 找出任一點的所有鄰居(掃過row跟column)
          • visit many 0 for sparse graph
      • space
        • O(n²)
    • adjacency list:
      • adjacency list of G is an array Adj[] of n lists, one for each node represents its neighbors
        • Adj[u] = a linked list of v (u, v) ${\in$ E}.
      • degree of u: u有多少鄰居
      • time:
        • O(deg(u)) time for checking one edge or all neighbors of a node.
      • space:
        • undirected: n+2m
          $\to$O(n+m)
        • directed: n+m
          $\to$O(n+m)
      • indegree and outdegree for directed graph
• Implementing BFS
• Implementing DFS
• Summary

Testing Bipartiteness

• bipartite graph (bigraph): a graph whose nodes can be partitioned into sets X and Y in such a way that every edge has one one end in X and the other end in Y.
• X and Y are two disjoint sets
• No two nodes within the same set are adjacent
• node可分成兩個group，group內的node不相連，所有edge的兩端必落在不同group
• Check if bipartite: Color the nodes with blue and red (two-coloring)
• If a graph G is bipartite, then it cannot contain an odd cycle.
• Procejure
  1. 假設G=(V,E)是connected
     • 若不是，不同的connected component分開執行
  2. 選一個任意起始點s塗成紅色
  3. 把s的鄰居塗成藍色
  4. 重複塗色直到整張圖都塗完顏色
  5. Test bipartiteness: 所有edge兩端都是不同顏色
  • 如果欲塗色的點已經被塗色而且其顏色跟欲塗的顏色不同，則不是bipartite graph
• 可用BFS實作
  • time: O(m+n)
  • 在最後加上著色的動作
• Correctness
  • 2 case:
    1. 沒有連接同層間node(兄弟姊妹)的edge
       $\to$bipartite
    2. 有連接同層間node(兄弟姊妹)的edge
       $\to$有odd cycle
       $\to$not bipartite
  • BFS特性: Let x
    $\in$L_i, y
    $\in$L_j, and (x, y)
    $\in$E. Then i and j differ by at most 1.
    • edge兩端的layer差必小於等於1
  • proof case 2:
    1. 假設(x,y)是兩端皆在同個layer L_j的edge
    2. z = lca(x, y) = lowest common ancestor
       • x跟y往上層layer看時最早的共同祖先
    3. Let L_i be the layer containing z
    4. 考慮經過x,y,z及(x,y)的cycle
    5. 長度為1+2(j-i)，為奇數

Connectivity in Directed Graphs

• directed graph: asymmetric relationships
• Representation: Adjacency list
  • Each node is associated with two lists, to which and from which
• mutually reachable: 對node u跟v，有從u到v的path，也有從v到u的path
• strongly connected: every pair of nodes are mutually reachable
• Lemma: If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable.
• determine strongly connectivity in linear time
  1. 選擇graph G中的任意起始點s
  2. R = BFS(s, G)
  3. R^rev = BFS(s, G^rev)
     • 因為要雙向都有path可到達對方，把G的edge方向全部反轉再做一次，就可以知道是否有反向的path連結
  4. 如果(R = V = R^rev)則為strongly connected
  • time: O(m+n)
• Strong Component
  • strong component containing s in a directed graph is the maximal set of all v s.t. s and v are mutually reachable.
  • Theorem: For any two nodes s and t in a directed graph, their strong components are either identical or disjoint.
    • directed graph中的任意兩點，不是在同個strong component就是在不同的strong component
    • proof:
      • Identical if s and t are mutually reachable
      • Disjoint if s and t are not mutually reachable

Directed Acyclic Graphs (DAG)

• an undirected graph has no cycles: tree (or forest)
• DAG: directed graph without cycles

Topological Ordering

• Given a directed graph G, a topological ordering is an ordering of its nodes as v1, v2, …, vn so that for every edge (vi, vj), we have i<j.

  • node可以照順序排好，排好後edge的方向都相同

  • 

  • Precedence constraints: edge (vi, vj) means vi must precede vj

• Lemma: If G has a topological ordering, then G is a DAG.
  • If G is a DAG, then does G have a topological ordering?
    • yes
  • proof by contradiction:
    • assume graph has cycle
• Lemma: In every DAG G, there is a node with no incoming edges.
  • proof by contradiction:
    1. 假設某DAG中每一點都有incoming edge
    2. 任選一點v，挑一條他的incoming edge往回走
    3. 因為每個點都有incoming edge，此動作可以一直重複，沒有上限
    4. 重複n+1次後，因為只有n個點，我們必會走到重複的點上
    5. C為兩次走到重複點w之間走過的點，C是cycle
       $\to$矛盾
    • 
• 
• Lemma: If G is a DAG, then G has a topological ordering.
  • proof by induction
    1. base case: n=1時成立(只有一個點，直接編號1號)
    2. inductive step:
       • 假設n個點時成立: n個點的DAG有topological ordering
       • 對於一個有n+1點的DAG，把一個沒有incoming edge的點分出來
         • 
       • 拿掉一個點及其連接的edge並不會創造cycle
         $\to$ G – {v}是有n個點的DAG
       • 根據假設，有n個點的DAG有topological ordering
       • 把v放在topological ordering的最前端是安全的(不會有cycle)
       • $\to$ G也有topological ordering
• Linear-Time Algorithm
  • 
  • time
  • O(n²): n個點執行n次函式，每次執行函式第1行找沒有incoming edge的點要掃過{n, n-1, n-2 …}個點
  • O(m+n):
    • Initialization: 建立adjacency list及紀錄indeg，把沒有incoming edge的點放到S
      • indeg(w) = # of incoming edges from undeleted nodes
      • S = set of nodes without incoming edges from undeleted nodes
      • O(m+n)
    • 原算法的line 3改為：
      1. Remove v from S
      2. 把所有從v連到w的indeg(w)減1，如果indeg(w)為0把w放進S
         • 單獨動作皆為O(1)
         • 這步會做m次(m條edge)
      • O(m+n)
    • line 4改為check S