用组合零点定理证明,任意偶圈都是2-可选边
时间: 2023-05-31 13:03:20 浏览: 59
首先,回顾一下组合零点定理的表述:
组合零点定理:对于一个有向图G=(V,E),如果存在一个实数函数f:V→R,使得对于任意的有向边(u,v)∈E,都有f(u)≤f(v),那么G中一定存在一条路径,使得路径上所有点的函数值都相等。
现在我们来证明任意偶圈都是2-可选边。假设G=(V,E)是一个包含偶圈C的有向图,并且C的长度为2k。我们定义一个函数f:V→R如下:
- 对于圈C上的每个点v,令f(v)=0;
- 对于圈C外的每个点v,令f(v)等于v到C上最近的点的距离。
下面我们来证明f满足组合零点定理。
首先,对于任意的有向边(u,v)∈E,我们需要证明f(u)≤f(v)。有两种情况:
- 如果(u,v)不跨越偶圈C,那么显然有f(u)≤f(v),因为u到v的路径上的所有点都离C更远或者与C上的点距离相等。
- 如果(u,v)跨越偶圈C,那么我们不妨设(u,v)是从C上的点x到C上的点y的一条有向边。此时,我们可以将偶圈C分成两条路径:从x出发到y,和从y出发到x。我们发现,在这两条路径上,除了x和y之外的所有点在f函数下的值都是相等的,因为它们离C的距离相等。而x和y的f值都是0。因此,如果我们沿着(u,v)从x到y走过去,那么u的f值和v的f值都是0,而如果我们沿着(v,u)从y到x走过去,那么u的f值和v的f值都是相等的,且大于0。因此,无论哪种情况,都有f(u)≤f(v)。
由于f满足组合零点定理,因此存在一条路径,使得路径上所有点的函数值都相等。但是我们发现,对于偶圈C上的任意一对相邻点x和y,它们的f值都是0,因此路径不可能经过偶圈C上的任何一条边。因此,偶圈C上的所有边都是可选边,即任意偶圈都是2-可选边。证毕。