找出图8.37所示的6X6残缺棋盘（阴影部分表示已割去的方块)的一个完全覆盖（完全覆盖是指用多米诺

考虑如图7.10所示带有禁止放子位置的棋盘B，构造与B相关的车-二分图G。找出B上6个非攻击型车的6个位置，确定G中的对应匹配。

  

把6个非攻击型车放到具有如图4.3(1)、(2)、(3)所示禁止位置的6×6棋盘上的方法数是多少?

  

  

如图x1.4所示，考查缺失右上角(面积为4ⁿ-1)的2ⁿ×2ⁿ棋盘，n≥1。

a)试证明，使用由三个1x1正方形构成、面积为3的L形积木，可以恰好覆盖此类棋盘;

b)试给出一个算法，对于任意n≥1，给出覆盖方案;

c)该算法的时间复杂度是多少?

在无向图中有一个顶点集合,如果不在该集合中的每个顶点至少与该集合中的一个顶点邻接,则称该集合是支配集.如果一个支配集的任何真子集都不是支配集,则称该支配集为最小支配集。

(a)在图8.10中找出两个不同大小的最小支配集。

(b)设棋盘的64个方块用64个顶点表示,如果两顶点对应的两个方块是在同一行，同一列或同一对角线上,则这两顶点之间有一条边。已知5个皇后能被放在棋盘上,使它们支配所有64个方块，而且5是必须的最小皇后数，再用图论名词叙述这一结论.

问题描述:8×8的国际象棋棋盘上的一只马,恰好走过除起点外的其他63个位置各一次,最后回到起点.这条路线称为马的一条Hamilton周游路线.对于给定的m×n的国际象棋棋盘,m和n均为大于5的偶数,且|m-n|≤2,试设计一个分治算法找出马的一条Hamilton周游路线.

算法设计:对于给定的偶数m,n≥6,且|m-n|≤2,计算m×n的国际象棋棋盘上马的一条Hamilton周游路线.

数据输入:由文件input.txt给出输入数据.第1行有两个正整数m和n,表示给定的国际象棋棋盘山m行,每行n个格子组成.

结果输出:将计算出的马的,Hamilton周游路线用下面的两种表达方式输出到文件output.txt.

第1种表达方式按照马步的次序给出马的Hamilton周游路线.马的每一步用所在的方格坐标(x,y)来表示.x表示行坐标,编号为0,1,...,m-1;y表示列坐标,编号为0,1...,n-1.起始方格为(0,0).

第2种表达方式在棋盘的方格中标明马到达该方格的步数.(0,0)方格为起跳步,并标明为第1步.

令h_n表示用多米诺牌和单牌(半张多米诺牌)对1×n棋盘进行完美覆盖(即没有发生重叠的完全覆盖)的方法数，其中要求任意两张多米诺牌都不相邻，找出h_n所满足的递推关系和初始条件。

一个带有禁止位置的棋盘，它具有性质：如果一个方格禁止放子，则其右边和其下边的每一个方格也禁止放子，如图7.23所示。试证明该棋盘有用多米诺牌的完美覆盖当且仅当允许放子的白格个数等于允许放子的黑格个数。这里已假定行的方向和列的方向都是黑白格相间的。

  

用红、白和蓝色对1×n棋盘方格涂色。设h_n是没有两个涂成红色的方格相邻的着色方法数。求出h_n所满足的递推关系，然后找出h_n的公式。