拓扑排序图算法sat_欧拉hamilton路教学课件(编辑修改稿)

拓扑排序图算法sat_欧拉hamilton路教学课件(编辑修改稿)内容摘要：

此 SAT问题是否有解，即可验证 S是否可以 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 118 HornSAT • 每个子句里最多有一个 positive literal • 存在多项式的构造算法： –如果每个子句都包含大于 1个变量，则所有变量取负即为解 –否则，存在包含 1个变量的子句，则这些变量的值可唯一确定，代入原式化简即可 • TOJ 2730 Horn Clauses ( ) ( )A B C B D       425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 119 欧拉路 (Euler Tour) •定义：经过图中每条 边 恰好一次的路 •如果起点和终点相同，叫做欧拉回路 •无向图存在欧拉路的条件 –如果图连通，且所有的点都是偶数度，则有欧拉回路。 –如果图连通，且恰有两点是奇数度，则有欧拉路。 且欧拉路的起止点为这两个奇数度点。 –对重边、自环的情况仍适用。 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 120 欧拉路 •有向图存在欧拉路的条件 –如果图连通，且每个点的入度等于出度，则存在欧拉回路。 –如果图连通，且恰有一点 u的出度比入度大1，另有一点 v的出度比入度小 1，其余的出度等于出度，则存在欧拉路，起点为 u，终点为 v。 –对重边、自环适用 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 121 欧拉路 •套圈算法 –任意找一个经过点 p的环 p,V1,V2,…,Vn,p。 其中每条边都是未被访问过的。 –对环上的每一个点 Vi，递归调用步骤 (1) 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 122 欧拉路 • 一个巧妙的实现： DFS一遍，把沿途的边倒序输出即可 dfs(int k) { for (每条满足 == k且未被访问的边 e) { 标记 e为己访问。 dfs()。 edge_list[t] = e。 t = t + 1。 } } 倒序输出 edge_list[ ]中的边，即为一条欧拉路 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 123 欧拉路 1 2 3 4 5 6 边结束访问的顺序为 : (2,1) (4,2) (3,4) (6,3) (5,6) (3,5) (1,3) 因此找到一条欧拉路 : 1→3→5→6→ 3→4→2→1 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 124 例题分析 • Catenyms (Waterloo Jan 03) –TOJ 1416 / POJ 2337 –题目大意：给定一组单词，问这些单词能否连成一串，使得前面一个单词的最后一个字母和后面一个单词的第一个字母相同。 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 125 例题分析 • Sample Input 6 aloha arachnid dog gopher rat tiger 3 oak maple elm • Sample Output . *** 42513。