离散数学形成性考核作业（二）第 4 章 几种特殊图1．试分别构造满足下列条件的无向欧拉图（1）有偶数个结点，奇数条边．（2）有偶数个结点，偶数条边．（3）有奇数个结点，偶数条边．（4）有奇数个结点，奇数条边．2．分别构造满足下列条件的四个汉密尔顿图（1）偶数个结点，奇数条边．（2）有偶数个结点，偶数条边．（3）有奇数个结点，偶数条边．（4）有奇数个结点，奇数条边．3．试画出一种没有一条欧拉回路，但有一条汉密尔顿回路的图．4．如图 2.8 与否为欧拉图？试阐明理由．图 2.8 判断与否为欧拉图 5．如图 2.9 与否为汉密尔顿图？试阐明理由．图 2.9 判断与否为汉密尔顿图6．试分别阐明图 4.3（a）、（b）与（c）与否为平面图．图 2.10 判断与否为平面图 7．试分别求出图 2.11（a）、（b）与（c）的每个图的面的次数．图 2.11 求面的次数 8．试运用韦尔奇·鲍威尔算法分别对图 2.12（a）、（b）与（c）着色．图 2.12 图的着色9．若 G 是一种汉密尔顿图，则 G 一定是( )．A．欧拉图 B．平面图 C．连通图10．设 G 是有 n 个结点 m 条边的连通平面图，且有 k 个面，则 k 等于( )．A．m-n+2 B．n-m-2 C．n+m-2 D．m+n+211．无向连通图 G 是欧拉图的充足必要条件是_________________．12．设 G 是具有 n 个结点的简单图，若在 G 中每一对结点度数之和不小于等于________，则在 G 中存在一条汉密尔顿路．13．既有一种具有k 个奇数度结点的图，若要使图中有一条欧拉回路，至少要向图中添加_________条边．第 5 章 树及其应用1．试指出图 2.13 中那些是树，那些是森林，并阐明理由．图 2.13 习题 1 的图2．试画出图 2.14 中的一种生成树，并阐明其中的树枝、弦，以及对应生成树的补． 图 2.14 习题 2 的图3．试画出如图 2.15 的完全图 K5 的所有不一样构的生成树． 图 2.15 习题 3 的图4．试求出图 2.16 中的最小生成树及其权值． 图 2.16 习题 4 的图 5．给定一组权值为 1，2，2，3，6，7，9，12，是求出对应的一种最优树． 6．无向树 T 有 7 片树叶, 3 个 3 度结点,其他的都是 4 度结点，则 T 有（ ）个 4 度结点？ A．1 B．2 C．3 D．4 7．无向树 T 有 3 个 3 度结点,2 个 4 度结点,其他的都是树叶，则 T 有（ ）片树叶？ A．3 B．7 C．9 D．11 8．无向树 T 有 1 个 2 度结点,3 个 3 度结点,4 个 4 度结点,1 个 5 度结点,其他的都是树叶，则 T 有（ ）片树叶？ A．12 B．14 C．16 D．20 9．无向树 T 有 9 片树叶,5 个 3 度结点,其他的都是 4 度结点，则 T 有几种 4 度结点？ A．0 B．1 C．2 D．3
