Проблемы построения двухцветной линейной мозаики

Рассматривается задача о построении дискретных образов на линейном поле зрения (линейная мозаика). Показано, что задача сводится к решению системы линейных уравнений в поле вычетов по конечному модулю. Розглядається задача про побудову дискретних образів на лінійному полі зору (лінійна мозаїка). Пок...

Full description

Saved in:

Bibliographic Details
Published in:	Теорія оптимальних рішень
Date:	2010
Main Author:	Шулинок, И.Э.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2010
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/46686
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Проблемы построения двухцветной линейной мозаики / И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 126-136. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860160718931755008
author	Шулинок, И.Э.
author_facet	Шулинок, И.Э.
citation_txt	Проблемы построения двухцветной линейной мозаики / И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 126-136. — рос.
collection	DSpace DC
container_title	Теорія оптимальних рішень
description	Рассматривается задача о построении дискретных образов на линейном поле зрения (линейная мозаика). Показано, что задача сводится к решению системы линейных уравнений в поле вычетов по конечному модулю. Розглядається задача про побудову дискретних образів на лінійному полі зору (лінійна мозаїка). Показано, що задача зводиться до розв’язання системи лінійних рівнянь у полі лишків за скінченним модулем. A problem of building discrete images on linear visual field (linear mosaic) is considered. This problem may be reduced to solving a system of linear equalities in residue field on finite modulo.
first_indexed	2025-12-07T17:54:52Z
format	Article
fulltext	126 Теорія оптимальних рішень. 2010, № 9 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматривается задача о по- строении дискретных образов на линейном поле зрения (линейная мозаика). Показано, что задача сводится к решению системы линейных уравнений в поле выче- тов по конечному модулю.  И.Э. Шулинок, 2010 ÓÄÊ 519.1 È.Ý. ØÓËÈÍÎÊ ÏÐÎÁËÅÌÛ ÏÎÑÒÐÎÅÍÈß ÄÂÓÕÖÂÅÒÍÎÉ ËÈÍÅÉÍÎÉ ÌÎÇÀÈÊÈ Введение. Эта задача в том или ином виде встречается в различных областях, где ис- пользуется прямоугольная метрика. Пусть задано прямоугольное поле ( ) nmij , π=Π , со- стоящее из mnN = клеток, где n − число клеток в каждой строке, а m − число клеток в каждом столбце. Имеется множество { }psssS ,...,, 21= из p связных фигур (без повторений), каждая из которых состоит из ( )piki ,...,2,1= клеток, число горизонталь- ных клеток каждой фигуры не превышает n, вертикальных − m. Две клетки считаются связными, если они имеют одну или две об- щих вершины. Иногда, когда имеется только второе, будем говорить о сильной связности. Каждую фигуру ( )pisi ,...,2,1= логично представить в виде графа с ki вершинами, если каждую пару вершин, соответствующих связным клеткам, соединить ребром. Фигура будет связной, если связен соответствующий граф. В дальнейшем S будем называть мно- жеством шаблонов, и не будем ограничивать в общих случаях число копий каждого шаб- лона. Пусть задано множество целых чисел { }1,...,1,0 −= rQ , которое назовем множест- вом красок. Каждой клетке шаблона ( )pisi ,...,2,1= поставлена в соответствие определенная краска 0≠q , или { }0\Qq ∈ . Это задается с помощью отражения ( )pffff ,...,, 21= , где { }0\: Qsf ii → . Первоначально полагаем, что поле Π рас- крашено в цвет 0. На поле можно в допусти- мых пределах последовательно накладывать ПРОБЛЕМЫ ПОСТРОЕНИЯ ДВУХЦВЕТНОЙ ЛИНЕЙНОЙ МОЗАИКИ Теорія оптимальних рішень. 2010, № 9 127 шаблоны без ограничения на место, порядок и повторение некоторых из них. Окончательный цвет каждой клетки поля будет равен сумме цветов тех клеток всех шаблонов, которые накладывались на данную клетку, по mod r. Задача о построении дискретного образа состоит в следующем: при заданных S, Q и f найти такое семейство шаблонов и разместить их на поле таким образом, чтобы в результате получить заданную раскраску QFB →Π= : , которая называется образом или мозаикой. В зависимости от исходных данных задача может быть неразрешимой. Постановка задачи. Линейная мозаика. Для математической постановки задачи необходимо определиться с тем, как однозначно фиксировать положение произвольного шаблона на поле. Это тем более необходимо, если учитывать то обстоятельство, что любой шаблон можно размещать на плоскости кроме задан- ного, еще в трех положениях, которые получаются после поворота шаблона в плоскости на 90°, 180° и 270°. Иногда новые положения можно получить после поворота шаблона вокруг горизонтальной или вертикальной осей. Самый про- стой выход из этого – считать новое положение шаблона, отличное от заданного, новым типом шаблона. Тогда множество S расширится до { }lsssS ,...,, 21= , где каждый шаблон имеет уникальный вид независимо от места, которое он занима- ет на поле. Теперь в каждом шаблоне можно выделить одну постоянную клетку, относительно которой все остальные клетки шаблона определяются однозначно. Назовем такую клетку меткой соответствующего шаблона. Занумеруем все клет- ки поля по строкам от 1 до N. Тогда любая клетка поля ijπ будет иметь номер ( ) jinl +−= 1 ( )njmi ,...,2,1;,...,2,1 == . Если какой-то шаблон расположить на поле таким образом, чтобы его метка совпала с клеткой l, то координаты осталь- ных клеток шаблона определяются однозначно, через l. Рассмотрим пример шаблона из 9 клеток, где его метка заштрихована. РИС. 1. Шаблон с меткой Можно записать уравнение шаблона, которое состоит из координат всех его клеток, выраженных через координаты его метки l. ( )32,22,12,2,1,,1,1, +++++++++++−++= nlnlnlnlnlnlnllls . (1) Двигая горизонтально или вертикально шаблон на поле, можно найти до- пустимые пределы его положения, которые выразятся в виде ограничений на параметр l: β≤≤α l для первой строки, и ( )3−≤γ≤γ+β≤≤γ+α minln для остальных строк. Множество положений шаблона st на поле определяется множеством коор- динат его меток ( ) ( ) ( ) ( ){ } ( )LtxxxtX t M tt ,...,2,1,...,, 21 == . Каждая координата И.Э. ШУЛИНОК 128 Теорія оптимальних рішень. 2010, № 9 ( ) ( )11 −≤λ≤λ= rx t i определяет число экземпляров шаблона st, наложенных друг на друга, метки которых имеют эту координату. Заданный образ, который необходимо построить, можно определить как ( )NbbbB ,...,, 21= , где ( )NiQbi ,...,2,1=∈ . Обозначим ( )ltΘ – окрестность клетки l относительно шаблона ( )Ltst ,...,2,1= , т. е. подмножество координат ( )tX , для которых дан- ный шаблон содержит клетку l. Так же, как и уравнение шаблона (1), можно за- дать его раскраску ( ) { } ( ),,...,2,1,...,, 21 Liqqqqs iki == (2) где цвета расположены в том же порядке, что и клетки в (1). Очевидно, что в окрестность клетки l любого шаблона входит и сама клетка l. Для некоторых пар (t,l) множество ( )ltΘ может быть пустым. Учитывая все обозначения основную задачу можно свести к решению уравнений такого типа: ( ) ( ) ( )( ) ( ) ( ).,...,2,1mod 0: Nlrbqx l lt li t l t i t t =≡∑ ∑ ≠Θ Θ∈ (3) Все решения ( ) 0≠t ix определяют положение и количество тех шаблонов, кото- рые в сумме дают заданный образ B. В общем виде эта задача довольно слож- ная, так как число переменных в ней существенно превышает число уравнений. При этом возникают проблемы с определением ранга системы, что во многом зависит от типов шаблонов и множества красок. Из всех полей Π самым простым является поле, в котором 1=m , представ- ляющее одну строку из n клеток. Тогда любой шаблон состоит из последова- тельности клеток, окрашенных в цвета { }0\Q . Задачу с таким полем будем на- зывать задачей о линейной мозаике. Меткой шаблона удобно считать его левую крайнюю клетку. Координаты клеток поля определяются как числа натурального ряда 1, 2, …, n. Координаты меток шаблонов зависят от их размеров. Они пред- ставляют также натуральные числа 1, 2, …, n – kt+1, где kt – размер (длина) шаблона ( )Ltst ,...,2,1= . Множество шаблонов можно представлять как множе- ство векторов, например, ( ) ( ) ( ){ }t k tt t t qqqs ...,,, 21= , где ( ) { }0\Qq t i ∈ . Из всех задач о линейной мозаике самая простая та, где { }1,0=Q . Тогда ок- раска шаблонов единственная (цвет 1) и они отличаются друг от друга только размерами. Это позволяет представить множество шаблонов S в виде вектора, компонентами которого служат длины шаблонов. Следует заметить, что они все разные, так как одноцветный шаблон не меняет своего вида после различных преобразований в отличие от плоских шаблонов. Самым простым образом есть одна окрашенная клетка, т. е. { }ijbbB ji ≠=== ,0,1 . Будем называть такой образ единицей. Если возможно ПРОБЛЕМЫ ПОСТРОЕНИЯ ДВУХЦВЕТНОЙ ЛИНЕЙНОЙ МОЗАИКИ Теорія оптимальних рішень. 2010, № 9 129 построить такой образ для любой клетки, то комбинируя их, легко построить любой образ на строке. Определение 1. Базисом системы (1) называется наименьший набор шабло- нов, позволяющий построить единицу в любой клетке строки. Очевидно, что тривиальным базисом будет { }1=S . Для двух шаблонов s1 и s2 базис существует не всегда. Это связано с тем, что если один из них по длине больше, чем 1 2 +   n , то появляются ограничения на передвижение этого шабло- на вдоль строки, и некоторые единицы построить невозможно. Поэтому для та- кого базиса необходимо, чтобы один из них по длине был не больше 1 2 +   n . Можно указать несколько простейших базисов такого рода. Один из них имеет вид { }1, += ddS , где 1 2 1 +    << n d . На рис. 2 это показано для S(4,3). На нем шаблон s1 изображен в первой строке, s2 – во второй, т. е. поле дублируется для прозрачности построения. Внизу приводится результат сумм по 2mod раскра- сок этих шаблонов, откуда и появляется единица в соответствующей клетке по- ля. РИС. 2. Базис для шаблонов S(4,3) и n = 7 Еще один пример простейшего базиса системы представляет множество { }12,2 += kS , где k – произвольное и 1 2 1 −    ≤≤ n k . В этом случае сделать 1=jb для произвольного j можно неоднозначно с помощью нескольких шабло- нов s1 и одного шаблона s2. Для этого расположим s2 так, чтобы он покрывал клетку j, при этом координата его метки (левая крайняя клетка) ( )2modjl ≡ . Это возможно всегда, так как длина s2 меньше n, поэтому его можно сдвигать хотя бы на одну позицию вдоль поля. Затем размещаем k экземпляров шаблона s1 слева и справа от клетки j, чтобы покрыть оставшиеся клетки шаблона s2. Для произвольных значений s1 и s2 больше 2 такие построения не всегда возможны. Можно сказать, что для каждого n существует пороговое значение длин двух шаблонов, когда существует ровно один базис, а для других значений базис либо не существует, либо их несколько. И.Э. ШУЛИНОК 130 Теорія оптимальних рішень. 2010, № 9 В качестве примера рассмотрим два шаблона 8,5 21 == ss и 11=n . Соста- вим систему уравнений типа (1). При заданных параметрах метка первого шаблона, учитывая размеры поля, может принимать значения ( ) 11 =ix для 7,...,2,1=i . Аналогично, метка второго шаблона может принимать значения ( ) 12 =jx для j = 1, 2, 3, 4. Чтобы не иметь дело с верхними индексами, обозначим xi ( )7,...,2,1=i переменные для первого шаблона, а xj (j = 8, 9, 10, 11) – перемен- ные для второго шаблона. Тогда система (1) для нашего примера приобретет конкретный вид. 1 8 1 1 2 8 9 2 1 2 3 8 9 1 0 3 1 2 3 4 8 9 1 0 1 1 4 1 2 3 4 5 8 9 1 0 1 1 5 2 3 4 5 6 8 9 1 0 1 1 6 3 4 5 6 7 8 9 1 0 1 1 7 4 5 6 x x b x x x x b x x x x x x b x x x x x x x x b x x x x x x x x x b x x x x x x x x x b x x x x x x x x x b x x x ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ = + ⋅ ⋅ ⋅ ⋅ ⋅ + + ⋅ ⋅ = + + ⋅ ⋅ ⋅ ⋅ + + + ⋅ = + + + ⋅ ⋅ ⋅ + + + + = + + + + ⋅ ⋅ + + + + = + + + + ⋅ + + + + = + + + + + + + + = + + + 7 8 9 1 0 1 1 8 5 6 7 9 1 0 1 1 9 6 7 1 0 1 1 1 0 7 1 1 1 1 x x x x x b x x x x x x b x x x x b x x b + + + + = + + ⋅ + + + = + ⋅ ⋅ + + = ⋅ ⋅ ⋅ + = . (4) Если обозначить матрицу этой системы A, то решение задачи о построении линейной мозаики для двух шаблонов ( )21,ssS = сводится к решению системы сравнений с 221 −+ ss переменными ( )2modbAX ≡ . (5) Матрица A имеет специфическую структуру: она состоит из двух массивов единиц (остальные равны нулю), которые напоминают параллелограммы. Отно- сительно строк и столбцов они имеют такие координаты своих вершин: ( ) ( ) ( ) ( )[ ]1,,,1,1,,1,1 21121 −− sssss и ( ) ( ) ( ) ( )[ ]nnnssss ,,,1,,,,1 1222 − . Эту матрицу можно задать и по-другому      ≥−+≤≤ −≤−+≤≤ = случаях.остальных в0 и1если,1 ;1и1 если,1 ;21 21 sjsiji sjsjij aij Если Adet ( )2mod0 , то решение (4) запишется в виде ( )2mod 1 bAX −≡ , поэтому необходимо найти 1−A из условия ( )2mod 1 EAA ≡− . Для этого необхо- димо решить n систем простых уравнений из n неизвестных. Рассмотрим систе- му уравнений, где неизвестными являются элементы первой строки матрицы 1−A . Обозначим их ( )nyyyy ,...,, 21= . Необходимо решить систему ПРОБЛЕМЫ ПОСТРОЕНИЯ ДВУХЦВЕТНОЙ ЛИНЕЙНОЙ МОЗАИКИ Теорія оптимальних рішень. 2010, № 9 131 ( )( )2mod0,...,0,0,1≡yAT . (6) Матрица TA также имеет два массива единиц (остальные элементы равны 0), которые образуют 2 параллелограмма, но уже в транспонированном виде. Лемма 1. Детерминант матрицы А системы уравнений (4) равен 1(mod 2) тогда и только тогда, когда наибольший общий делитель чисел s1 и s2 НОД(s1,s2) ≡ 1(mod 2). Для доказательства рассмотрим матрицу А для двух шаблонов s1 и s2 и обо- значим ее А(s1,s2). В каждом из первых s2 – 1 ее столбцов находиться по s1 еди- ниц, а в каждом из оставшихся s1 – 1 столбцов находиться по s2 единиц. Попыта- емся непосредственно вычислить AA =det . Для этого разделим матрицу на ее верхние s1 строк и нижние n–s1. Затем каждую из этих частей разделим на левые s1 столбцов и правые n–s1 столбцов. Обозначим полученные подматрицы А11, А12, А21 и А22. Подматрицей А11 является треугольной, у которой наддиагональные элементы равны нулю, а остальные равны 1. В подматрице А12 все столбцы с единицами равны первым s1 – 1 столбцам подматрицы А11. Вычтем в матрице А из последних s1 – 1 столбцов первые s1 – 1 столбцы. В результате подматрица А12 превратиться в нулевую подматрицу, что можно отразить так: . 0 22 2221 11 2221 1211 A AA A AA AA A ′= ′ == (7) Это означает, ( )2moddetdetdetdet 222211 AAAA ′=′⋅= , так как ( )2mod1det 11 ≡A . А подматрица 22A′ имеет размеры ( ) ( )11 snsn −×− . В ней остались s2 – 1 – s1 столбцов, каждый из которых содержит по s1 единиц, и s1 – 1 столбцов, каждый из которых содержит по s2 – s1 единиц. Получается последова- тельный переход ( ) ( )2121 ,det,det ssAssA ′′= , где { } { }12121211 ,max;,min ssssssss −=′−=′ ; 22 2211 −=−′+′=−=′ ssssnn . В виду конечности чисел s1 и s2 это в конце концов приведет к образованию одной из матриц А(1,k) или А(0,k). Первая матрица получиться, если НОД(s1,s2) = 1. Она тождественна 1−kE , поэтому ( ) ( )2mod1,det 21 ≡ssA . Вторая – если НОД(s1,s2) = d > 1. В ней присутствуют столбцы с нулями, поэтому ( ) ( )2mod0,det 21 ≡ssA , что и требовалось доказать. Покажем это на нашем примере. ( ) →                                     →                                     = 10001000000 11001100000 11101110000 01111111000 00111111100 00010111110 00000011111 00000001111 00000000111 00000000011 00000000001 10001000000 11001100000 11101110000 11111111000 11111111100 11110111110 11110011111 11110001111 01110000111 00110000011 00010000001 8,5A И.Э. ШУЛИНОК 132 Теорія оптимальних рішень. 2010, № 9 ( ) ( ) 1 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 3 , 5 2 , 3 1 1 1 1 1 0 . 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 0 1 A A                → = → = →                     . (8) Детерминант последней матрицы равен 1(mod 2), что соответствует соотно- шению между s1 и s2, а именно НОД(5,8) = 1. Запишем теперь уравнение (6) в виде системы уравнений для нашего примера. 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9 6 7 8 9 10 7 8 9 10 11 1 2 3 4 5 6 7 8 2 3 4 5 6 1 0 0 0 0 0 0 0 y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y + + + + ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ≡ ⋅ + + + + ⋅ ⋅ ⋅ ⋅ ⋅ ≡ ⋅ ⋅ + + + + ⋅ ⋅ ⋅ ⋅ ≡ ⋅ ⋅ ⋅ + + + + ⋅ ⋅ ⋅ ≡ ⋅ ⋅ ⋅ ⋅ + + + + ⋅ ⋅ ≡ ⋅ ⋅ ⋅ ⋅ ⋅ + + + + ⋅ ≡ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + + + + ≡ + + + + + + + ⋅ ⋅ ⋅ ≡ ⋅ + + + + 7 8 9 3 4 5 6 7 8 9 10 4 5 6 7 8 9 10 11 mod 2. 0 0 0 y y y y y y y y y y y y y y y y y y y             + + + ⋅ ⋅ ≡  ⋅ ⋅ + + + + + + + + ⋅ ≡   ⋅ ⋅ ⋅ + + + + + + + + ≡  (9) Для решения этой системы уравнений в общем виде нам понадобится поня- тие числового графа. Определение 2. Числовым графом G=(X,U,F) называется математический объект, состоящий из двух множеств ( ) NxxxX n ∈= ,...,, 21 – множества вер- шин, ( ) NuuuU m ∈= ,...,, 21 – множества образующих и порождающей функции F двух аргументов. Две вершины xi и xj называются смежными, если ( ) UxxF ji ∈, . Числовой граф, у которого nNX = , а ji xxF −= , называется натуральным модульным графом (NM-графом). В матрицы системы (9) множества элементов из единиц также образуют два параллелограмма на первых s2 – 1 строках и s1 – 1 остальных строках. Прибавим по mod 2 (i – 1)-ю к i -й строке (2 ≤ i ≤ s2 – 1), затем (j – 1)-ю к j-й строке (s2 + 1 ≤ j ≤ n). В результате система уравнений (9) превратится в систему уравнений ПРОБЛЕМЫ ПОСТРОЕНИЯ ДВУХЦВЕТНОЙ ЛИНЕЙНОЙ МОЗАИКИ Теорія оптимальних рішень. 2010, № 9 133 1 2 3 4 5 1 6 2 7 3 8 4 9 5 1 0 6 1 1 1 2 3 4 5 6 7 8 1 9 2 1 0 3 1 1 1 1 0 0 0 0 0 0 0 0 0 y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y + + + + ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ≡  ⋅ ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ ⋅ ⋅ ≡ ⋅ ⋅ ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ ⋅ ≡ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ ≡ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + ⋅ ⋅ ≡ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + ⋅ ≡  ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + ≡ + + + + + + + ⋅ ⋅ ⋅ ≡ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + ⋅ ⋅ ≡ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + ⋅ ≡ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + ≡ m o d 2 .                (10) Рассмотрим теперь NM-граф G = (Y,U), где U = (5,8), а n = 11, изображен- ный на рис. 3, а. Граф отображает свойство смежности для двух вершин, соот- ветствующих двум переменным, для которых ( )2modji yy ≡ из системы (10). РИС. 3. Числовые графы для системы (10) Единственное ребро (волнистое) отображает соотношение ( )2mod161 ≡+ yy или 1y y6. В графе 11 вершин (n = s1 + s2 – 2). Известно, что NM-граф связен, если 121 +≤+ nuu . Но у нас 5 + 8 = 13 > 11 + 1. Если доба- вить вершину 12 и соответствующие ей два ребра (на рис. 3 они обозначены пунктиром), то получим связный граф. Это означает, что исходный граф несвя- зен и состоит из двух компонент. Одна компонента содержит вершину 11 21 −=−+ ssn (на рис. 3 это 7), а вторая – вершину n + 1 – s2 = s1 – 1 (на рис. 3 это 4). Одна из этих компонент разделена волнистым ребром на две части: одна часть соответствует значениям переменных ( )2mod0≡iy , а другая часть – пе- ременным ( )2mod1≡jy . Определить эти значения можно из первого и s2-го уравнений системы (10). U = (3,5) б 3 1 2 4 5 6 а U = (5,8) 1 2 3 4 5 11 12 8 9 10 6 7 И.Э. ШУЛИНОК 134 Теорія оптимальних рішень. 2010, № 9 ( )∑ = ≡ 1 1 2mod1 s i iy ; ( )∑ = ≡ 2 1 2mod0 s j jy . (11) Однако систему (9) можно еще упростить. Если подставить в нее значения из (10), то придем к системе 2mod 0 0 0 0 0 1 654 543 432 321 65432 54321           ≡++⋅⋅⋅ ≡⋅++⋅⋅ ≡⋅⋅++⋅ ≡⋅⋅⋅++ ≡++++⋅ ≡⋅++++ yyy yyy yyy yyy yyyyy yyyyy . (12) Если в (12) переместить две верхние строки вниз, то получим систему урав- нений типа (9), но для 31 =′s и 52 =′s . При этом единица в правой части нахо- дится в первой строке уравнений для 2s′ . Тем самым доказан следующий ре- зультат. Лемма 2. Систему уравнений (9) для образующих ( )21, ssS = можно свести к системе уравнений для ( )21 , ssS ′′=′ , где { }1211 ,min ssss −=′ , а { }1212 ,max ssss −=′ . Тот факт, что уравнение с единицей в правой части перемещается вниз, мы будем отмечать подчеркиванием второго шаблона, т. е. ( ) ( )2121 , ssSssS ′′′→ , или ( ) ( )2121 , ssss ′′→ . Если единица после ряда таких переходов возвращается в пер- вую строку, то подчеркивание убираем. Если в системе (12) сложить две первые строки, затем к i-й строке добавить (i + 1)-ю (3 ≤ i ≤ n – 1), то получим соотношение: ;61 yy ≠ ;41 yy = 6352 ; yyyy == . Этим значениям соответствует NM-граф на рис. 3, б. Из первых строк системы (12) получаем: 0;; 3213221 =++=≠ yyyyyyy или ( )2mod1;0 321 ≡== yyy . Подставляя эти данные в исходный граф на рис. 3, а, получим решение Y = (0,1,1,0,1,1,1,1,0,1,1). Таким образом, лемма 2 позволяет понизить размер исходной системы уравнений до такого уровня, когда решение становиться очевидным. Затем это решение подставляем в NM-граф исходной системы и получаем полное решение. Так как число указанных переходов конечно, то в результате придем к системе уравнений для таких шаблонов (2, s2) или (s1, s1 + 1). Каждый из этих случаев, в свою очередь, распадается на два в зависимости от наличия подчеркивания вто- рого шаблона. Рассмотрим каждый из них. S = (2, s2). Тогда система (9) приобретает вид: ПРОБЛЕМЫ ПОСТРОЕНИЯ ДВУХЦВЕТНОЙ ЛИНЕЙНОЙ МОЗАИКИ Теорія оптимальних рішень. 2010, № 9 135 ( ) ( ) ( ) ( ).2mod0;1,...,3,2,2mod0;2mod1 2 1 2121 ≡−=≡+≡+ ∑ = + s i iii ysiyyyy (13) Очевидно, что s2 нечетное число, иначе в изначальной системе s1 и s2 имели бы общий делитель 2, что невозможно. Поэтому ( )2mod21 yy ≠ , а остальные ( )22 >= iyyi . Из последнего уравнения следует y1 = 0, а остальные yi = 1(i > 2). ( )2,2 sS = . Система имеет вид ( ) ( ) ( ).2mod1;1,...,2,1,2mod0 2 1 21 ≡−=≡+ ∑ = + s i iii ysiyy (14) Здесь все yi = y1 (i = 2,3,..,s2). А из последнего уравнения получаем ( ) ( )212mod1 siyi ≤≤≡ . ( )1, 11 += ssS . Система имеет вид ( ) ( ) ( ) ( )∑∑ ∑ + == −+ = ≡=≡≡ 11 1 .2mod0;,...,3,2,2mod0;2mod1 1 1 1 sj ji i s i sj ji ii ysjyy (15) Вычитая из уравнений, входящих в третью сумму, уравнения второй суммы, получим решение ( )2mod0... 121 1 ≡=== −syyy . Из первого уравнения получа- ем ( )2mod1 1 ≡sy . Из первого уравнения, входящего во вторую сумму, получаем ( )2mod111 ≡+sy . Остальные ( )2mod0≡iy , ( )11 +> si . ( )1, 11 += ssS . Система приобретает вид ( )( ) ( ) ( )∑ ∑ −+ = + = =≡=≡ 11 11 1 1 11 ;,...,3,2,2mod1;,...,2,12mod0 sj ji s i ii sjysjy ( ) ( )∑ + = −=≡ 1 .1,...,3,2,2mod0 1 sj ji i sjy (16) Если из уравнений, входящих в третью сумму вычесть 11 −s нижних урав- нений, входящих в первую сумму, то получим решение: ;11 =y == 32 yy ( )2mod0... 11 ≡== −sy . Из первого уравнения следует 1 1 =sy , а из второго – 111 =+sy . Остальные ( )2mod0≡iy . Заключение. Рассмотренная задача имеет различные области применения. Это особенно относится к многоцветным мозаикам, а также к плоским мозаи- кам, о которых речь будет идти в последующих публикациях. И.Э. ШУЛИНОК 136 Теорія оптимальних рішень. 2010, № 9 І.Е. Шулінок ПРОБЛЕМИ ПОБУДОВИ ДВОКОЛЬОРОВОЇ ЛІНІЙНОЇ МОЗАЇКИ Розглядається задача про побудову дискретних образів на лінійному полі зору (лінійна мо- заїка). Показано, що задача зводиться до розв’язання системи лінійних рівнянь у полі лишків за скінченним модулем. I.E. Shulinok PROBLEMS WITH BUILDING TWO COLORS LINEAR MOSAIC A problem of building discrete images on linear visual field (linear mosaic) is considered. This prob- lem may be reduced to solving a system of linear equalities in residue field on finite modulo. Получено 17.05..2010
id	nasplib_isofts_kiev_ua-123456789-46686
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	XXXX-0013
language	Russian
last_indexed	2025-12-07T17:54:52Z
publishDate	2010
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Шулинок, И.Э. 2013-07-06T06:49:26Z 2013-07-06T06:49:26Z 2010 Проблемы построения двухцветной линейной мозаики / И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 126-136. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46686 519.1 Рассматривается задача о построении дискретных образов на линейном поле зрения (линейная мозаика). Показано, что задача сводится к решению системы линейных уравнений в поле вычетов по конечному модулю. Розглядається задача про побудову дискретних образів на лінійному полі зору (лінійна мозаїка). Показано, що задача зводиться до розв’язання системи лінійних рівнянь у полі лишків за скінченним модулем. A problem of building discrete images on linear visual field (linear mosaic) is considered. This problem may be reduced to solving a system of linear equalities in residue field on finite modulo. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Проблемы построения двухцветной линейной мозаики Проблеми побудови двокольорової лінійної мозаїки Problems with building two colors linear mosaic Article published earlier
spellingShingle	Проблемы построения двухцветной линейной мозаики Шулинок, И.Э.
title	Проблемы построения двухцветной линейной мозаики
title_alt	Проблеми побудови двокольорової лінійної мозаїки Problems with building two colors linear mosaic
title_full	Проблемы построения двухцветной линейной мозаики
title_fullStr	Проблемы построения двухцветной линейной мозаики
title_full_unstemmed	Проблемы построения двухцветной линейной мозаики
title_short	Проблемы построения двухцветной линейной мозаики
title_sort	проблемы построения двухцветной линейной мозаики
url	https://nasplib.isofts.kiev.ua/handle/123456789/46686
work_keys_str_mv	AT šulinokié problemypostroeniâdvuhcvetnoilineinoimozaiki AT šulinokié problemipobudovidvokolʹorovoílíníinoímozaíki AT šulinokié problemswithbuildingtwocolorslinearmosaic

Проблемы построения двухцветной линейной мозаики

Institution

Similar Items