论文部分内容阅读
数学归纳法在图论中的广泛应用致使图的“约简”(reduction)日益受到重视。图的“约简”是指在保持图的某种性质的前提下使图的阶数或边数减少的一系列运算的总和，图的边收缩便是其中之一。自从一九六一年W．T．Tutte用可缩边给出了3连通图的结构特征，一九八○年C．Thomassen用可缩边给出了Kuratowski定理的一个简短证明之后，图论界有许多著名专家，学者对不同的约简方法进行了有益的探索和研究，其中有W．Mader，B．Jackson,L．A．Goddyn等人的可去圈(Removablecircuits)；W．Mccuaig的可收缩3边形(contractibltriple)；KiyoshiAndo和AtsusiKaneko的双收缩对(bi-contractiblepair)，M．Kriesell的非边收缩(contractiblenon-edges)以及D．W．Barnette的可收缩圈(contractiblecircuits)．有些方式，如，已经有重要的应用。值得注意的是，上述约简方法中有许多是基于3连通图的。