中文XML论坛--离散数学欧拉图课后题网上答案有疑问

贴子主题：离散数学欧拉图课后题网上答案有疑问

本主题类别:

第八章习题4：G为欧拉图，若v0可以任意行遍当且仅当G-v0中无圈

下载的网友发的答案感觉证的不对，任意遍历指的是从该点走任何没走过的边总能有办法
遍历形成欧拉回路，网友的充分性证明仅是走了一条欧拉回路，是不对的。希望大家讨论下证法。
   我用归纳证了下充分性，不知行不。
   G为欧拉图，G-v0无圈，则v0为所有圈公共顶点，证v0是任意行遍的；
   就同证v0为n个边不交的圈的公共顶点，则v0是任意行遍的；
   n=1时任意行遍成立显然；
   设n=k时成立，则证n=k+1时成立即可；
   n=k+1时由v0出发的任意行走均可再回到v0,否则的话从v0的任意走法中止于vi（非v0），由于
  vi是偶数度，即从一边进入vi必定还有一边可以走出vi在进仍可再出，所以中止于vi是不
  可能的，由于vi的一般性，从v0的任意走法必可回到v0,将此回路拆除，剩下k个边不交
的圈，由假设知可以任意行遍，则n=k+1可以任意行遍。得证


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	93.750ms