Хроматические номера прямоугольников | Статья в журнале «Молодой ученый»

Автор:

Рубрика: Математика

Опубликовано в Молодой учёный №12 (116) июнь-2 2016 г.

Дата публикации: 18.06.2016

Статья просмотрена: 97 раз

Библиографическое описание:

Алиев М. А. Хроматические номера прямоугольников // Молодой ученый. — 2016. — №12. — С. 3-7. — URL https://moluch.ru/archive/116/31908/ (дата обращения: 14.12.2018).



Данная работа посвящена исследованию хроматических номеров и нахождению минимальных раскрасок. Похожая тема была представлена на Колмогоровских чтениях в 2005 году. Тогда в совместной работе Веры и Елены Бушмановых были найдены хроматические номера всех тетра- и пентамино. Задача, являющаяся частным случаем этой работы, была представлена на Санкт-Петербургской городской олимпиаде в 2010 году.

Тема хроматических номеров и минимальных раскрасок породила много открытых вопросов, большинство из которых не решены до сих пор. В частности, оказалось, что даже нахождение хроматических номеров прямоугольников представляет собой весьма сложную и содержательную задачу. В данной работе найдены хроматические номера «широких» прямоугольников, т. е. тех, у которых отношение большей стороны к меньшей не превосходит двух.

Постановка и решение задачи

Определение: Рассмотрим бесконечную клетчатую плоскость, раскрашенную в k цветов, и клетчатую фигурку (полимино) X. Раскраску будем считать правильной, если она обладает следующим свойством: как бы мы ни расположили данную фигуру X на плоскости (по клеточкам), цвета клеток, которые ограничены фигурой X, будут различными. Наименьшее такое k будем называть хроматическим номером фигуры X (обозначаем cr(X)), а соответствующую раскраску назовём минимальной.

Лемма 1: Если фигура X содержится в фигуре Y, то cr(X)cr(Y)

Доказательство: (Бушмановы) Возьмем минимальную, подходящую для Y раскраску. Допустим, что эта раскраска не подходит для фигурки X. Значит, есть какая-то фигурка, X не покрашенная в разные цвета, но этой фигурке соответствует фигурка Y, которую можно наложить на фигурку X, тогда получается, что эта фигурка Y покрашена не в разные цвета. Это противоречит тому, что мы взяли подходящую для Y раскраску.

Замечание: Хроматический номер прямоугольника не меньше количества клеток в прямоугольнике, т. е. .

Следующая теорема отвечает на вопрос, в каких случаях вышеупомянутое неравенство обращается в равенство.

Теорема 1: Хроматический номер прямоугольника (где m и n — стороны прямоугольника) имеют те и только те прямоугольники, у которых одна из сторон кратна другой.

Доказательство: (Карашевич) Пусть дан прямоугольник вида . Покажем, что для него существует раскраска. Заметим, что все цвета равноправны. Пусть каждой краске соответствует число, тогда произвольно заполним прямоугольник числами от. Теперь разобьём наш прямоугольник на квадратов , пронумеруем квадраты числами от , затем ответим на вопрос задачи для полоски (см. рис. 1), теперь в пронумерованные квадраты вставим числа соответствующие номеру квадрата (см. пример на рис. 2 и рис. 3, где ). Получилась нужная раскраска.


Рис. 1

Рис. 2 Рис. 3

Если же прямоугольник имеет другой вид то для него раскраски не существует. Пусть большая сторона лежит по вертикали, тогда, нумеруя краски числами по строкам, получим, что все числа в -ом столбце кратны . Сдвинув наш прямоугольник вправо на одну клетку, легко понять, что все числа из первого столбца совпадают со всеми числами из нового (последнего) столбца. Построим новый прямоугольник, совпадающий левым верхним углом с первым прямоугольником, большая сторона которого лежит по горизонтали. Заметим, что в этом прямоугольнике в каждом -ом столбце содержаться числа кратные r, но так как по горизонтали таких чисел , а в первом прямоугольнике значит, раскраска некорректна (см. рис. 4).

Рис. 4

Теорема 2: Если в прямоугольнике отношение большей стороны к меньшей меньше , но больше , то хроматический номер данной фигуры равен 2, где — длина меньшей стороны, т.e. если , то

Доказательство: Разобьем наш прямоугольник на блоки, как показано на рис. 5 (жирными линиями выделен исходный прямоугольник):

Рис.5

В данном случае мы просто переворачиваем наш прямоугольник четыре раза и полученные части выделяем в блоки. Блоки А, В, Е, D, F, G — образуют изначальный прямоугольник. Рассмотрим прямоугольник С, все цвета в этом блоке не совпадают с цветами исходного прямоугольника. Теперь рассмотрим прямоугольник А+. Он не может иметь общих цветов с прямоугольниками D, B, E, F, G, C. Из этого следует, что в прямоугольнике А+ могут быть только цвета из блока А либо новые цвета. Также рассмотрим прямоугольник В+. Он не может иметь общих цветов с прямоугольниками A, D, E, F, G, C. Аналогично в В+ должны быть цвета из В либо новые. Теперь посмотрим на самый правый блок — это блок Е, с возможно какими-то новыми цветами. Под ним будет располагаться блок D (с возможно какими-то новыми цветами). И наконец, рассмотрим блок, находящийся под блоком С и по размерам равный блоку F. В нем (с учетом уже прибавленных) в сумме новых цветов будет столько же, сколько и в блоке F. Теперь мы можем считать, что у нас появился новый блок (назовем его Н), по размерам равный блоку F.

Теперь посчитаем, сколько всего цветов у нас затрачено:

+ +

Получили, что у нашего прямоугольника хроматический номер не менее чем у прямоугольника . Исходный же прямоугольник помещается в прямоугольник . По лемме хроматический номер меньшего прямоугольника не больше хроматического номера большего прямоугольника. Из этого следует, что cr(n, m) строго равен хроматическому номеру прямоугольника . По теореме 1 хроматический номер в точности равен . На данной картинке мы использовали, что блок Е+ «длиннее», чем блок D, т. е. В противоположном случае утверждение про блок Н неверно. Таким образом, теорема верна при условии

. Доказано.

Все раскраски, возникающие в работе, построены по следующему принципу. Дана координатная плоскость (точки с целочисленными координатами соответствуют центрам клеток). Покрасим клетку (0,0) в первый цвет. Возьмем два вектора а = (x1,y1) и b = (x2, y2). Покрасим клетки в этот же цвет, где k, l — целые числа. Остальные цвета покрасим сдвигом на вектор относительно первого цвета. Количество цветов в этой раскраске равно площади параллелограмма, образованного векторами .

Лемма 2: площадь параллелограмма, образованного двумя векторами (x1,y1) и (x2,y2) равна |x2y1 — x1y2|.

Доказательство: Рассмотрим параллелограмм (см. рис. 6), образованный двумя векторами (x1,y1) и (x2,y2): Sпараллелограмма = (x1+x2)(y1+y2) — x1y2 — x1y2 — x2y2 — x1y1 = = x1y1 + x2y1 + x1y2 + x2y2 — x1y2 — -x1y2 — x2y2 — x1y1 = x2y1 — x1y2 Что и требовалось доказать.

Рис. 6

Теорема 3: Если в прямоугольнике отношение большей стороны к меньшей меньше 3/2, но больше 1, то хроматический номер данной фигуры равен , где — длина большей стороны, а — длина меньшей, то есть если , то .

Доказательство:Найдем такие целые , что . Буквами A, B, C, D, E, F обозначим наборы различных цветов, которые должны быть в искомой раскраске (см. рис.7).

Рис.7

Повернём исходный прямоугольник на 90 градусов относительно левого верхнего угла. В квадрате C+ могут быть только цвета С или новые (их мы обозначаем как +) Аналогично выясняем для прямоугольника A+. Вследствие этих двух поворотов в прямоугольнике G новый цвет, который мы обозначимc как G. В прямоугольнике D+ может быть либо цвет D, либо новый. В прямоугольнике E+ может быть либо цвет E, либо новый. Теперь рассмотрим самый нижний прямоугольник.

Рис.8

В нем может быть только новый цвет и цвета, которые есть в В, но нет в В+.

Получается, что кол-во цветов, нужных для раскраски плоскости не менее

=

Из того что следует, что ,

=

Докажем, что их достаточно. Рассмотрим координатную плоскость. Покрасим целые точки цветами. Пусть в точках A(0,0), B(n,n), C(m+n,m), D(m,m-n) находится цвет G (см. рис. 8). Заметим, что на плоскости не существует прямоугольников , содержащих два цвета G. Тогда кол-во различных цветов равно площади параллелограмма ABCD. . Что и требовалось доказать.

Итог

В данной работе найдены хроматические номера «широких» прямоугольников, т. е. тех, у которых отношение большей стороны к меньшей не превосходит двух. Задача разбивается на два случая. Если в прямоугольнике отношение большей стороны к меньшей меньше 2, но больше 3/2, то хроматический номер данной фигуры равен , где — длина меньшей стороны. Для прямоугольников, у которых отношение большей стороны к меньшей меньше 3/2, но больше 1, хроматический номер равен , где — длина большей стороны, а — длина меньшей.

Основные термины (генерируются автоматически): цвет, прямоугольник, большая сторона, хроматический номер, раскраска, хроматический номер прямоугольника, блок, площадь параллелограмма, исходный прямоугольник, число.


Похожие статьи

Занятие «Раскраски графов» факультативного курса «Элементы...

Минимальное число цветов, требующихся для раскраски графа, называют хроматическим числом.

То есть хроматический полином нашего исходного графа (рис.7) раскладывается на сумму двух хроматических полиномов (5)

Структура разбиений прямоугольников на Т-тетрамино

Хроматические номера прямоугольников.

Хроматические номера прямоугольников. Структура численного диапазона обобщенной модели Фридрихса.

Метод обнаружения автомобилей на аэрокосмических снимках

Обозначим три (красную, зелёную и синюю) цветовые компоненты исходных точек как , , , составленный из них вектор цвета .

Область может иметь от одного до неопределённо большого (ограниченного сверху количеством точек изображения) числа соседей.

Вычисление площадей фигур, изображенных на клетчатой бумаге

Номера журнала.

Площадь большого прямоугольника равна , прямоугольника, расположенного внутри — , площади «лишних» треугольников — , , тогда площадь искомой фигуры .

Обработка и сегментация тепловизионных изображений

2) среднеарифметическим значением цветовых составляющих трёх каналов: (2). 3) Быстрым: выполнять алгоритм с пикселями зеленого цвета

Обработка изображения данным фильтром 11×11 предполагает большое число операций умножения, а в данной матрице присутствуют и...

Исследование листа Мёбиуса с точки зрения математики

Хроматическое число — это максимальное число областей можно поделить поверхность так, что каждая будет иметь общую границу со всеми другими. Если по-разному выкрасить эти области, то любой цвет должен соседствовать со всеми остальными [5].

Алиев Мирза Али оглы — Информация об авторе

Хроматические номера прямоугольников. №12 (116) июнь-2 2016 г. Авторы: Алиев Мирза Али оглы. Рубрика: Математика. Страницы: 3-7.

Рациональный выбор вида компьютерной графики

Номера журнала.

Число цветов, в которые можно раскрасить отдельный пиксель

В векторной графике базовым элементом изображения выступает линия и все изображения состоят из простых объектов — дуг, окружностей, эллипсов, прямоугольников, прямых линий...

Дидактические игры, как средство сенсорного воспитания...

Можно дать детям задание образовать прямоугольник, каждая сторона которого – дети с фонариками одного цвета.

Раздаточный материал: по три круга и овала разных цветов и размеров, по 2 больших

На каждом конвейере изготовляют одинаковое число изделий.

Занятие «Раскраски графов» факультативного курса «Элементы...

Минимальное число цветов, требующихся для раскраски графа, называют хроматическим числом.

То есть хроматический полином нашего исходного графа (рис.7) раскладывается на сумму двух хроматических полиномов (5)

Структура разбиений прямоугольников на Т-тетрамино

Хроматические номера прямоугольников.

Хроматические номера прямоугольников. Структура численного диапазона обобщенной модели Фридрихса.

Метод обнаружения автомобилей на аэрокосмических снимках

Обозначим три (красную, зелёную и синюю) цветовые компоненты исходных точек как , , , составленный из них вектор цвета .

Область может иметь от одного до неопределённо большого (ограниченного сверху количеством точек изображения) числа соседей.

Вычисление площадей фигур, изображенных на клетчатой бумаге

Номера журнала.

Площадь большого прямоугольника равна , прямоугольника, расположенного внутри — , площади «лишних» треугольников — , , тогда площадь искомой фигуры .

Обработка и сегментация тепловизионных изображений

2) среднеарифметическим значением цветовых составляющих трёх каналов: (2). 3) Быстрым: выполнять алгоритм с пикселями зеленого цвета

Обработка изображения данным фильтром 11×11 предполагает большое число операций умножения, а в данной матрице присутствуют и...

Исследование листа Мёбиуса с точки зрения математики

Хроматическое число — это максимальное число областей можно поделить поверхность так, что каждая будет иметь общую границу со всеми другими. Если по-разному выкрасить эти области, то любой цвет должен соседствовать со всеми остальными [5].

Алиев Мирза Али оглы — Информация об авторе

Хроматические номера прямоугольников. №12 (116) июнь-2 2016 г. Авторы: Алиев Мирза Али оглы. Рубрика: Математика. Страницы: 3-7.

Рациональный выбор вида компьютерной графики

Номера журнала.

Число цветов, в которые можно раскрасить отдельный пиксель

В векторной графике базовым элементом изображения выступает линия и все изображения состоят из простых объектов — дуг, окружностей, эллипсов, прямоугольников, прямых линий...

Дидактические игры, как средство сенсорного воспитания...

Можно дать детям задание образовать прямоугольник, каждая сторона которого – дети с фонариками одного цвета.

Раздаточный материал: по три круга и овала разных цветов и размеров, по 2 больших

На каждом конвейере изготовляют одинаковое число изделий.

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Занятие «Раскраски графов» факультативного курса «Элементы...

Минимальное число цветов, требующихся для раскраски графа, называют хроматическим числом.

То есть хроматический полином нашего исходного графа (рис.7) раскладывается на сумму двух хроматических полиномов (5)

Структура разбиений прямоугольников на Т-тетрамино

Хроматические номера прямоугольников.

Хроматические номера прямоугольников. Структура численного диапазона обобщенной модели Фридрихса.

Метод обнаружения автомобилей на аэрокосмических снимках

Обозначим три (красную, зелёную и синюю) цветовые компоненты исходных точек как , , , составленный из них вектор цвета .

Область может иметь от одного до неопределённо большого (ограниченного сверху количеством точек изображения) числа соседей.

Вычисление площадей фигур, изображенных на клетчатой бумаге

Номера журнала.

Площадь большого прямоугольника равна , прямоугольника, расположенного внутри — , площади «лишних» треугольников — , , тогда площадь искомой фигуры .

Обработка и сегментация тепловизионных изображений

2) среднеарифметическим значением цветовых составляющих трёх каналов: (2). 3) Быстрым: выполнять алгоритм с пикселями зеленого цвета

Обработка изображения данным фильтром 11×11 предполагает большое число операций умножения, а в данной матрице присутствуют и...

Исследование листа Мёбиуса с точки зрения математики

Хроматическое число — это максимальное число областей можно поделить поверхность так, что каждая будет иметь общую границу со всеми другими. Если по-разному выкрасить эти области, то любой цвет должен соседствовать со всеми остальными [5].

Алиев Мирза Али оглы — Информация об авторе

Хроматические номера прямоугольников. №12 (116) июнь-2 2016 г. Авторы: Алиев Мирза Али оглы. Рубрика: Математика. Страницы: 3-7.

Рациональный выбор вида компьютерной графики

Номера журнала.

Число цветов, в которые можно раскрасить отдельный пиксель

В векторной графике базовым элементом изображения выступает линия и все изображения состоят из простых объектов — дуг, окружностей, эллипсов, прямоугольников, прямых линий...

Дидактические игры, как средство сенсорного воспитания...

Можно дать детям задание образовать прямоугольник, каждая сторона которого – дети с фонариками одного цвета.

Раздаточный материал: по три круга и овала разных цветов и размеров, по 2 больших

На каждом конвейере изготовляют одинаковое число изделий.

Занятие «Раскраски графов» факультативного курса «Элементы...

Минимальное число цветов, требующихся для раскраски графа, называют хроматическим числом.

То есть хроматический полином нашего исходного графа (рис.7) раскладывается на сумму двух хроматических полиномов (5)

Структура разбиений прямоугольников на Т-тетрамино

Хроматические номера прямоугольников.

Хроматические номера прямоугольников. Структура численного диапазона обобщенной модели Фридрихса.

Метод обнаружения автомобилей на аэрокосмических снимках

Обозначим три (красную, зелёную и синюю) цветовые компоненты исходных точек как , , , составленный из них вектор цвета .

Область может иметь от одного до неопределённо большого (ограниченного сверху количеством точек изображения) числа соседей.

Вычисление площадей фигур, изображенных на клетчатой бумаге

Номера журнала.

Площадь большого прямоугольника равна , прямоугольника, расположенного внутри — , площади «лишних» треугольников — , , тогда площадь искомой фигуры .

Обработка и сегментация тепловизионных изображений

2) среднеарифметическим значением цветовых составляющих трёх каналов: (2). 3) Быстрым: выполнять алгоритм с пикселями зеленого цвета

Обработка изображения данным фильтром 11×11 предполагает большое число операций умножения, а в данной матрице присутствуют и...

Исследование листа Мёбиуса с точки зрения математики

Хроматическое число — это максимальное число областей можно поделить поверхность так, что каждая будет иметь общую границу со всеми другими. Если по-разному выкрасить эти области, то любой цвет должен соседствовать со всеми остальными [5].

Алиев Мирза Али оглы — Информация об авторе

Хроматические номера прямоугольников. №12 (116) июнь-2 2016 г. Авторы: Алиев Мирза Али оглы. Рубрика: Математика. Страницы: 3-7.

Рациональный выбор вида компьютерной графики

Номера журнала.

Число цветов, в которые можно раскрасить отдельный пиксель

В векторной графике базовым элементом изображения выступает линия и все изображения состоят из простых объектов — дуг, окружностей, эллипсов, прямоугольников, прямых линий...

Дидактические игры, как средство сенсорного воспитания...

Можно дать детям задание образовать прямоугольник, каждая сторона которого – дети с фонариками одного цвета.

Раздаточный материал: по три круга и овала разных цветов и размеров, по 2 больших

На каждом конвейере изготовляют одинаковое число изделий.

Задать вопрос