书籍介绍:

https://book.douban.com/subject/3155710/

配套课程:

CS170(伯克利),CS161(斯坦福)

github仓库:

https://github.com/Doraemonzzz/Algorithm-DPV

参考资料:

https://math.stackexchange.com/questions/114240/disjoint-edges-between-vertices-of-odd-degree

https://cg3.chero.help/9780077388492-7007638.html

这次回顾第3章,图的分解。

3.5

方法:

  • 记原始邻接表为$G_1$
  • 初始化新接表$G_2$
  • for $v$ in $V$:
    • for $u$ in $G_1[v]$:
      • $G_2[u].\text{append}(v)$

时间复杂度:

  • 每条边和每个顶点都遍历一次,所以时间复杂度为$O(|V|+|E|)$

3.6

(a)

注意到

注意对于每条边$(u,v )\in E$,会分别在$d(u),d(v)$中记录一次,所以

(b)

如果度为奇数的顶点有奇数个,那么顶点的度之和为奇数,这就产生了矛盾。

(c)

不一定,考虑如下例子:

3.7

(a)

假设顶点编号为$1,\ldots, n$。

思路:

  • 进行dfs,给每个节点标记,父节点和子节点的标记不同,如果碰到已经访问过的节点,则查看其已有的标记和待标的标记是否相同,如果不同则返回false,否则返回true。

修改explore:

  • 初始化$\mathrm{group}[n], \mathrm{visited[n]}$
  • $\mathrm{explore}(v, k)$:
    • $\mathrm{visited}[v]=\mathrm{true}$
    • $\mathrm{group}[v]= k$
    • $\mathrm{res = true}$
    • for each edge $(v,u) \in E$:
      • if not $\mathrm{visited}[u]$:
        • $\mathrm {res} =\mathrm{explore}(u, 1-k)$
      • else if $\mathrm{group}[u]\neq 1-k$:
        • $\mathrm {res}=\ \mathrm{false}$
        • break
    • return res

修改dfs:

  • for all $v \in V$:
    • $\mathrm{visited}(v) = \mathrm{false}$
  • for all $v \in V$:
    • if not $\mathrm{visited}(v)$:
      • $\mathrm{res= explore}(v,0)$
      • if res = false:
        • return false
  • return true
(b)

$\Rightarrow$:

利用反证法,如果存在长度为奇数的环,不妨设为$a_1\to a_2 \to \ldots \to a_{2k-1}\to a_1$,那么依次涂色得到同色的两组:

  • $a_1,a_3,\ldots ,a_{2k-1}$
  • $a_2, a_4,\ldots, a_{2k-2}$

注意$a_1,a_{2k-1}$相邻,这就产生了矛盾。

$\Leftarrow$:

如果不存在长度为奇数的环,考虑如下着色法:

  • 构造搜索树。
    • 对于不存在环的无向图,搜索树中不存在回边,所以给根节点标记为颜色1,其余节点和父节点标记为不同色即可。
    • 对于存在环的无向图,用搜索树中访问到环中的第一个节点为$v$替换该环,那么新的搜索树不包含环,利用之前的方法着色即可;对于每个环,根据节点$v$着色即可,注意此时环的长度为偶数,对环着色是可以做到的。
(c)

最少的话需要三种颜色即可。

3.8

(a)

节点:三元组$v=(v_1, v_2,v_3), 0\le v_i \le m_i ,i=1,2,3$,此处$m_1= 10, m_2= 7,m_3 =4$。

边:$(u,v)\in E$当且仅当存在$i\neq j$使得:

起点:$u=(0, 7,4)$。

终点:$v=(7,2,2)$。

(b)

利用DFS即可。

3.9

  • 假设节点为$1,\ldots, n$,邻接表为$G$
  • for $u=1,\ldots,n$:
    • $\text{degree}[u]=G[u].\mathrm{size}$
    • $\text{degree}[u]=0$
  • for $u=1,\ldots,n$:
    • for $v$ in $G[u]$:
      • $\text{twodegree}[u]+=\text{degree}[v]$

3.10

修改后的算法如下:

  • $\mathrm{visited}=\{\mathrm{false}\}$
  • $S = \mathrm{stack}()$
  • $S.\mathrm{add}(u)$
  • $L=[]$
  • while !$S.\mathrm{empty}()$:
    • $u=S.\mathrm{back}()$
    • if $\mathrm{visited}(u)=\mathrm{false}$:
      • $\mathrm{visited}(u)=\mathrm{true}$
      • $\mathrm{previsit}(u)$
    • flag = true(判断相邻节点是否都访问过)
    • for $(u, v) \in E$:
      • if $\mathrm{visited}(v)=\mathrm{false}$:
        • $S.\mathrm{add}(v)$
        • flag = false
    • if flag:
      • $\mathrm{postvisit}(v)$
      • $S.\mathrm {pop}()$

3.11

假设$e=(u,v)$,从$v$开始dfs,假设第一步不访问$u$,如果后续访问到$u$,则存在包含$e$的回边。

3.12

因为$\operatorname{post}(u)<\operatorname{post}(v)$,所以$v$比$u$先入栈,因为$v,u$之间存在边,所以从$v$出发一定会访问到$u$,即在搜索树中,$v$是$u$的祖先;从$u$出发也会访问到$v$,但是这就和$\operatorname{post}(u)<\operatorname{post}(v)$矛盾。

3.13

(a)

删除搜索树的叶节点即可。

(b)

考虑环。

(c)

感觉题目有点问题,不添加边应该无法使其连通。

3.14

  • 记录每个顶点的邻接表$G[u]$。
  • 记录每个顶点的入度邻$\mathrm{indegree}[u]$,将$\mathrm{indegree}[u]=0$的点记录在数组$V$。
  • $L=[]$
  • while !$V.\mathrm{empty}()$:
    • $v= V.\mathrm{last}$
    • $L.\mathrm{append}(v)$
    • $V.\mathrm{popback}()$
    • for $u\in G[v]$:
      • $\mathrm{indegree}[u]—$
      • if $\mathrm{indegree}[u]=0$:
        • $V.\mathrm{append}(u)$
  • return $L$

第一步时间复杂度为$O(|V|+|E|)$,第二步中,每条边和每个点都遍历一次,时间复杂度为$O(|V|+|E|)$,因此总时间复杂度为$O(|V|+|E|)$。

3.17

(a)

任取$Inf(p)$中两个节点$v_{i}\neq v_j ,i< j$,如果$v_i,v_j$不属于同一强连通分量,如果$v_i$比$v_j$先访问,那么$v_i$访问次数有限,$v_j$访问次数无限,这就产生了矛盾;反之同理。

(b)

根据(a),只要判断是否存在元素数量大于$1$的强连通分量,利用课本中的算法即可。

后续两问没有给出优等顶点和劣等顶点的定义,默认为满足某种性质的顶点。

(c)

定义性质a:

  • 如果强连通分量中存在多于$1$个满足优等性的点,那么称其满足性质a。

判断全部强连通分量中是否有满足性质a的强连通分量即可。

(d)

定义性质b:

  • 如果强连通分量中存在多于$1$个满足优等性的点,并且不存在满足劣等性的点,那么称其满足性质b。

判断全部强连通分量中是否有满足性质b的强连通分量即可。

3.18

参考资料:

《算法概论习题试解》——吴彧文

方法1:

不妨设顶点编号为$1,\ldots, n$,申请二维数组$a[n][n]$,默认值为$0$。

利用dfs,dfs的过程中维护当前节点$u$的所有前驱节点集合$A$,

  • for $v\in A$:
    • $a[v][u] = 1$

时间复杂度分析:

dfs时间复杂度为$O(|V|+|E|)$;赋值操作中,时间复杂度为$O(|V|^2)$,所以总时间复杂度为$O(|V|+|E|+ |V|^2)$。

方法2:

利用霍夫曼码的思想给每个节点编码,然后判断两个节点的编码是否为另一个的前缀即可,但是这种方法查询时的时间复杂度为$O(l)$,其中$l$为两个节点编码的较小长度。

3.20

DFS的过程中记录根节点到当前节点$r_k$的路径$A=[r_0,\ldots, r_{k}]$,然后利用下式更新即可

3.22

  • 第一轮:计算强连通分量,得到图元。
  • 第二轮:在图元中从入度为$0$的点开始dfs,判断能否遍历图元中所有顶点。

3.23

  • 线性化图,将节点按照线化的顺序标记为$1,\ldots, n$,$s$和$t$的序号分别为$i_s, i_t$。
  • 初始化数组$\text{cnt}[n]=\{0\}$
  • for $j=1,\ldots , i_t$:
    • for $(k, j)\in E, k < j$:
      • $\mathrm{cnt}[j] = \mathrm{cnt}[j] + \mathrm{cnt}[k]$

3.24

从入度为$0$的顶点开始dfs,得到搜索树,如果树只有一个叶节点,则存在对应的路径。

3.25

(a)
  • 在$G^v$上计算线性序,将顶点记为$1,\ldots, n$。
  • 初始化$\text{cost}[i]= p_i$。
  • for $i=n,\ldots, 1$:
    • $\text{cost}[i]= \min_{(i,j)\in G^v, j\ge i} \text{cost}[j]$
(b)

计算SCC,得到图元$G_1$,每个图元顶点的价格为其所在SCC中顶点价格的最小值,在图元上利用算法(a)计算$\text{cost}$,对图元每个顶点$u$所在SCC中其他顶点$v$,令$\text{cost}[v]=\text{cost}[u]$。

3.26

注意欧拉圈存在的大前提应该是图是连通的。

(a)

证明:

$\Rightarrow$:

如果无向图含有Euler圈,那么必然存在如下形式的路径(该路径遍历了连通块中每个顶点以及每条边):

那么对于$a_{i_j}, 1<j < n$,存在边

这两条边使得$a_{i_j}$的度增加$2$。

对于$a_{i_1}(a_{i_n})$,存在边

这两条边使得$a_{i_1}$的度增加$2$。

注意该结论对每个连通块都成立,因此所有顶点的度都是偶数。

$\Leftarrow$:

如果所有顶点的度都是偶数,不妨设顶点为$1,\ldots, n$。

从顶点$1$开始,选择一条边$v_1$,注意这是连通块,并且$1$的度为偶数,因此必然存在一条路径从$1$出发,终止于$1$:

在该连通块中删除该路径,由之前的讨论可得新的图中节点的度依然为偶数,但是变成一个边数更少的图,因此在有限步之后图必然为空,每次删除的路径拼接在一起即可得到该连通块的欧拉圈;对每个连通块重复此操作即可得到完整图的欧拉圈。

(b)

充要条件是所有顶点的度为$2$(环)或者除了两个顶点的度为$1$,其余顶点的度为$2$(环加一条凸出边)。

(c)

充要条件是所有顶点的入度等于出度,这部分也可以使用之前的分析方法。

3.27

参考资料:

https://math.stackexchange.com/questions/114240/disjoint-edges-between-vertices-of-odd-degree

首先无向中所有顶点的度之和为偶数,因此度为奇数的顶点数量必然为偶数,从而可以构成分组。

为了方便叙述,后续将度为奇数的顶点简称为奇数顶点。

考虑如下命题:

$P(n)$:对于有$2n$个奇数顶点无向图,可以将奇数顶点分为$n$对顶点$\{(a_i, b_i) | i=1,\ldots, n\}$,使得存在$a_i\to b_i$的路径,满足$a_i\to b_i, a_j \to b_j ,\forall i\neq j$是边分离的。

利用数学归纳法证明该结论。

$n=1$时结论显然。

假设$n= k-1$时结论成立,下面证明$n=k$时结论也成立。

在某个连通分量中任取奇数顶点$i,j$,那么必然存在$i\to j$的路径,

找到该路径中的两个奇数顶点$a_s, a_t$,使得对于满足$ s< k< t$的任意$k$,$a_k$都为偶数顶点。

接着删除$a_s\to a_t$对应的边,奇偶性的变换:

  • $a_s, a_t$都删除一条边,所以变成偶数顶点。
  • 对于$ s< k< t$的任意$k$,$a_k$删除两条边$(a_{k-1}, a_k), (a_k,a_{k+1})$,所以$a_k$依然是偶数顶点。

因此经过该变换后,化成了$n=k-1$的情形,利用归纳假设可得对这$k-1$对奇数顶点,存在边分离的路径,显然这些路径都和$a_s\to a_t$边分离(因为新图中不存在$a_s\to a_t$的路径),因此对$n=k$,结论依然成立。

3.28

(a)

可知$x_1$必然为true,代入后将原问题化简为

因此$x_3$为false,$x_4$为true。从而$x_2$可以取true或false。

(b)

由之前讨论可得,$x_1$为true,并且$\overline{x_1}$为true,但这是矛盾的。

(c)

略。

(d)

如果$x$和$\bar x$在同一强连通分量中,那么

这显然是矛盾的。

(e)

首先解释算法的合理性。

假设我们已经给汇点强连通部件中两个文字$\alpha,\beta$赋值为true,那么

成立。

注意此时$\overline \alpha$为false,所以如下形式的蕴含必然为true

因此只需考虑如下形式的蕴含是否为true

注意到这等价于

这显然也是成立的($\overline \gamma$属于$\alpha$所在强连通部件)。

该讨论说明,如果对汇点强连通部件$S_1$中所有文字赋值为true,并且对文字的反赋值为false,那么必然会消除$S_1$以及$\overline \alpha $所在的强连通分量(其中$\alpha \in S_1$),从而算法的必然会停止。

注意到该算法等价于如下循环:

  • while 字句非空:
    • 令汇点强连通部件中文字$\alpha$为true,删除其所在子句;删除包含$\overline \alpha$的子句中的$\overline \alpha$。

该过程显然是正确的,并且由之前讨论可得该循环必然会结束,因此正确性得证。

(f)
  • 构造有向图$G_I$。
  • 计算SCC。
  • 按照e的方式赋值。

时间复杂度:

$O(n + m)$

3.31

参考资料:

https://cg3.chero.help/9780077388492-7007638.html

(a)

只需证明传递性,自反性和对称性是显然的。

假设$e_1\sim e_2, e_2\sim e_3$。

如果$e_1= e_2$或$e_2=e_3$,那么显然$e_1\sim e_3$。

如果$e_1\neq e_2$且$e_2\neq e_3$,那么存在环$p_1$包含$e_1,e_2$,存在环$p_2$包含$e_2,e_3$。

如果$p_1$包含$e_3$,或者$p_2$包含$e_1$,那么结论是显然的;否则考虑如下路径

该路径也是环,并且包含$e_1,e_3$,结论成立。

(b)

双连通部件:

  • $(A,B),(B,N),(N,O),(O,A)$
  • $(B,D)$
  • $(C, D)$
  • $(D, M)$
  • $(D,E),(E,L),(L,D)$
  • $(K,J),(J,I),(F,G),(G,H),(H,I), (H,K), (F,H),(L,J),(L,K)$

孤立顶点:$B,D,L$。

(c)

如果顶点集合的交集为空,那么对应不相交。

如果顶点集合的交集元素数量大于等于$2$,那么双连通部件存在公共边,这就和假设矛盾。

因此如果有交集,交集包含的元素数量必然等于$1$,不妨设该顶点为$u$,注意$u$在两个连通部件中各对应了两条边($(u,v_1),(u,v_2)$以及$(u,v_3),(u,v_4)$)。删除$u$之后,$v_1$无法到达$v_3$,这是因为如果存在路径$v_1\to v_3$,那么$u,v_1\to v_3$形成环,从而$v_1\to v_3$上的边为两个连通部件的交集,这就和假设矛盾,$u$必然为孤立顶点。

(d)

直观理解:将双连通部件变成超级节点减少了回路,从而使变换后的图是树。

利用反证法证明结论,如果变换后存在环,那么根据定义,该环构成了双连通部件,这就与图已经处理完矛盾。

(e)

该结论是显然的,因为子节点之间必然不存在路径,所以删除根节点之后图不连通。