MathLabs

第6题

给定平面上的有限点集,每个点具有整数坐标。是否总能把这些点染成红色或白色,使得对每条平行于某一坐标轴的直线 LL,其上直线 LL 上白点数与红点数之差的绝对值不超过 11?
第 1/4 步:构造二分图
通俗地说

一个点自然对应一条边:它所在的行和列是两个端点。轴平行直线上的颜色平衡就变成图顶点相邻边的颜色平衡。

V=H⊔W,p=(h,w)↔hwV=H\sqcup W,\qquad p=(h,w)\leftrightarrow hw
用 K3,3 示意行列二分;顶点颜色标出两部分。
含三个行侧顶点和三个列侧顶点的完全二分图。
详细分析

对每条含点的水平线设一个顶点,对每条含点的竖直线设另一类顶点。点 (h,w)(h,w) 对应连接行顶点 hh 与列顶点 ww 的边。该图为二分图;给边染红或白就是给点染色,而每条直线的条件正是顶点条件。