算法设计与分析笔记0x01 —— 图

Basic Definition and Application

  • 有向图与无向图
  • 图的表示
    • 邻接矩阵
      • 查看二点间是否有边很方便, $\Theta(1)$
      • 遍历复杂度较高, $\Theta(n^2)$
    • 邻接表
      • 利于稀疏图
      • 遍历复杂度 $\Theta(m+n)$, m个结点,n条边
      • 检查(u,v)是否为边, O(deg(u)),检查与u相邻的边

  • Paths and Connectivity
    • Def. A path in an undirected graph G = (V, E) is a sequence P of nodes v1 , v2 , …, v(k-1) , vk with the property that each consecutive pair vi , v(i+1) is joined by an edge in E.
    • Def. simple path: 路径上结点不重复
    • Def. connected graph: 任意两个结点间都存在路径
  • Cycles
    • Def. cycle: a path (v1,v2…vk),前k-1个结点不重复
  • Tree
    • Def: 不含cycle的无向图
    • Theorem
      • connected
      • no cycle
      • n-1 edges (n is number of nodes)
  • Rooted tree. Given a tree T, choose a root node r and orient each edge away from r.

Graph Traversal

  • s-t connectivity problem 连通性问题
  • s-t shortest path problem 最短路径问题
  • Applications
    • Maze traversal.
    • Fewest number of hops in a communication network.
    • Driving direction in Google Maps
  • Algorithm
    • 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 .
    • L(i+1) = all nodes that do not belong to an earlier layer, and that have
      an edge to a node in Li .
  • Theorem. For each i, Li 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 (x, y) be an edge of G. Then the level of x and y differ by at most 1.
  • 走到底再回溯

BFS/DFS Analysis

  • O(m+n) 邻接表存储
  • Pf.
    • 初始化 访问O(n)
    • 访问一条边 deg(u),每条边访问两次
    • 总访问时间 sum(deg(u)) = 2m
  • BFS/DFS也可以用于查找Connected Component,连通分支

Testing Bipartiteness

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
  • Testing bipartiteness
    • 给定一个图,判断是否是二分图
    • 若给定图是二分图,很多图的相关问题会变得更简单
  • independent set: 多项式时间算法

    Lemma

  • 二布图不含奇数长度的环(充分必要
  • BFS时,以下命题仅一个发生
    • (i) 没有一条边连接同一层的两个结点,为二布图
    • (ii) 同一层的两个结点中至少一条边,含奇数长度的环,不为二布图
  • Pf. (i)
    • Suppose no edge joins two nodes in the same layer.
    • Bipartition: red = nodes on odd levels, blue = nodes on even levels.
  • Pf. (ii)
    • Suppose (x, y) is an edge with x, y in same level L j .
    • Let z be lowest common ancestor of x, y in BFS tree.
    • Let L i 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.

Connectivity in Directed Graph

  • Directed reachability
  • Directed s-t shortest path problem
  • Graph search
  • Web crawler
  • Strong Connectivity
    • Def. mutually reachable. u->v and v->u
    • Def. 任意两个结点都可相互抵达,则strong connectivity
  • Lemma. Let s be any node. G is strongly connected iff every node is reachable from s, and s is reachable from every node.

Strong Connectivity: Algorithm

  • Theorem. Can determine if G is strongly connected in O(m + n) time.
    • Pick any node s.
    • Run BFS from s in G.
    • Run BFS from s in Grev(reverse orientation of every edge in G).
    • Return true iff all nodes reached in both BFS executions.
    • Correctness follows immediately from previous lemma.

DAGs and Topological Ordering

  • Directed Acyclic Graphs
  • 有向无环图
  • 拓扑序列: A topological order of a directed graph G = (V, E) is an ordering of its nodes as v1 , v2 , …, vn so that for every edge (vi , vj) we have i < j.
  • Applications of Precedence Constraints
    • Edge (vi , vj) means task vi must occur before vj .
    • 课程先修图, course vi must be taken before vj .
    • 编译顺序, module vi must be compiled before vj .
    • Pipeline of computing jobs, output of job vi needed to determine input of job vj.

Lemma

  • Lemma1: 若一张图有拓扑排序,则为DAG(充分必要)。证明如下:
    • Suppose that G has a topological order v1 , …, vn 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 vj be the node just before vi; thus (vj , vi) is an edge.
    • By our choice of i, we have i < j.
    • On the other hand, since (vj , vi) is an edge and v1 , …, vn is a topological order, we must have j < i, a contradiction.
  • Lemma2: DAG中存在一个结点,没有边指向它。证明如下:
    • Suppose that G is a DAG and every node has at least one incoming edge. Let’s see what happens.
    • Pick any node v, and begin following edges backward from v. Since v has 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 walk backward 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.
  • Lemma3: 若一张图为DAG,则有拓扑排序。证明如下:
    • 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.
    • (即不断删除没有边指向的点)

Running Time

  • Theorem. 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

Leave a Reply

Your email address will not be published.