Question

着急！《离散数学》两个选择题！

1.半群、群及独异点的关系是（ ）
A.{群}{独异点}{半群} B.{独异点}{半群}{群}
C.{独异点}{群}{半群} D.{半群}{群}{独异点}

2.设G是具有n个结点的无向简单图，若G中每一对结点的度数之和与n-1的关系为（ ）时，则在G中存在一条汉密尔顿路，
A．大于 B．大于等于 C．等于 D．小于

Answer 1

第二题 B
具有汉密尔顿回路的图称作汉密尔顿图。
定理1 若图G=<V,E>具有汉密尔顿回路，则对于结点集V的每个非空子集S均有 W(G-S)≤|S|成立。其中W(G-S)是G-S中连通分支数。
定理2 设G具有n个结点的简单图，如果G中每一对结点度数之和大于等于n-1，则在G中存在一条汉密尔顿路。
定理3 设G是具有n个结点的简单图。如果G中每一对结点度数之和大于等于n,则在G中存在一条汉密尔顿回路。
定义2 给定图G=<V,E>有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G’，对图G’重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为是原图G的闭包，记作C(G)。
定理4 当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。