완전 매트릭스

Perfect matrix

수학에서 완전행렬은 다음 [1]조건을 충족하는 k-by-k 하위행렬 K가 없는 m-by-n 이진행렬이다.

  • k > 3
  • K의 행과 열의 합계는 각각 b와 같다. 여기서 b 2 2
  • 합계가 b보다 큰 K에 포함되지 않은 행으로 구성된 (m - k)-by-k 하위행렬의 행이 존재하지 않는다.

다음은 k = 5 및 b = 2인 K 서브매트릭스의 예입니다.

레퍼런스

  1. ^ D.M. 라이언, B.A.Foster, 스케줄링에 대한 정수 프로그래밍 접근법, 페이지 274, 오클랜드 대학교, 1981.