行拉丁矩横截的一个算法

An Algorithm for Transversals in Row-Latin Rectangls

一个 m× n阶矩阵 ,其元素取自集合 { a1,a2 ,… ,ak} ,满足每一行的元素互不相同 ,称这个矩阵为基于 k的一个 m× n阶行拉丁矩 .设 R是一个 m× n阶拉丁矩 ,它的 n个不同行不同列的且互不相同的元素称为 R的横截 .当 m>2 n-2时 ,给出了一个求 m× n阶行拉丁矩横截的新方法 ,并证明了当 k>n时 ,任一个基于 k的 ( 2 n-2 )× n阶行拉丁矩有横截存在 .

An m×n row latin rectangle based on k is an m×n array R whose entries are elements of {a 1,a 2,...,a k} such that no entry occurs more than once in any row. A transversal in an m×n row latin rectangle R is a set of n distinct entries of R, no two of which are in the same row or column. We show a new algorithm for finding a transversal in an m×n row latin rectangle if m>2n-2 and prove that any (2n-2)×n row Latin rectangle based on k has a transversal if k>n.