而类似的对于某n2算法，n2=100n02 则n=10n0 ，即当计算机的速度提高100倍，就可以使n0的数值提高10倍。
如：前面我们介绍过，线性规划有多项式算法，从而可以在计算机上实现有效的求解。另外，Dijkstra算法、改良圈算法等是好算法。
但有些问题没有多项式算法，如货郎担问题（或旅行售货商问题）。
也有许多问题，虽没有多项式算法，但可以将其转化为判定问题(如果某问题的答案为是或不是,则称该问题为判定问题)。
一个判定问题D在不确定Turing机上在多项式时间内被解决是指： 对于问题D, 存在多项式P(n),使得对D的输入长为n时, 若其答案为”是”,则存在一个猜想, 对于它, 机器在P(n)时间内停机于 “YES” 状态； 若其答案是“否”, 则对于每个猜想,在P(n) 时间内Turing机皆停机于 “NO” 状态。
注：这里不确定Turing机概念中 “不确定” 三个字的含义是：上述的 “若答案为 ?是?,则存在一个猜想, 对于它, 机器停机于“YES”状态”一语中, 我们只是相信有这么一个猜想存在, 但并未给出一个确定的方法可以找到这个猜想。也许我们侥幸碰上了这么一个猜想,但这种幸运是罕见的；或者这个问题的答案是否定的, 这时, 要逐个验算猜想, 而猜想可有?P(n)?1个（?表示纸带上带符集合，输入符是带符的子集）,要用P(n)?P(n)?1时间来完成, 这是一个可怕的指数时间, 会随着n的增大而爆炸性增大, 所以用这种方法来求解, 实际上是不现实的, 也就是说, 用Turing机如此解决问题不可能实际地得出确定的答案。
不确定Turing机对于解决问题实际上是个无效的工具, 它只有理论上的价值, 借助于它, 我们可以建立 NP问题的概念.
P问题：对于一个判断问题D，存在一个多项式时间算法，解决该问题，则此类问题称为P类问题集合，记为P.
定义2-2 在多项式时间内能被不确定Turing机解决的判定问题之集合叫做NP 类判定问题集合, 记做NP。
对于上述的货郎担问题可以转化为判定问题：给出一个边长为自然数的图和一个自然数k，问是否有长度不超过k走遍所有顶点的巡回路线？
对于这个判定问题，可以在所谓不确定Turing机上找到多项式算法。于是，货郎担问题是一个NP问题。
下面介绍NP完全问题：
首先，若某问题A能在多项式时间内归结为问题B，则记为A∝B。
定义2-3：（C完全问题）考虑由判定问题组成的集合类C，若B∈C且对于任何A
８８
∈C，有A∝B，则称B为C完全问题。 显然，C完全问题?C。
定义2-4：(NP完全问题，记为CNP) 对B∈NP，若?A∈NP,A∝B，则B∈NPC。 显然, P?NP。.但P=NP是否成立?这是一个尚未解决而其意义十分深远的问题。先介绍：
定理2-5：若B∈P， A∝B，则A∈P。
由此知：(1) 一个NP完全问题∈P，则所有NP完全问题∈P。
(2) 一个NP完全问题?P 的充分必要条件是 P≠NP。
因此，能否找到一个NP问题，说明其∈P或?P（即证明P=NP或P≠NP）仍是个世界难题。
从1972年，多伦多大学 Cook找到了第一个NPC问题，陆续繁衍出大批的NPC问题，目前已达2000多个（见[6]）。 对NPC问题，目前更倾向于P不等于NP的看法，即这些问题也许根本不存在多项式时间算法。
6．树，最小生成树
定义2-5：无圈连通图称为树；只有孤立顶的树称为平凡树；每个连通片都为树的图称为林。
定理2-6：对于树，如下结论等价： ⅰ）G为树；
ⅱ）G中任二顶之间有且仅有一条路 ； ⅲ）G中无圈，且|E|=|V|-1 ； ⅳ)G连通且|E|=|V|-1 ； ⅴ)G连通，?e∈E，G-e不连通 ； ⅵ）G无圈，?e?E，且以V中点为顶，G+e恰有一圈。 定义2-6：若G1是G的子图，若V1?V,E1?E,E1?E，则称G1为G的生成子图。 若G1又是树，称G1为G的生成树。
一个图的生成图很多，如仅10个顶的完全图有1010-2（1亿）个生成树。
定理2-7：(Caylay) n个顶点的完全图的生成树共n个。
十九世纪中期，克希霍夫（Kirchhoff,1847年）在研究电网时巧妙的应用了生成树的概念；凯莱（A.Cayley,1857年）利用树的概念成功的解决了有机化学中的同分异构体。使树的理论获得发展。
求生成树可用BFS（Breadth First Search）方法。
８９
n?2算法如下：
1） 取v∈V(G)，标l(v)=0 取l=0； 2） 当所有标号为l的顶u的相关联的顶均
已标号止；否则把与u相邻的未标号的顶标以l+1，记录这些边（图2-37中用粗线，注意不重复标记）。且以l+1代l，转2）。 3） 止。
该算法终止得到的标记边即为生成树。 例15．设1，2，?，n表示n个城市。若i，j城市之间的铁路造价为Cij，设计一个线路图，使总造价最低。
即求连通（加权）图的生成树使其权最小，称最优树。
若n较小，求出所有生成树再比较找出最优树即可。若n较大，将所有生成树皆求出再比较是不现实的。因为一个完全图的生成树共有nn?2个，为幂指数函数。一般情况下，可用Kruskal 算法找出最小生成树。
Kruskal 算法（求最小生成树）
1） 选e1∈E，使?(e1)?min{?(ei),i?1,2,?,n}；
2） 若e1?ei已选好，则从E-{e1?ei}中选取ei?1，使得： ⅰ）G[{e1?ei，ei?1}] 无圈 ⅱ）求ei?1使ω（ei?1）=min{ω(e)|e∈E-{e1?ei}且{e1?ei，ei?1}无圈}；
3) 继续到第 |V|-1个e （e|E|-1）选出。
由定理2-6，边的个数=|V|-1表示图为连通图，故Kruskal 算法的结果为G的最小生成树。
定理2-8 Kruskal算法得到的生成子图为最优树。 7．迷宫，扫雪问题
迷宫问题有二类：1）从入口进入迷宫中心（有财宝，怪物，点将台）；2）在迷宫中迷路后再走出来。如神话中的英雄Theseus（瑞典王子）被绑架到迷宫中心，公主亚利阿特涅给他一团线，让他边走边放。王子最后借助这一条线指示的路线逃出。
图论提法：从图的一个顶点出发，游历图中每一条边，二次且仅二次。 下属方法是实现上述问题的有效方法：
1）Tarry算法 当到达一个交叉点v时，二件事情已知：ⅰ）与v相邻的且离开v的方向、已经走过的边的集合； ⅱ）我们初次到达v时所经过的边（进入边）。此时，
９０
233432121021图2-37
当到达v时，继续沿着一条尚未按v到v?方向走过的边（v，v?）前进，除非不得已，不要选进入边。
可以证明：按Tarry算法一定可以从v0到v0且每条边恰走二次。
2）沿墙向右拐：无圈时，沿墙向右拐不失为一种走迷宫的方法。（有圈时可能形成死循环）。
胡同?边死胡同、交叉点?顶点 图2-38
3） 纵深搜索法（DFS：Depth First Search，1973，Hopcroft&Tarjan） (1) 标志一切边 “未用过”，对每一顶v?V(G),k(v)?0,令i?0,v?s； (2) i?i?1,k(v)?i；
(3) 若v无未用过的关联边，转（5）；
(4) 选一条未用过的与v关联的边e=uv，标志e “用过了”；若k(u)≠0，转（3）；否则(k(u)=0), f(u)?v,v?u，转（2）；
(5) 若k(v)=1,止；
(6) v?f(v),转（3）；
易知DFS过程中，图的每一边恰通过二次。
再讨论例11（ AMCM—90B）扫雪车问题 分几种情况：
若只有一辆扫雪车，双行道（相对于一辆车可清扫一半路面），则可用上述算法按走迷宫的算法（由于道路不熟）。
单车道双车扫雪： 相当于 “多个邮递员的中国邮路问题”（它是一个NPC问题）：多个邮递员送信，将区域分为若干块使送信的总时间最少。
双车道双车扫雪：将街道分为二部分，使得两部分都连通且总长相等，则每车清扫的部分可以看成一个单车扫雪车问题，按上述算法扫雪即可。
但这并不总是可以的。
即使对于权为“1”的Euler图情况，要寻求等长闭行迹c1，c2使E(c1)∪E(c2)=E(G)
９１
且E(c1)∩E(c2)=Ф，W(c1)=W(c2)，被称为“Euler二等分问题”，是NPC问题，它的更特殊例子是 “PART问题”（它的最初提法：一大学分东西二区，每班住一区，问：是否存在分法使东西各区人数相等？）也是一个NPC问题。
其他情况
1． 要求每边恰通过一次，同时完工，但未必回到出发点。（一笔画）
2． 不要求同时完工，但要求最后一个完工者最早完工，且每条街道恰扫一次。
8．分工问题与偶图（二分图）
分工问题
某公司有员工x1?xn及n项工作y1?yn， 每个员工适合做其中某些工作。问能否使每一人分到一项适合工作？若否，最多几人能分配合适工作？怎样分配？（最初提法：n个姑娘，n个小伙，每个姑娘只认识一部分小伙子，问是否存在适当的方法使每一个姑娘都能和理想的小伙子成婚）。
图论中与之相关的概念是匹配。
匹配：图G的边的子集M称为G的一个匹配。若ei，ej∈M， ei ，ej不相邻，M中的一条边之二个端点叫做在M之下相配。M中的每个端点称为被M许配；G中每个顶点被M许配的，称M为完备匹配。G中无匹配M? │M?│>|M|，则称M为最大匹配。
二分图：图G称为二分图，若V（G）=X∪Y， X∩Y=?， X中顶点不相邻且Y中顶点不相邻。
完全二分图：X中每一顶与Y中任一顶相邻的二分图，记为Km，n
邻集：A?V(G)， V(G)中与A中顶相邻之顶集N(A)称为A的邻集。注：v和v自身不叫相邻。
设G1，G2为G的子图， G1∪G2(并)： G1，G2所有边组成的图；G1∩G2(交)： G1，G2公共边组成的图 ；G1－G2（差集）：从G1中去掉G2的边后得到的图，若G1中去掉一边时出现孤立点，则把该孤立点也去掉；G1?G2 ：G1∪G2－G1∩G2. (环和，对称差，也可以G1?G2记之为图2-39 )；
交替道路：从二分集G(X,Y,E)的匹配集M到E?M交替出现的路；交替树：G=(X,Y,E)
９２