Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

§ 1.1. Разбиение части плоскости на 2n ячеек

Существует несколько способов разбиения части плоскости* на 2n ячеек с помощью п фигур. Приведем некоторые из них.

Замкнутая кривая ψi без самопересечений делит плоскость на две части (ячейки) - внутреннюю и внешнюю (предполагаем, что кривая ψi - граница ячеек - не принадлежит ни одной из них), одну из ячеек (внутреннюю)_обозначим ai, другую, дополняющую аi до (части) плоскости, - āi, i = 1,...,n. Иногда в качестве - удобно использовать прямую, которая также делит плоскость на две части (ячейки).

При n = 1 в качестве можно взять окружность произвольного, но фиксированного радиуса (рис. 1.1) или прямую (рис. 1.2).

Рис. 1.1
Рис. 1.1

Рис. 1.2
Рис. 1.2

При n > 1 замкнутые кривые ψ1,...,ψn без самопересечений располагаются на плоскости так, чтобы разделить ее на 2n ячеек.

При n = 2 можно разделить плоскость на ячейки двумя окружностями (рис. 1.3) или двумя прямыми (рис. 1.4).

Рис. 1.3
Рис. 1.3

Рис. 1.4
Рис. 1.4

При n = 3 еще можно воспользоваться тремя окружностями* (рис. 1.5) или двумя прямыми и окружностью с центром в точке их; пересечения (рис. 1.6), но уже нельзя - тремя прямыми.

Рис. 1.5
Рис. 1.5

Рис. 1.6
Рис. 1.6

* (Для краткости вместо слов "часть плоскости" далее будем употреблять слово "плоскость".)

При n > 3 использовать только окружности нельзя. Действительно, предположим, что на плоскости расположены три окружности ψ1, ψ2, ψ3 так, что плоскость делится на 8 ячеек (рис. 1.5). Невозможно' расположить на этой плоскости 4-ю окружность ψ4 так, чтобы плоскость делилась на 16 ячеек, так как ψ4 (для того, чтобы каждую из имеющихся 8 ячеек разделить пополам) должна была бы пересекать ψ1, ψ2, ψ3 в 8 точках, но при любом расположении на трех окружностях 8 точек по крайней мере три из них лежат на одной окружности (рис. 1.7). Следовательно, должна была бы пересекать одну из трех ψ1, ψ2, ψ3 окружностей, не совпадая с ней не менее чем в трех точках, что невозможно.

Наибольшее число ячеек, на которое могут разбить плоскость n окружностей, равно n2 - n + 2 [22].

При n = 4 можно расположить на плоскости две прямые, окружность и эллипс так, что плоскость разделится на 2n ячеек (рис. 1.8).

Следовательно, при n = 1, 2, 3, 4 плоскость можно разделить на 2п ячеек с помощью п фигур, ограниченных кривыми без точек самопересечения. Перейдем к общему способу разбиения плоскости на 2n ячеек с помощью n фигур.

Рис. 1.7
Рис. 1.7

Рис. 1.8
Рис. 1.8

Индуктивный способ разбиения плоскости на 2n ячеек.

1. При n = 1, 2, 3 способы разбиения окружностями указаны выше (рис. 1.1, 1.3, 1.5).

2. Предположим, что при n = k, k > 3 указано такое расположение k фигур, что плоскость делится на 2k ячеек. Тогда для расположения k + 1 фигуры на этой плоскости достаточно

во-первых, выбрать незамкнутую кривую υ без точек самопересечения, т, е. незамкнутую кривую Жордана*, принадлежащую границам всех 2k ячеек и имеющую с каждой из этих границ только один общий кусок,

* (Кривая Жордана есть геометрическое место точек плоскости: х = f(t), y = g{t), где функции f(t) и g(t) непрерывны.)

во-вторых, обвести φ замкнутой кривой Жордана %+1 так, чтобы кривая %+1 проходила через все 2k ячеек и пересекала границу каждой ячейки только два раза.

Таким образом, получится такое расположение n = k + 1 фигур, что плоскость разделится на 2k+1 ячеек.

Для расположения k + 2 фигур на плоскости достаточно за φ взять кусок границы k + 1 фигуры.

Например, пусть при n = 3 плоскость разделена на 8 ячеек (рис. 1.5). Для проведения кривой ψ4 за φ можно взять дугу АВ (рис. 1.5, дуга АВ проведена жирной линией). Обведем φ замкнутой кривой Жордана ψ4 (рис. 1.9), получим n = 4. Для расположения пятой фигуры за φ можно взять кривую CDEF (рис. 1.10).

Рис. 1.9
Рис. 1.9

Рис. 1.10
Рис. 1.10

На рис. 1.9 в ячейках плоскости расположены последовательности из n (n = 4) нулей и единиц; единица на j-том месте последовательности означает принадлежность ячейки фигуре ai, нуль на j-том месте - принадлежность ячейки дополнению фигуры ау. Такие последовательности из п нулей и единиц можно воспринимать как числа в двоичной системе; в десятичной системе эти числа равны соответственно 0, 1,..., 2n - 1 (при n = 4 эти числа равны 0, 1,.., 15; см., рис. 1.10).

При индуктивном построении с ростом п площадь ячеек уменьшается.

Известны другие способы разбиения плоскости на 2n ячеек. Например, при разбиении плоскости по методу Минского - Сэлфриджа [23] площадь каждой ячейки не обязательно уменьшается с ростом n.

В методе Минского-Сэлфриджа при построении кривых ψi используются куски синусоид, период и амплитуда которых увеличиваются с ростом n: при n = 1 разбиение показано на рис. 1.11, при n = 2 - на рис. 1.12, при n = 3 - на рис. 1.13 и т. д.

Рис. 1.11
Рис. 1.11

Рис. 1.12
Рис. 1.12

Рис. 1.13
Рис. 1.13

Таблицы Венна. Очевидно, что с ростом n наглядность геометрических картинок уменьшается. Поэтому для больших n удобнее пользоваться таблицами, состоящими из 2n ячеек - таблицами Венна n переменных.

На рис. 1.14 приведена таблица Венна 5 переменных. Она содержит 32 ячейки. На левой стороне таблицы указаны все возможные комбинации фигур a1, а2 и их дополнений ā1, ā2, на верхней стороне - все возможные комбинации фигур а̄3, а̄4, а̄5 и их дополнений a3, а4, а5. Следовательно, для каждой ячейки таблицы можно однозначно определить, принадлежит она ai или āi, i = 1,..., 5; так, ячейка, расположенная на пересечении 6-го слева столбца и 2-й сверху строки (на рис. 1.14 в этой ячейке поставлена звездочка), принадлежит ā1, а2, а3, а̄4, а5.

На рис. 1.15 нриведена таблица Венна 6 переменных, в каждой ячейке которой расположена соответствующая последовательность из нулей и единиц (единица на j-том месте последовательности означает принадлежность ячейки фигуре аi, нуль на i-том месте - принадлежность ячейки дополнению фигуры aj) и десятичная запись числа, образованного этой последовательностью.

Рис. 1.14
Рис. 1.14

Рис. 1.15
Рис. 1.15

Символ Венна. Для дальнейшего несущественно, каким образом получены 2n ячеек - разбиением плоскости или построением таблицы. Поэтому введем понятие символа Венна.

Символом Венна n переменных будем называть часть плоскости, состоящую из 2n ячеек, или таблицу Венна n переменных.

Ячейки символа Венна будем нумеровать числами 0, 1, ..., 2n-1, двоичная запись каждого из которых совпадает с соответствующей последовательностью из n единиц и нулей (единица на i-том месте последовательности означает принадлежность ячейки фигуре ai, нуль на j-том месте - принадлежность ячейки дополнению фигуры aj). Так, на рис. 1.10 в ячейках поставлены их номера при n = 4, а на рис. 1.15 - при n = 6.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"