图连通性 若干拓展问题探讨 北京大学 李煜东.

Presentation on theme: "图连通性 若干拓展问题探讨 北京大学 李煜东."— Presentation transcript:

1 图连通性 若干拓展问题探讨 北京大学 李煜东

2 引言 Black History …… 去年冬令营营员交流时，我和王启圣上来讲了Robert.E.Tarjan参与发明的斐波那契堆……
Why this topic > _ <？ 今年有幸再次来WC，本着继续膜拜Tarjan的一种精神，于是决定把Tarjan主要研究的方向 之一 —— 图连通性作为主题。 这部分内容难度本身就不大，所以希望大家度过一个愉悦的上午。。。（什么？你说后缀 仙人掌和函数式LCT也愉♂悦？别闹了那不是一种愉悦好么……）

3 安排 第一节课 - 知识普及 - 8:00~9:00 无向图连通性（面向NOIP选手）
第二节课 - 主要内容 - 9:00~9:15、9:30~10:45 有向图连通性、Dominator Tree、Shannon Switching Game、Disjoint Spanning Tree 第三节课 - 拓展讨论 - 11:00~12:00 图灵机与计算复杂性理论（知识扩充）

4 无向图连通性 无向图的割点、桥、双连通分量；经典Tarjan算法

5 需要解决的问题 无向图的割点、割点集合与点连通度 无向图的桥、割边集合与边连通度 无向图的割点与点双连通分量的求法
无向图的桥与边双连通分量的求法、边双连通分量的构造 使用Tarjan算法求最近公共祖先 相关例题讨论

6 割点 在无向连通图G上进行如下定义： 割点：若删掉某点P后，G分裂为两个或两个以上的子图，则称P为G的割点。
割点集合：在无向连通图G中，如果有一个顶点集合，删除这个顶点集合以及与该点集中 的顶点相关联的边以后，原图分成多于一个连通块，则称这个点集为G的割点集合。 点连通度：最小割点集合的大小称为无向图G的点连通度。

7 割边 类似地，在无向连通图G上进行如下定义： 桥(割边)：若删掉某条边b后，G分裂为两个或两个以上的子图，则称B为G的桥(割边)。
割边集合：如果有一个边集合，删除这个边集以后，原图分成多于一个连通块，则称这个 边集为割边集合。 边连通度：最小割边集合的大小称为无向图G的边连通度。

8 双连通分量 点双连通图：点连通度大于1的图称为点双连通图（没有割点）。 边双连通图：边连通度大于1的图称为边双连通图（没有割边）。
无向图G的极大(点/边)双连通子图称为(点/边)双连通分量。 缩点：把一个双连通分量缩为一个点的过程，就是删除与该双连通分量相关的所有点和边， 然后新建一个点，向所有与双连通分量中的点有边相连的点连边。

9 无向图上的经典Tarjan算法 Tarjan基于对图的深度优先搜索，并对每个节点引入两个值：
dfn[u]：节点u的时间戳，记录点u是DFS过程中第几个访问的节点。 low[u]：记录节点u或u的子树不经过搜索树上的边能够到达的时间戳最小的节点。 对于每一条与u相连的边(u,v)： 若在搜索树上v是u的子节点，则更新low[u]= min(low[u], low[v])； 若(u,v)不是搜索树上的边，则更新low[u]= min(low[u], dfn[v])；

10 求割点 对于一条搜索树上的边(u,v)，其中u是v的父节点，若low[v]>=dfn[u]，则u为割点。
low[v]表示v和v的子树不经过搜索树上的边能够到达的时间戳最小的节点； low[v]>=dfn[u]说明从v到以u为根的子树之外的点必须要经过点u； 因此u是图中的一个割点。 在DFS的过程中，首先递归u的子节点v。从v回溯至u后，检查上述不等式是否成立。若成 立，则找到了一个割点u。

11 求点双连通分量 可以在求割点的过程中维护一个栈求出每个点双连通分量。 建立一个栈，存储DFS过程中访问的节点，初次访问一个点时把该点入栈。
如果边(u,v)满足low[v]>=dfn[u]，即满足了u是割点的判断条件，那么把点从栈顶依次取出， 直至取出了点v，取出的这些点和点u一起组成一个点双连通分量。 割点可能属于多个点双连通分量，其余点和每条边属于且仅属于一个点双连通分量。因此 在从栈中取出节点时，要把u留在栈中。 整个DFS结束后，栈中还剩余的节点构成一个点双连通分量。

12 实现 procedure tarjan(x is a vertex) { visit[x]←true dfn[x]←low[x]←num←num+1 push x into stack s for each edge (x,y) from x do if not visit[y] then { tarjan(y) low[x]←min(low[x],low[y])     if low[y]>=dfn[x] then     { mark x as a cut-vertex     repeat     z←top of stack s pop z from stack s     until z=y mark vertexes just poped and x as a DCC     }    } else low[x]←min(low[x],dfn[y]) }

13 Knights of the Round Table
国王要在圆桌上召开骑士会议，但是若干对骑士之间互相憎恨。出于各种各样奇♂怪的原 因，每次开会前都必须对出席会议的骑士有如下要求： ① 相互憎恨的两个骑士不能坐在相邻的2个位置； ② 为了让投票表决议题时都能有结果（不平票），出席会议的骑士数必须是奇数。 如果有某个骑士无法出席任何会议，则国王会为了Peace of the World把他踢出骑士团。 现在给定骑士总数n(n<=1000)，以及m(m<= )对相互憎恨的关系，求至少要踢掉 多少个骑士？

14 Knights of the Round Table
题目大意：给定若干骑士和他们之间的仇恨关系，规定召开圆桌会议时，两个有仇恨的骑 士不能坐在相邻位置，且召开一次圆桌会议的骑士人数必须为奇数，求有多少骑士永远不 可能参加某一次圆桌会议。 模型转化：建补图——没有仇恨的骑士间连边。 几个骑士可以召开圆桌会议的条件是它们构成一个奇环。 问题转化为：求有多少个骑士不包含在任何奇环内。

15 Knights of the Round Table
引理：若某个点双连通分量中存在奇环， 则该点双联通分量中的所有点都在某个奇 环内。 用经典Tarjan算法找出所有点双联通分量。 判定每个点双联通分量是不是二分图，就 可以知道它有没有奇环。

16 求桥 对于一条搜索树上的边(u,v)，其中u是v的父节点，若low[v]>dfn[u]，则(u,v)是桥。
low[v]表示v和v的子树不经过搜索树上的边能够到达的时间戳最小的节点； low[v]>dfn[u]说明从以v为根的子树到子树之外必须要经过边(u,v)，因此(u,v)是桥。 可以像求割点一样，当v回溯至u后，判断上述不等式是否成立。 另一种判断方法：当递归v结束时，如果low[v]==dfn[v]说明v和v的父节点之间的边是桥。 P.S. 在有重边的图上求桥，需要注意对这些重边加以区分。

17 求边双连通分量 边双连通分量的求法非常简单，只需在求 出所有的桥以后，把桥边删除。
此时原图分成了若干个连通块，每个连通 块就是一个边双连通分量。 桥不属于任何一个边双连通分量； 其余的边和每个顶点都属于且仅属于一个 边双连通分量。

18 实现 procedure tarjan(x is a vertex) { visit[x]←true dfn[x]←low[x]←num←num+1 for each edge (x,y) from x do if not visit[y] then { tarjan(y) low[x]←min(low[x],low[y]) if low[y]>dfn[x] then mark edge (x,y) as a bridge } else if edge(x,y) not on DFS tree then low[x]←min(low[x],dfn[y]) //the following step can also find bridges if dfn[x]=low[x] then mark edge into x on DFS tree as a bridge }

19 边双连通分量的构造 任意给定一个无向连通图，最少添加多少条边可以把它变为边双连通图？
求出所有的桥和边双连通分量，把每个双连通分量缩为一个点。 此时的图只包含缩点后的双连通分量和桥边，是一棵无根树。 统计树中度数为1的节点的个数cnt。把树变为边双连通图，至少需要添加(cnt+1)/2条边。 构造方法：每次寻找最近公共祖先最远的两个度数为1的节点，在两点之间连一条边。 这样可以使这两个点到LCA的路径上的所有点形成环，环一定是双连通的。

20 故乡的梦 不知每日疲于在城市的水泥森林里奔波的你会不会有时也曾向往过乡村的生活。你会不会 幻想过，在夏日一个静谧的午后，你沉睡于乡间路边的树荫里，一片叶子落在了你的肩上， 而你正做着一个悠长的梦，一个没有城市的梦。我们的问题，正围绕着这个梦境展开…… 从 Azure 求学的城市到 Azure 家乡的村庄由若干条路径连接，为了简化起见，我们把这 些路径抽象成一个 N 个节点的无向图，每个节点用一个[1,N]内的整数表示，其中城市在S 节点，Azure 的故乡在T 节点。在某些节点对(x,y)之间会有双向道路连接，道路的长度为c。 不过最近某些道路可能会在施工，Azure 想知道，假如某条道路被施工而不能通行的话， 他到故乡的最短路经的长度为多少（多次询问）。

21 故乡的梦 第一行两个正整数 N 和 M，分别表示结点数和道路数。
之后M 行，每行三个正整数x,y,c，表示在x 和 y 之间存在一条长度为c的道路。 之后一行包含两个正整数S 和T，表示 Azure 所在位置和故乡的位置。 之后一行包含一个整数Q，表示询问的数目。 之后Q行，每行两个整数u 和v，表示 Azure 想知道如果连接u 和v之间的道路进入了维修 状态，从S 到T 的最短距离会变为多长。 N,m,Q<=

22 故乡的梦 首先用堆优化的Dijkstra算法求出各个点到起点S和终点T的最短路。
然后BFS求出最短路径图（所有满足DistS[u]+w(u,v)=DistS[v]的边构成的图）。 从图中去掉无用节点（把满足上面条件的边(u,v)看做有向边时不能到达T的点）。 使用经典Tarjan算法求出图中的桥，并找出所有的边双连通分量。 由最短路径图的性质，这些双连通分量可以一字排开，相邻两个之间由桥边连接。

23 故乡的梦 对于不删除桥边的询问，最短路不变，答案就是DistS[T]。 如果删除了桥边，就离线采用以下做法求出所有此类询问的答案：
建立一个小根堆，在堆中存储一些边，边(u,v)对应的值为DistS[u]+w(u,v)+DistT[v]. 依次扫描到每个双连通分量。到达一个DCC后，首先在堆中删除前面的DCC出发到这个 DCC的边，然后在堆中添加这个DCC出发到后边DCC的边。 堆中的最小值就是“删除掉当前连通块和下一个连通块之间的关键边”时的答案。 整个算法的复杂度为O((N+M+Q)logN)。

24 最近公共祖先 离线处理：读入所有的询问（可使用邻接表存储）。
给每个节点添加一个颜色标记，尚未访问的标记为0，进入递归而未回溯的节点标记为1， 已经访问过的标记为2。 维护一个并查集，访问完某个节点时，就合并该节点所在的集合与其父节点所在的集合。 正在处理点u时，u和u的所有祖先的标记均为1，已经访问过的节点均与父节点相连；因此 遍历子树u后，考虑所有与u相关的询问lca(u,v)，那么lca(u,v)就是v所在并查集的根。

25 经典Tarjan算法求LCA procedure tarjan(x is a vertex) { fa[x]←x, color[x]← for each edge (x,y) from x do if color[y]=0 then tarjan(y), fa[y]←x for each query(x,y) from x do if color[y]=2 then answer of query(x,y) ← get(y); color[x]←2; }

26 Network A network administrator manages a large network. The network consists of N computers and M links between pairs of computers. Any pair of computers are connected directly or indirectly by successive links, so data can be transformed between any two computers. The administrator finds that some links are vital to the network, because failure of any one of them can cause that data can't be transformed between some computers. He call such a link a bridge. He is planning to add some new links one by one to eliminate all bridges. You are to help the administrator by reporting the number of bridges in the network after each new link is added.

27 Network The input consists of multiple test cases. Each test case starts with a line containing two integers N(1 ≤ N ≤ 100,000) and M(N - 1 ≤ M ≤ 200,000). Each of the following M lines contains two integers A and B ( 1≤ A ≠ B ≤ N), which indicates a link between computer A and B. Computers are numbered from 1 to N. It is guaranteed that any two computers are connected in the initial network. The next line contains a single integer Q ( 1 ≤ Q ≤ 1,000), which is the number of new links the administrator plans to add to the network one by one. The i-th line of the following Q lines contains two integer A and B (1 ≤ A ≠ B ≤ N), which is the i-th added new link connecting computer A and B.

28 Network 使用Tarjan算法求出图中所有的桥； 找到图中的每一个双联通分量，缩成一个点，此时图变成了一棵树；
每次加入一条边(x,y)，相当于x到lca(x,y)、y到lca(x,y)和(x,y)这条边构成了一个环； 在环上的边都不是割边，于是可以给这些边打上标记，并更新割边个数。 当然以前标记过的边就不要重复计算了； 处理环的过程中，对于标记过的边可用并查集路径压缩加以优化，不重复经过以保证时间。 思考：在仙人掌上多次询问两点之间的最短路径？

29 Traffic Real Time Query System
City C is really a nightmare of all drivers for its traffic jams. To solve the traffic problem, the mayor plans to build a RTQS (Real Time Query System) to monitor all traffic situations. City C is made up of N crossings and M roads, and each road connects two crossings. All roads are bidirectional. One of the important tasks of RTQS is to answer some queries about route-choice problem. Specifically, the task is to find the crossings which a driver MUST pass when he is driving from one given road to another given road.

30 Traffic Real Time Query System
The first line contains two integers N and M. （0<N<=10000, 0<M<=100000） The next M lines describe the roads. In those M lines, the ith line (i starts from 1)contains two integers Xi and Yi, representing that roadi connects crossing Xi and Yi (Xi≠Yi). The following line contains a single integer Q. （0<Q<=10000） Then Q lines follows, each describing a RTQ by two integers S and T(S≠T) meaning that a driver is now driving on the road s and he wants to reach road t . For each RTQ prints a line containing a single integer representing the number of crossings which the driver MUST pass.

31 Traffic Real Time Query System
题目要求在一个无向图上多次询问从一条路到另一条路的必经点。 Tarjan求出点双连通分量，缩点后建树； 对于每个询问通过LCA即可计算； 类似的题目还有多次询问一个点到另一个点的必经边（ContestHunter Round #24 C）。 改为求边双连通分量即可。

32 有向图连通性与Dominator Tree
有向图的割点、桥；必经节点树(Dominator Tree)的Lengauer-Tarjan算法

33 需要解决的问题 有向图的强连通分量（大家已经非常熟悉，不再介绍） 有向图的必经点 有向图的桥边 必经节点树 Dominator Tree
Lengauer-Tarjan算法

34 Flow Graph的DFS遍历 Flow Graph
若有向图G中存在一点r，从r出发可以到达G中所有的点，则称G是Flow Graph，记为(G,r)。 搜索树（Dfs Tree） 从r出发对G进行深度优先遍历，递归时经过的有向边构成一棵树，称为G以r为根的搜索树。 时间戳（Dfn） 遍历过程中，按照节点经过的时间先后顺序给每个节点一个标号——时间戳，记为dfn[x]。 时间戳为x的节点的原编号记为id[x]，即id[dfn[x]]=x。

35 对图中的边进行分类 若(G,r)是一个Flow Graph，T是其Dfs Tree，则G中的每条边(x,y)必属于以下四类之一：
树枝边 (tree arcs)：边(x,y)在搜索树T中； 前向边 (forward arcs)：在T中存在一条从x到y的路径； 后向边 (cycle arcs)：在T中存在一条从y到x的路径； 横叉边 (cross arcs)：在T中既没有x到y的路径，也没有y到x的路径，并且dfn[y]<dfn[x]。

36

37 有向图的必经点问题 例题：Important Sisters 冬令营讲义第123页 题目要求解决的模型：
给定有向图G（可能有环）和图中的一个点r，对于G中的任意一个点x，求从r到x的路径上 （可能有很多条）必须经过的点集。

38 必经点与最近必经点 必经点（dom） 若在(G,r)中从r到y的路径一定经过点x，则 称x是从r到达y的必经点，记为x dom y。
从r出发到达y的所有必经点构成的集合记 为dom(y)，即dom(y)={x | x dom y}。 最近必经点（idom） 节点y的必经点集合dom(y)中dfn值最大的 点x是距离y最近的必经点，称为y的最近 必经点。最近必经点是唯一的，因此可以 记x=idom(y)。

39 暴力求解 𝑝𝑟𝑒 𝑦 = 𝑥 (𝑥,𝑦)∈𝐸} —— 𝑦的前驱节点集合 𝑠𝑢𝑐 𝑥 = 𝑦 (𝑥,𝑦)∈𝐸} —— 𝑥的后继节点集合
𝑝𝑟𝑒 𝑦 = 𝑥 (𝑥,𝑦)∈𝐸} —— 𝑦的前驱节点集合 𝑠𝑢𝑐 𝑥 = 𝑦 (𝑥,𝑦)∈𝐸} —— 𝑥的后继节点集合 𝑑𝑜𝑚 𝑟 ={𝑟} 𝑑𝑜𝑚 𝑦 = 𝑥∈𝑝𝑟𝑒(𝑦) 𝑑𝑜𝑚(𝑥) ∪ {𝑦} 𝑖𝑑𝑜𝑚 𝑥 =𝑖𝑑[𝑀𝑎𝑥 𝑑𝑓𝑛 𝑦 𝑦∈𝑑𝑜𝑚 𝑥 }] DAG上可以按照拓扑序计算，有环图上可以迭代计算， 𝑂(𝑉 2 )。

40 Dominator Tree 设有向图G=(V,E)，(G,r)是一个Flow Graph，则称(G,r)的子图D=(V, { (idom(i),i) | i∈V,i≠r }, r) 为(G,r)的一棵Dominator Tree。 (G,r)的Dominator Tree是一棵有向有根树，从r出发可以到达G中的所有点，并且树上的每 条边(u,v)都满足：u=idom(v)，即父节点是子节点的最近必经点。 x=idom(y)，当且仅当有向边(x,y)是Dominator Tree中的一条树枝边。 x dom y，当且仅当在Dominator Tree中存在一条从x到y的路径。 x的必经点集合dom(x)就是Dominator Tree上x的所有祖先以及x自身。

41 半必经点 半必经点（semi） 在搜索树T上点y的祖先中，通过非树枝边 可以到达y的深度最小的祖先x，称为y的 半必经点。半必经点也是唯一的，因此可 以记x=semi(y)。

42 半必经点定理 对于𝐺中的一点𝑦，考虑所有𝑥∈𝑝𝑟𝑒 𝑦 ，定义一个临时变量𝑡𝑒𝑚𝑝=+∞。
若𝑑𝑓𝑛 𝑥 <𝑑𝑓𝑛 𝑦 ，则 𝑥,𝑦 为树枝边或前向边，此时𝑡𝑒𝑚𝑝=min⁡(𝑡𝑒𝑚𝑝,𝑑𝑓𝑛[𝑥])。 若𝑑𝑓𝑛 𝑥 >𝑑𝑓𝑛 𝑦 ，则 𝑥,𝑦 为横叉边或后向边，此时∀𝑥在𝑇中的祖先𝑧，满足𝑑𝑓𝑛 𝑧 > 𝑑𝑓𝑛 𝑦 时，有𝑡𝑒𝑚𝑝=min⁡(𝑡𝑒𝑚𝑝,𝑑𝑓𝑛 𝑠𝑒𝑚𝑖 𝑧 )。 𝑠𝑒𝑚𝑖 𝑦 =𝑖𝑑[𝑡𝑒𝑚𝑝]。即在上述所有可能情况中取𝑑𝑓𝑛值最小的一种，就是𝑦的半必经点。

43 半必经点一定是必经点吗？

44 必经点定理 对于𝐺中的一点𝑥，考虑搜索树𝑇中𝑠𝑒𝑚𝑖 𝑥 到𝑥的路径上除端点之外的点构成的集合𝑝𝑎𝑡ℎ。
设𝑦=𝑖𝑑 min 𝑑𝑓𝑛 𝑠𝑒𝑚𝑖 𝑧 𝑧∈𝑝𝑎𝑡ℎ ]，即𝑝𝑎𝑡ℎ中半必经节点的时间戳最小的节点。 𝑖𝑑𝑜𝑚 𝑥 = 𝑠𝑒𝑚𝑖 𝑥 𝑠𝑒𝑚𝑖 𝑥 =𝑠𝑒𝑚𝑖(𝑦) 𝑖𝑑𝑜𝑚 𝑦 𝑠𝑒𝑚𝑖(𝑥)≠𝑠𝑒𝑚𝑖(𝑦)

45 Lengauer-Tarjan算法 Lengauer和Tarjan于1979年提出，经典Tarjan算法的进一步应用。
时间复杂度O(NlogN)或O(Nα(N))，几乎接近于线性。 基本思想： 通过DFS构建搜索树，并计算出每个节点的时间戳。 根据半必经点定理，按照时间戳从大到小的顺序计算每个节点的半必经节点。 根据必经点定理，按照时间戳从小到大的顺序，把半必经节点≠必经节点的节点进行修正。

46 使用的数据结构：并查集 在访问每个节点时，把该节点放入图的一个生成森林中。
根据半必经点定理，对于一条边(x,y)，若dfn[x]>dfn[y]，则计算semi[y]时需要考虑x的祖先 中比y的时间戳大的节点。 由于算法按照时间戳从大到小的顺序计算，此时比y的时间戳小的节点还未加入生成森林， 因此直接在生成森林中考虑x的所有祖先即可。 使用并查集维护生成森林，把dfn[semi[z]]作为z到其父节点的边的权值，在路径压缩的过 程中对每个节点维护一个变量，很容易计算z到其祖先上所有边权的最小值。

47 算法实现 procedure dfs(x is a vertex) { dfn[x]←t←t+1, id[t]←x for each y in suc[x] do if dfn[y]==0 then dfs(y), fa[dfn[y]]←dfn[x] } function get(x is a vertex):a vertex if x=anc[x] then return x y←get(anc[x]) if semi[best[x]]>semi[best[anc[x]]] then best[x]←best[anc[x]] anc[x]←y, return y suc[u] – successors of u pre[u] – predecessors of u fa[u] – DFS tree father dfn[u] – DFS order number id[u] – vertex number of dfn dom[u] – vertexes that u dominates semi[u] – semidominator idom[u] – immediate dominator anc[u] – ancestor in disjoint set best[u] – dfn of the vertex with the smallest semi in ancestor chain

48 算法实现 anc[y]←x for each z in dom[x] do { get(z) if semi[best[z]]<x then idom[z]←best[z] else idom[z]←x } empty dom[x] for i←2 step 1 until t+1 do if idom[i]≠semi[i] then idom[i]←idom[idom[i]] push i into the back of dom[idom[i]] idom[1]←0 procedure tarjan { for y←t step -1 until 1 do x←fa[y] for each z in pre[id[y]] do z←dfn[z] if z=0 then continue get(z) semi[y]←min(semi[y],semi[best[z]]) } push y into the back of dom[semi[y]]

49 例题 首先是可以用来求有向图的割点（SPOJ BIA）。 Problem：Entrapment（SPOJ EN） 冬令营讲义第124页
题目大意：有向图，求起点S到终点T的所有路径中最接近源的必经点。 Lengauer-Tarjan算法求Dominator Tree，得到S到T的必经点，找最近的一个。 也可以用网络流，拆点构图，增广两次，第二次增广能够到达的最远点就是答案。

50 有向图的桥边 给定一张Flow Graph (G,r)，若去掉图中的一条边e后，r不能到达图中的全部节点，则称e 是(G,r)的桥。
给定一张有向图G和图中的两个点S、T，若图中的一条边e处于从S到T的所有路径上，则 称e是从S到T的必经边。 有向无环图上的必经边？ 有向图(可能有环)上的桥边？ 注意在环上的边可能也是桥，因此不能简单地缩点转化为DAG。

51 有向图的桥边 有向无环图上的必经边？ 求S到每个点的路径条数CntS，每个点到T的路径条数CntT；
若边(u,v)满足CntS[u]*CntT[v]=CntS[T]，则(u,v)是从S到T的必经边； 可以对几个大质数取模做上述计算。 有向图(可能有环)上的桥边？ 在一条边u→v的中间加一个点，变成u→w→v，然后用Lengauer-Tarjan算法求有向图的割 点，若一个新加的点是割点，则对应的边是割边。

52 PKU ACM Team's Excursion
It is a traditional activity for PKU ACM Team to go hiking during the summer training camp. The coach has found a national park and acquired the map of this park. In this map, there are n intersections (numbered from 0 to n-1) connected by m one-way roads, and the map of the park is a Directed acyclic graph. The excursion will begin at a certain starting intersection s and end at a certain destination intersection t. You can find a route from intersection s to t. A road is called a "bridge" if and only if you cannot find a route from starting intersection to destination once it disappears. The other ordinary roads are not bridges so they are not dangerous at all. According to the experience of the tourists, the danger level of a "bridge" is equal to its length.

53 PKU ACM Team's Excursion
The national park provides an "express" service. The hikers can order at most two buses beforehand to help them to escape some of the most dangerous routes. Each bus can start from anywhere (any intersection or any point on any road) in the national park. But the bus is powered by electricity so it can only travel no more than q meters continuously and the passenger should get off before the electricity runs out. When the team is on a bus, the danger level along the route can be ignored. The problem is reduced to find a route from the start intersection to the end with the least sum of danger levels. On the way we can take two special buses to make our route safe. 1 ≤ n ≤ , 1 ≤ m ≤ , 0 ≤ s,t < n, s ≠ t, 1 ≤ q ≤

54 PKU ACM Team's Excursion
题目要求有向无环图中的一条危险程度最小的路径，开始节点和终止节点已经被指定。对 于一条边，当它成为“桥”的时候，这条边被标记为危险，危险程度等于边的长度。可以选 择搭乘两次车，每次连续行驶不超过q米，在车上经过的桥不计入路径的危险程度。 对于这道题目，我们首先用前面提到的计算路劲条数+取模的方法求出S到T的必经边。 由于S到T的任何一条路径都包含所有必经边，根据贪心，可以任取一条S到T的最短路。 把最短路上的点和边取出，就转化为了一个线性问题，用两段区间尽可能覆盖上面的桥。 正向、反向各扫描一遍，求出[S,x]和[x,T]上搭一次车的最小危险度，枚举切点x即可。

55 Disjoint Spanning Tree
Shannon Switching Game, Minimum Spanning Trees, Edge-disjoint Spanning Tree

56 Shannon Switching Game
Problem：Game of Connect 冬令营讲义第125页 给定一张无向图和两个特定点A和B，图中的每条边可被染色或者删除。 有两个玩家，代号分别为Short Player和Cut Player，轮流操作。 Short每次可以选择一条边染色，Cut每次可以删除一条尚未染色的边。 如果最终A和B不再连通，Cut获胜；如果最终从A到B有一条被染色的路径，Short获胜。

57 Game Time ! 通过玩这个Demo的经验，你觉得怎样做才能获胜？

58 局面与必胜策略 Shannon Switching Game只有三种局面： Short有必胜策略、Cut有必胜策略、先手有必胜策略。
Short Player有必胜策略，当且仅当图中存在一个连接A和B的子图，子图中存在两棵边不 相交的生成树。 此时如果Cut删除了一条边使得其中一棵生成树断开分成了两棵子树，Short只需要在另一 棵生成树中找到一条连接这两棵子树的边染色。 除此之外，其它必胜情况可以考虑图中是否有两棵生成树仅有一条公共边。

59 Edge Disjoint Spanning Tree
从Shannong Switching Game的必胜策略出发，我们讨论以下几个问题： Minimum Spanning Trees 问题：求带边权无向图G中k棵边不相交的生成树，并且生成树 的边权之和尽量小。 （A set of k disjoint spanning trees such-that the total value of the edges is minimum） 求无向图G中边不相交的生成树的最多个数 （A maximum number of spanning trees in G which are pairwise edge-disjoint）

60 Minimum Spanning Trees
问题概述：给定无向图G=(V,E)和一个正整数k，G中的每条边都有一个权值。求无向图G的 k棵生成树，满足生成树两两之间没有公共边，并且生成树上所有边的权值之和最小。 边不相交生成树：edge-disjoint spanning trees 边不相交生成森林：edge-disjoint spanning forest 解决问题主要在于求出这k棵生成树的边集，基本思想是按边权排序后，贪心地尝试把每 条边加入到边集中，并检测加入之后边集还能否分成k个边不相交的生成森林。 理论依据来自于拟阵(matroid)。

61 Var 𝑖 + = 𝑖 𝑚𝑜𝑑 𝑘 +1 𝐹是𝐸的一个子集，包含𝐺中的若干条边。
若𝐹能分成𝑘个集合，每个集合是𝐺的生成森林的边集，则称𝐹是独立的(𝑖𝑛𝑑𝑒𝑝𝑒𝑛𝑑𝑒𝑛𝑡)。 若𝐹是独立的，则记 𝐹 1 , 𝐹 2 ,…, 𝐹 𝑘 为𝐹分成的𝑘个边集构成的𝑘个生成森林。 若𝑒= 𝑢,𝑣 ∈𝐸 并且𝑢,𝑣在 𝐹 𝑖 中的同一棵树上，则记 𝐹 𝑖 (𝑒)为 𝐹 𝑖 中从𝑢到𝑣的路径。 在接下来的讨论中，我们不再区分生成树、森林与其边集之间的区别。

62 增广序列(Augmenting Sequence)
∀𝑖∈ 0,𝑡 ， 𝑒 𝑖 ∈𝐸 ∀𝑖∈ 1,𝑘 ， 𝑒 0 ∉ 𝐹 𝑖 ∀𝑖∈ 0,𝑡−1 ， 𝑒 𝑖+1 ∈ 𝐹 𝑖+ 𝑒 𝑖 𝑒 𝑡 的两个端点不在 𝐹 𝑡+ 的同一棵树中

63 增广(Augmentation) 给定一个增广序列 𝑒 0 , 𝑒 1 ,…, 𝑒 𝑡 ，以下两步过程称为对𝐹的一次增广(Augmentation)： ∀𝑖∈ 0,𝑡−1 ，令 𝐹 𝑖+ = 𝐹 𝑖+ ∪ 𝑒 𝑖 − 𝑒 𝑖+1 ； 令 𝐹 𝑡+ = 𝐹 𝑡+ ∪ 𝑒 𝑡 ； 对𝐹进行一次增广后，𝐹变为𝐹∪{ 𝑒 0 }。 引理1：通过增广序列对独立的边集𝐹进行增广后， 𝐹仍然独立。

64 增广的实际意义 增广的意义在于，尝试把一条新的边 𝑒 0 加入到边集𝐹中，同时维护𝐹分成的𝑘个生成森林。
把 𝑒 𝑖 加入到 𝐹 𝑖+ 中，如果 𝑒 𝑖 在 𝐹 𝑖+ 中不形成环，说明找到了一个增广序列； 否则令 𝑒 𝑖+1 为 𝑒 𝑖 在 𝐹 𝑖+ 中形成的环上的某一条边； 从 𝐹 𝑖+ 中删除 𝑒 𝑖+1 ，并对 𝑒 𝑖+1 重复以上步骤。 因此如果能找到 𝑒 0 为开头的增广序列，说明可以把 𝑒 0 加入到𝐹中，否则不行。

65

66 寻找增广序列 把𝐹中的所有边置为未标记状态，把 𝑒 0 加入队列，进行一次宽度优先搜索。 重复以下步骤直到队列为空，或者找到增广序列：
取出队头元素𝑒，设𝑖满足𝑒∈ 𝐹 𝑖 ，若𝑒不在任何 𝐹 𝑖 中(𝑒= 𝑒 0 时)，则令𝑖=0； 如果𝑒的两个端点不在 𝐹 𝑖+ 的同一棵树中（不形成环），说明找到了一个增广序列，结束； 否则把 𝐹 𝑖+ (𝑒)中所有未标记的边依次标记为𝑒并加入队尾；

67 BFS的结果 第一种情况： 如果宽搜中途结束，那么在BFS的过程中找到了 𝑒 0 开头的长度最短的增广序列。
由于每条边在加入队尾时的标记都是当时的队头，因此通过边的标记很容易复原该序列。 第二种情况： 引理2：如果宽搜由于队列为空而结束，那么𝐹∪{ 𝑒 0 }是非独立的。 换言之，这说明从 𝑒 0 出发找不到增广序列，因此 𝑒 0 不能被加入到𝐹中。

68 第二种情况的进一步思考 若宽搜由于队列为空而结束，∀𝑖∈ 1,𝑘 ，设 𝑆 𝑖 为 𝐹 𝑖 中所有被标记的边的端点构成的集合， 则有以下三条性质成立： 性质一： 𝑆 1 = 𝑆 2 =…= 𝑆 𝑘 =𝑆； 性质二：𝑆包含 𝑒 0 的两个端点； 性质三：∀𝑖∈ 1,𝑘 ， 𝐹 𝑖 中所有被标记的边构成一棵生成𝑆的子树（记为 𝑇 𝑖 ）。

69 三条性质的证明 设 𝑒 𝑖 为 𝐹 𝑖 中任意一条被标记的边。
由于未找到增广序列，所以 𝑒 𝑖 的两个端点在 𝐹 𝑖+ 的同一棵树中，并且 𝐹 𝑖+ ( 𝑒 𝑖 )上的边均被标记。 𝑆 𝑖 ⊆ 𝑆 𝑖+ 𝑆 1 ⊆ 𝑆 2 ⊆…⊆ 𝑆 𝑘 ⊆ 𝑆 1 𝑆 1 = 𝑆 2 =…= 𝑆 𝑘 =𝑆 𝑆= 𝑆 1 包含 𝑒 0 的两个端点。 性质三等价表述：若𝑢是 𝑒 0 的端点之一，则∀𝑣∈𝑆,∀𝑖∈[1,𝑘]， 𝐹 𝑖 中已标记的边连接𝑢,𝑣。 反证法，设𝑒是满足“𝑢和其端点𝑣在 𝐹 𝑖+ 中不被已标记边连接”的最早被标记的边，𝑒被标记为 𝑒′，则𝑢和𝑒′的端点𝑤在 𝐹 𝑖 中被已标记边连接。这些边均扩展了 𝐹 𝑖+ 中的一条路径，因此𝑢和 𝑤在 𝐹 𝑖+ 中也被已标记边连接。而𝑣,𝑤∈ 𝐹 𝑖+ (𝑒′)，故𝑢和𝑣在 𝐹 𝑖+ 中被已标记边连接，矛盾！

70 Clump 若一个点集𝐶被𝐹的每个生成森林 𝐹 𝑖 中的一棵子树生成，则称该点集是一个丛(Clump)。
引理3：增广不破坏已有的丛（若𝐶是𝐹的一个丛，则对𝐹增广后， 𝐶仍是一个丛）。 引理4：两个端点在同一个丛中的边一定不在增广序列中。 初始状态下， 边集𝐹为空，每个点各自是一个丛。 一次增广如果成功，则扩大了𝐹的大小；如果失败，则可以合并两个丛。 因此增广最多进行𝑂(𝑘𝑉)次。

71 并查集维护 第0个并查集维护Clump，第1~k个并查集维护k个生成森林。
𝑓𝑖𝑛𝑑 0 (𝑥)返回点𝑥所在的丛的代表节点， 𝑢𝑛𝑖𝑜𝑛 0 (𝑥,𝑦)合并𝑥和𝑦所在的丛。 𝑓𝑖𝑛𝑑 𝑖 (𝑥)返回 𝐹 𝑖 中点𝑥所在子树的树根， 𝑢𝑛𝑖𝑜𝑛 𝑖 (𝑥,𝑦)连接 𝐹 𝑖 中𝑥和𝑦所在的子树。 对每条边𝑒=(𝑢,𝑣)关联三条信息： 𝑣𝑎𝑙𝑢𝑒(𝑒)表示其边权； 𝑓𝑜𝑟𝑒𝑠𝑡 𝑒 ∈[0,𝑘]表示其所在的生成森林的编号，不属于任何生成森林时为0； 𝑙𝑎𝑏𝑒𝑙 𝑒 为标记法宽搜时𝑒的标记，未标记时为null。

72 算法整体实现 初始化𝑘+1个并查集、所有边的𝑓𝑜𝑟𝑒𝑠𝑡值置为0； 把所有边按照𝑣𝑎𝑙𝑢𝑒从小到大排序；
按顺序依次考虑每条边 𝑒 0 =(𝑢,𝑣) ，检测是否有 𝑓𝑖𝑛𝑑 0 𝑢 = 𝑓𝑖𝑛𝑑 0 (𝑣)； 若成立，则跳过这条边；否则从 𝑒 0 出发进行宽搜； 如果找不到 𝑒 0 出发的增广序列，说明𝑢和𝑣在同一个丛中，此时执行 𝑢𝑛𝑖𝑜𝑛 0 (𝑢,𝑣)； 如果取出𝑒=(𝑥,𝑦)时发现 𝑓𝑖𝑛𝑑 𝑖 𝑥 ≠ 𝑓𝑖𝑛𝑑 𝑖 (𝑦)而结束搜索，则执行 𝑢𝑛𝑖𝑜𝑛 𝑖 (𝑥,𝑦)，并重复执 行𝑠𝑤𝑎𝑝(𝑖𝑛𝑑𝑒𝑥 𝑒 ,𝑖)和赋值𝑒=𝑙𝑎𝑏𝑒𝑙(𝑒)直到𝑒=null。

73 宽搜具体实现(1) 队列清空、所有边的𝑙𝑎𝑏𝑒𝑙值置为null，把 𝑒 0 =(𝑢,𝑣)加入队列；
在每个生成森林 𝐹 𝑖 中找到𝑢所在的树 𝑇 𝑖 ，令𝑢为 𝑇 𝑖 的根并计算每个点𝑥的父节点 𝑝 𝑖 (𝑥)； 引理5：① 𝐹 𝑖 中已标记的边构成 𝑇 𝑖 的一棵包含𝑢的子树； ②当𝑒=(𝑥,𝑦)被从队头取出时， 𝑥或𝑦在 𝐹 𝑖𝑛𝑑𝑒𝑥 𝑒 + 已标记的边构成的子树中。 证明：每条被标记的边要么与𝑢相连，要么与之前已经被标记的边相连，对搜索过程中边 的标记进行归纳，引理显然正确。

74 宽搜具体实现(2) 因此我们每次取出队头元素𝑒=(𝑥,𝑦)，令𝑖=𝑖𝑛𝑑𝑒𝑥 𝑒 +；
若 𝑓𝑖𝑛𝑑 𝑖 𝑥 ≠ 𝑓𝑖𝑛𝑑 𝑖 (𝑦)，说明𝑥,𝑦在 𝐹 𝑖 的不同子树中，找到了增广序列，结束搜索； 否则令𝑧是𝑥,𝑦中满足𝑧≠𝑢并且𝑙𝑎𝑏𝑒𝑙( 𝑒 ′ =(𝑧, 𝑝 𝑖 (𝑧)))=null的点； 把边 𝑒 ′ 入队并令𝑙𝑎𝑏𝑒𝑙 𝑒 ′ =𝑒, 𝑧= 𝑝 𝑖 𝑧 ，直到𝑧=𝑢或者𝑙𝑎𝑏𝑒𝑙((𝑧, 𝑝 𝑖 (𝑧)))≠null； 重复以上步骤，直到搜索结束或者队列为空； 一次宽搜的复杂度为𝑂(𝑘𝑉)。

75 其它问题 至此我们在𝑂( 𝑘 2 𝑉 2 +𝐸𝑙𝑜𝑔𝐸)的时间内解决了Minimum Spanning Trees问题，当𝑘=2时 即可应用于Shannon Switching Game。 接下来对算法做一些修改来求无向图中边不相交生成树的最多个数： 尝试从 𝑒 0 出发进行增广时，∀𝑖=[1,𝑘]，在 𝐹 1 , 𝐹 2 ,…, 𝐹 𝑖 中BFS寻找增广序列； 如果失败，把 𝐹 𝑖 中已标记的边放回队列，不清空标记并继续在 𝐹 1 , 𝐹 2 ,…, 𝐹 𝑖+1 中寻找； 如果𝑖=𝑘时仍然失败，则 𝑒 0 成为新的生成森林 𝐹 𝑘+1 中的边，并令𝑘←𝑘+1。 对所有边增广结束后，找到最大的𝑘满足 𝐹 𝑘 是一棵树，𝑘即为所求的答案。

76 知识扩充篇 图灵机与计算复杂性理论 图灵机、递归定理、可归约性、时间复杂性与空间复杂性

77 生命科学中的一个悖论 × （1）生物都是机器； 这是现代生物学的宗旨之一，生物体可以看做是以机械方式运作的。 （2）生物都能自再生；
显然，自再生（繁殖）是生物物种的本质特征。 （3）机器都不能自再生； 设计生产线比设计它制造的东西复杂，因为生产线的设计包含其制造物品的设计。 因此没有机器能够制造自己，故机器不可能自再生。 ×

78 引入 机器可以制造自己吗？如何制造？ 请大家思考这样一个问题： 编写一段C++程序，该程序打印出自身。 （程序的代码和输出是完全一样的）
可以在纸上尝试一下……

79 抽象化 在前几天的课程中，乔明达大神给大家讲解了正则语言、DFA与NFA。
而程序设计语言中的语法大多是上下文无关文法，可以用附带一个栈的自动机——下推自 动机（PDA）来识别。 我们称一个机器的实现方法叙述为它的“描述”。 由于丘奇-图灵论题告诉我们，算法的定义等价于图灵机描述，因此我们来考虑： 制造一个图灵机，该图灵机打印出自己的描述。

80 初识图灵机 图灵机(TM)是一种通用的计算机模型，它与有穷自动机类似，但是具有无限大容量的存储 和任意访问内部数据的能力。
图灵机具有一个无限长的纸带，开始运行时带上只有输入串，其余位置为空； 图灵机具有一个双向读写头，可以纸带上左右移动，读取或者修改纸带上的信息； 图灵机预置接受和拒绝两种状态，一旦进入则立即停机，没有进入则持续运行永不停止； 与有穷自动机类似，分为确定型（DTM）和非确定型（NTM）、单带和多带等。

81 图灵机的形式化定义 𝑇𝑀=(𝑄,Σ,Γ,δ, 𝑞 0 , 𝑞 𝑎𝑐 , 𝑞 𝑟𝑒 ) 𝑄是有穷状态集； Σ是输入字符集；
Γ是纸带字符集（必须包含空格符）； δ:𝑄×Γ→𝑄×Γ×{𝐿,𝑅}是转移函数； 𝑞 0 , 𝑞 𝑎𝑐 , 𝑞 𝑟𝑒 ∈𝑄分别是初始状态、接收状态、拒绝状态，其中 𝑞 𝑎𝑐 ≠ 𝑞 𝑟𝑒 ；

82 格局与语言 设当前纸带上的内容为 𝑠 0 , 𝑠 1 , 𝑠 2 ,…, 𝑠 𝑚 ，当前状态为𝑞，读写头处于 𝑠 𝑖 位置。
把字符串𝐶= 𝑠 0 , 𝑠 1 ,…, 𝑠 𝑖−1 ,𝑞, 𝑠 𝑖 , 𝑠 𝑖+1 ,…, 𝑠 𝑚 称为它的格局。 如果格局 𝐶 1 经过一次转移可以到达 𝐶 2 ，则称 𝐶 1 产生 𝐶 2 。 对于𝑇𝑀 𝑀和输入𝑤，如果存在格局序列 𝐶 0 , 𝐶 2 ,…, 𝐶 𝑘 满足：① 𝐶 0 是𝑀在输入𝑤上的初始格局； ② 𝐶 𝑘 是接受格局；③每个 𝐶 𝑖 产生 𝐶 𝑖+1 ；则称𝑇𝑀 𝑀接受输入𝑤。 𝑀接受的字符串的集合称为𝑀识别的语言𝐿(𝑀)。

83 图灵机的运行结果 停机接受； 停机拒绝； 不停机。 对于所有输入都停机的机器称为判定器。
如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。 如果一个语言能被某一图灵机判定，则称该语言是图灵可判定的。

84 图灵机的三种描述 形式化描述 就像上面那样使用数学符号严格定义。 实现描述 使用文字叙述，精确到指出每步的情况和读写头移动的方式。
高水平描述（通常使用） 使用文字叙述，就像叙述算法那样指出图灵机执行的工作和停机条件。 机器的描述可以看做对一个对象进行编码，用<M>代表TM M的描述。

85 可计算函数 函数𝑓: Σ ∗ → Σ ∗ 是一个可计算函数，如果 有某个图灵机𝑀，使得对于任意输入𝑤， 𝑀停机，且此时只有𝑓(𝑤)出现在带上。 引理：存在可计算函数𝑞: Σ ∗ → Σ ∗ ，对任 意串𝑤，𝑞 𝑤 是𝑇𝑀 𝑃 𝑤 的描述。其中 𝑃 𝑤 打 印出𝑤，然后停机。 证明：右面的𝑇𝑀 𝐷实现了𝑞 𝑤 ，因此 𝑞 𝑤 是可计算函数。 𝑇𝑀 𝑃 𝑤 =“对于任意输入: 1)抹去输入; 2)在带上写下𝑤; 3)停机;” 𝑇𝑀 𝐷=“对于输入𝑤: 2)输出< 𝑃 𝑤 >;

86 构造自我复制机SELF 把SELF分成两部分A、B实现，A的任务是 打印出B，B的任务是打印出A，但是它们 的实现方式不同。
B是对输入w，打印q(w)和w的图灵机； A是对任意输入，均打印<B>的图灵机； 首先运行A部分，结束时纸带上出现<B>， 接着运行B部分，它打印q(<B>)=<A>， 把<A>接在<B>的前面就得到了SELF。 𝑇𝑀 𝐴= 𝑃 <𝐵> 𝑇𝑀 𝐵=“对于输入<𝑀>, 其中𝑀是𝑇𝑀: 1)计算𝑞(<𝑀>); 2)将其结果与<𝑀>合成， 组成一个完整的𝑇𝑀描述; 3)打印这个描述，然后停机;” 𝑇𝑀 𝑆𝐸𝐿𝐹=𝐴𝐵

87 递归定理 递归定理：设𝑇是计算𝑡: Σ ∗ × Σ ∗ → Σ ∗ 的一个图灵机，则存在计算𝑟: Σ ∗ → Σ ∗ 的一个图灵机𝑅， 使得对于每一个𝑤，有：𝑟 𝑤 =𝑡(<𝑅>,𝑤)。 递归定理实际上是说，如果我们想制造一个得到自己的描述并用于计算的图灵机𝑅，只需 要制造一个定理中提到的图灵机𝑇，如果我们给𝑇一张说明书和一堆原材料， 𝑇就会看着这 张说明书去在原材料上模拟说明书上的操作。这样的“模拟器”是不难制造的，当我们制造 出𝑇后，就有一个叫做“递归定理”的奇♂妙的神犇跑过来瞬间给我们制造了一个图灵机𝑅， 这个图灵机在𝑤上运行的结果，和𝑇看着<𝑅>在𝑤上运行的结果是一样的。这也就是说𝑅 跟一个得到自己的描述并用于计算的图灵机是等价的！

88 递归定理 递归定理的证明与SELF的构造类似，此处略去。 根据递归定理，以下描述在图灵机中是合法的：“得到自己的描述<M>”。
所以我们可以运用递归定理来实现𝑆𝐸𝐿𝐹的描述： 𝑇𝑀 𝑆𝐸𝐿𝐹=“对于任意输入: 1)利用递归定理得到自己的描述<𝑆𝐸𝐿𝐹>; 2)输出<𝑆𝐸𝐿𝐹>;”

89

90 可判定性 对于可判定语言，我们需要用高水平描述 给出它的一个判定器。 然而存在着不可判定的语言，即图灵机可 能不会停机。
𝐴 𝑇𝑀 ={<𝑀,𝑤>|𝑀是一个𝑇𝑀, 𝑤是一个串, 𝑀接受𝑤} 是不可判定的。 假设𝑇𝑀 𝐻判定 𝐴 𝑇𝑀 ，构造右面的图灵机 𝑇𝑀 𝐷。 𝑇𝑀 𝐷=“对于输入𝑤: 1)利用递归定理得到自己的描述<𝐷> 2)在输入<𝐷,𝑤>上运行𝐻; 3)若𝐻拒绝,则接受;若𝐻接受,则拒绝;” 如果𝑇𝑀 𝐻判定 𝐴 𝑇𝑀 ，若它接受<𝐷,𝑤>，则 说明𝑇𝑀 𝐷接受输入𝑤，而𝑇𝑀 𝐷实际上总返 回与𝐻相反的结果，即𝐷拒绝𝑤。这产生了矛 盾，因此 𝐴 𝑇𝑀 不可能被判定。

91 归约 若存在可计算函数𝑓: Σ ∗ → Σ ∗ ，对于每一 个𝑤，有𝑤∈𝐴 𝑓(𝑤)∈𝐵，则称语言𝐴映 射可归约到语言𝐵，记为𝐴 ≤ 𝑚 𝐵。 若𝐴 ≤ 𝑚 𝐵且𝐵可判定，则𝐴可判定； 若𝐴 ≤ 𝑚 𝐵且𝐴不可判定，则𝐵不可判定； 例： HALT TM ={<M,w>|M是一个TM，且 对输入w停机}是不可判定的。 假设TM R判定 HALT TM ，构造TM S判定 A TM 。 𝑇𝑀 𝑆=“在输入<𝑀,𝑤>上， 𝑀是𝑇𝑀，𝑤是串： 1)在输入<𝑀,𝑤>上运行𝑇𝑀 𝑅。 2)如果𝑅拒绝，则拒绝。 否则在𝑤上模拟𝑀直到停机。 3)若𝑀接受，则接受； 若𝑀拒绝，则拒绝。” 因此 A TM ≤ 𝑚 HALT TM ，故 HALT TM 不可判定。

92 P与NP 时间复杂性类𝑇𝐼𝑀𝐸 𝑡 𝑛 = 𝐿 存在𝑂 𝑡 𝑛 时间的单带𝐷𝑇𝑀判定语言𝐿}
时间复杂性类𝑇𝐼𝑀𝐸 𝑡 𝑛 = 𝐿 存在𝑂 𝑡 𝑛 时间的单带𝐷𝑇𝑀判定语言𝐿} 时间复杂性类𝑁𝑇𝐼𝑀𝐸 𝑡 𝑛 = 𝐿 存在𝑂 𝑡 𝑛 时间的单带𝑁𝑇𝑀判定语言𝐿} P是确定型单带图灵机在多项式时间内可判定的语言类：𝑃= 𝑘 𝑇𝐼𝑀𝐸 𝑛 𝑘 NP是非确定型单带图灵机在多项式时间内可判定的语言类：𝑁𝑃= 𝑘 𝑁𝑇𝐼𝑀𝐸 𝑛 𝑘 NP是具有多项式时间验证机的语言类。 验证：给定一个问题和一个解，检查解的正确性。（区分验证、判定、识别）

93 NP完全性 若存在多项式时间可计算函数𝑓: Σ ∗ → Σ ∗ ，对于每一个𝑤，有𝑤∈𝐴 𝑓(𝑤)∈𝐵，则称语言 𝐴多项式时间映射可归约到语言𝐵，记为𝐴 ≤ 𝑝 𝐵。 若语言𝐵∈𝑃且𝐴 ≤ 𝑝 𝐵，则𝐴∈𝑃。这意味着只要𝐵在多项式时间有解，则𝐴也有。 若一个问题是多项式时间可验证的，则称它是NP问题； 若一个问题满足所有的NP问题多项式时间可归约到它，则称它是NP-Hard问题； 同时满足上面两个条件的问题被称为NP完全问题（NPC问题）。 只要有一个NPC问题∈𝑃，那么𝑃=𝑁𝑃。

94 第一个NP完全问题 – SAT 若存在一种赋值使包含布尔变量和运算的表达式为真，则称该表达式是可满足的布尔公式。
库克-列文定理：SAT={φ|φ是可满足的布尔公式} 是NP完全的。 这个定理从图灵机的格局出发，把经历的格局写成一个矩阵，并建立若干个布尔变量 a[i,j,k]，取值为真时表示矩阵的(i,j)位置是k。然后通过构造布尔公式及其可满足性来检查 初始和接受格局是否合法、格局之间的转移是否合法。由于任何一个问题都可以用图灵机 实现，所以问题的是否有解就归约为布尔公式是否可满足。 在更多的时候，从一个已知的NPC问题出发归约到另一问题来证明其NP完全性。

95 多项式时间归约 – 3SAT 布尔变量或它的非称为文字，V连接的若干文字称为子句，^连接的若干子句称为合取范 式。每个子句都有3个文字的合取范式称为3cnf公式。 3SAT={φ|φ是可满足的3cnf公式} 是NP完全问题。 显然 3SAT∈NP，下面只要证明SAT ≤ 𝑝 3SAT。 利用分配律可以把库克-列文定理中证明SAT的布尔公式转化为等价的合取范式，然后对子 句(a1Va2V……Val)，用(a1Va2Vz1) ^ (￢z1Va3Vz2) ^ (￢z2Va4Vz3) ^……^ (￢zl-3Val-1Val)替换， 就得到了等价的3cnf公式。

96 团问题 - Clique CLIQUE={<G,k>|G是包含k团的无向图} 是NP完全的。
CLIQUE的验证机= “对输入<<G,k>,c>：1) 检查c是否为G中k个结点的集合；2) 检查G是 否包含连接c中结点的所有边；3) 若两项检查都通过，则接受，否则拒绝。” 3SAT ≤ 𝑝 CLIQUE：设φ是k个子句的公式，该归约生成<G,k>。G中的节点分为k个三元组， 三元组对应子句，节点对应文字并做相应标记。除了同一三元组内节点、相反标记的两个 节点之外都有边相连。φ可满足当且仅当G有k团。

97 PSPACE 类似地，我们还可以定义PSPACE、NPSPACE类以及它们的完全性。 P⊆PSPACE, NP⊆PSPACE.
大部分时间、空间复杂性类之间的关系还是悬而未决的，例如P是否等于NP。 更多问题还有待大家讨论和思考。

98 总结 今天上午我们解决了以下问题： 无向图割点、桥、点/边双连通分量的求法；
有向图必经点(割点)/必经边(桥)的求法——Dominator Tree与Lengauer-Tarjan算法； 边不相交生成树的相关问题，与Shannon Switching Game的必胜策略的联系； 图灵机的相关定义、描述与基本应用； 计算复杂性的初步认知；

99 谢谢大家 E-mail：lydrainbowcat@pku.edu.cn
鸣谢： CCF NOI 科学委员会 Robert E. Tarjan 复旦大学 刘炎明 北京大学 唐浩 杜宇飞 石家庄市第二中学 章玄润 最佳浏览环境： Microsoft Office 2013 Pro on Windows 8.1 Pro 谢谢大家 CCF NOI2014 Winter Camp, 2014年2月10日