练习1。二分图是一组被分解为两个不相交集的图顶点，使得 同一集合内没有两个图顶点是相邻的。设G为二分图，V1和V2为 对应的顶点集。证明G不是哈密顿图。 1） 如果|V1−V2>1。 2） 如果G具有奇数个顶点。

1) 假设G是一个哈密顿图，考虑从V1中的某个顶点v1开始，沿着哈密顿回路依次经过V1中的所有顶点，最后回到v1。因为G是二分图，所以在沿着哈密顿回路从v1到v2的过程中，v2一定属于V2，然后在从v2到v3的过程中，v3一定属于V1，以此类推，最终回到v1时，最后一个顶点一定属于V2。这样，我们就找到了一个属于V2的顶点，与G是二分图矛盾。因此，假设不成立，G不是哈密顿图。

2) 假设G是一个哈密顿图，考虑从V1中的某个顶点v1开始，沿着哈密顿回路依次经过V1中的所有顶点，最后回到v1。因为G是二分图，所以在沿着哈密顿回路从v1到v2的过程中，v2一定属于V2，然后在从v2到v3的过程中，v3一定属于V1，以此类推，最终回到v1时，最后一个顶点一定属于V2。但是因为G有奇数个顶点，所以V1和V2中必有一个集合中的顶点数必须是奇数，所以最后一个顶点既属于V2，又属于V1，与G是二分图矛盾。因此，假设不成立，G不是哈密顿图。

相关问题

用python 给定两个数组1和2，输出他们的交集，并且输出的每一个数都是唯一的

可以使用set()函数将两个数组转换为集合(set)，然后使用“&”操作符求交集，最后再将交集转换回数组输出即可。示例代码如下：

arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
set1 = set(arr1)
set2 = set(arr2)
intersection = list(set1 & set2)
print(intersection)

输出结果：

[3, 4, 5]

其中，set1 & set2 是求两个集合的交集，结果仍然是一个集合。为了将结果转换为数组形式，使用了list()函数。

创建一个名为set_fun的函数，该函数可以输入两个集合并返回交集

以下是Python代码实现：

def set_fun(set_1, set_2):
    return set(set_1).intersection(set_2)

使用示例：

set_1 = {1, 2, 3, 4, 5}
set_2 = {3, 4, 5, 6, 7}
intersect = set_fun(set_1, set_2)
print(intersect)  # 输出 {3, 4, 5}

该函数接收两个集合作为参数，使用Python内置的`set()`函数将参数转换为集合类型，然后调用`intersection()`方法求交集，最终返回结果。