问答题 带有禁止放子位置的n×n棋盘。如果每行和每列都恰有p个方格允许放子,试证明在棋盘上能够放置n个非攻击型车。
【正确答案】可写出这个棋盘对应的车-二分图G。显然G是p阶正则的,故由定理可知,存在完美匹配。
【答案解析】