图论第二次作业(共4页).doc

精选优质文档-倾情为你奉上图论第二次作业 一、 第四章4.3（1）画一个有Euler闭迹和Hamilton圈的图；（2）画一个有Euler闭迹但没有Hamilton圈的图；（3）画一个有Hamilton圈但没有Euler闭迹的图；（4）画一个既没有Euler闭迹也没有Hamilton圈的图；解：（1）一个有Euler闭迹和Hamilton圈的图形如下： （2）一个有Euler闭迹但没有Hamilton圈的图形如下： （3）一个有Hamilton圈但没有Euler闭迹的图形如下： （4）一个既没有Euler闭迹也没有Hamilton圈的图形如下：4.7 证明：若G没有奇点，则存在边不重的圈C1,C1,Cm,使得。证明：将中孤立点除去后的图记为，则也没有奇点，且，则含圈，在去掉的孤立点后，得图，显然仍无奇度点，且，从而含圈，如此重复下去，直到圈，且全为孤立点为止，于是得到。4.10 证明：若（1） G不是二连通图，或