如何证明奇数个顶点的二分图不存在汉密尔顿圈

首先，让我们来看一下什么是二分图和汉密尔顿圈。

二分图是指一个图的所有顶点可以被分成两个互不相交的子集，使得同一个子集内的顶点之间没有边相连。换句话说，一个二分图可以用两个集合和它们之间的边来表示。

汉密尔顿圈是指一个图中通过每个顶点恰好一次的圈。也就是说，从一个顶点开始，按照任意顺序经过所有其他顶点并回到起点。

那么如何证明奇数个顶点的二分图不存在汉密尔顿圈呢？

假设有一个奇数个顶点的二分图，并且它有一个汉密尔顿圈。我们可以将这个圈分成两部分：第一部分是所有奇数编号的顶点，第二部分是所有偶数编号的顶点。因为奇数个顶点中只有偶数个顶点与偶数个顶点之间有边相连，所以第一部分中的顶点只能与第二部分中的顶点相连。

然而，如果存在一个汉密尔顿圈，那么第一部分中的任意一个顶点都必须与第二部分中的所有顶点相连。但是，由于第一部分中的顶点只能与第二部分中的顶点相连，所以这是不可能的。

因此，我们可以得出结论：奇数个顶点的二分图不存在汉密尔顿圈。

相关问题

练习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不是哈密顿图。

二分图两个集合的点数有什么性质

在二分图中，将图中的顶点分成两个互不相交的集合，使得同一个集合内的顶点之间没有边相连，而不同集合内的顶点之间有边相连。这样的图被称为二分图，其中的两个集合分别被称为二分图的两个部分。

二分图中，两个集合的点数有以下性质：

1. 相等性：如果一个二分图的两个集合的点数相等，即两个集合中的顶点个数相同，那么这个二分图被称为完全二分图。

2. 偶数性：对于任意一个二分图，无论其两个集合的点数是奇数还是偶数，两个集合的点数之和必定是偶数。这是因为对于每条边来说，一端属于一个集合，另一端属于另一个集合，所以边的数量是偶数。

3. 最大匹配：二分图中的最大匹配是指在这个二分图中选择尽可能多的边，使得任意两条边没有公共顶点。最大匹配的边数等于二分图中两个集合中点数较小的那个集合的点数。

这些性质有助于我们在处理二分图相关问题时进行分析和求解。