З Занятие 3. Число орбит

Определения и обозначения

Орбита элемента — множество элементов, получаемых из него повторным применением заданного преобразования. Например, если 1 переходит в 2, а 2 — в 1, орбита элемента 1 состоит из 1 и 2. Это понятие нужно, чтобы объединять элементы, связанные одними и теми же переходами.

Преобразование — правило, по которому каждому элементу рассматриваемого множества сопоставляется другой элемент этого множества. Запись 1 → 2 означает, что преобразование переводит 1 в 2. Зная такое правило, можно шаг за шагом строить орбиту любого элемента.

Цикл — последовательность элементов, в которой повторное применение преобразования возвращает к исходному элементу. Например, переходы 1 → 2, 2 → 3, 3 → 1 образуют цикл (1 2 3). Цикл помогает коротко записать замкнутую орбиту и узнать её длину.

Число орбит — количество различных орбит, на которые разбивается рассматриваемое множество. Если множество распалось на циклы (1 2) и (3 4), число орбит равно двум. Этот показатель позволяет понять, сколько независимых замкнутых частей образует преобразование.

Как это устроено

Чтобы построить орбиту, начните с выбранного элемента и запишите его переход по заданному правилу. Затем примените правило к новому элементу, потом к следующему и продолжайте такую цепочку. Например, из 1 при переходах 1 → 2, 2 → 3, 3 → 1 получится последовательность 1, 2, 3, 1. Последняя единица показывает, что все элементы цикла найдены.

Если множество конечно, новые элементы не могут появляться бесконечно, поэтому какой-то элемент рано или поздно повторится. Для перестановки каждый элемент имеет единственный предшествующий элемент: переходы не сливаются в одну точку. Поэтому повторившийся элемент ведёт не к новой ветви, а к уже пройденному кругу, который в итоге возвращается к началу. Так орбита замыкается в цикл.

Две орбиты не пересекаются, потому что общий элемент связал бы их переходами. Действительно, если в обеих цепочках встретился один и тот же элемент, дальнейшее применение преобразования даст одинаковые следующие элементы. Движение назад по перестановке также совпадёт, поэтому обе цепочки можно объединить. Значит, это не две орбиты, а одна.

Чтобы найти число орбит, сначала возьмите любой элемент и полностью постройте его цикл. Отметьте все элементы этого цикла, чтобы больше не начинать с них поиск. Затем выберите любой неотмеченный элемент и повторите процедуру. Когда отмечены все элементы множества, количество построенных циклов и есть число орбит.

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

Как описывать орбиты преобразования

Заполняйте таблицу по порядку: сначала выпишите множество и переходы, затем постройте циклы. После этого сосчитайте длины и число орбит. Последняя строка служит общей проверкой: сумма длин должна совпасть с количеством элементов множества.

Разбор задач

Задача 1

На множестве {1, 2, 3, 4} задано преобразование: 1 переходит в 2, 2 — в 1, 3 — в 4, 4 — в 3. Найдём орбиты и их число. Нужно не считать отдельно каждый возможный старт, потому что элементы одного цикла описывают одну орбиту.

1. Начнём с 1: получаем 1 → 2 → 1. Значит, первая орбита — {1, 2}, её длина равна 2.
2. Элементы 1 и 2 уже отмечены, поэтому выбираем 3. Переходы имеют вид 3 → 4 → 3, значит, вторая орбита — {3, 4}, также длины 2.
3. Других неотмеченных элементов нет. Получились две орбиты, а сумма длин равна 2 + 2 = 4, то есть размеру множества.

Ответ: орбиты {1, 2} и {3, 4}; число орбит — 2.

Задача 2

На множестве {1, 2, 3, 4, 5, 6} заданы переходы 1 → 2, 2 → 3, 3 → 1, 4 → 5, 5 → 6, 6 → 4. Требуется найти длины циклов и число орбит. Удобно построить один цикл, отметить его элементы, а затем перейти к оставшимся.

1. Из 1 идём в 2, затем в 3 и возвращаемся в 1. Получаем цикл (1 2 3), его длина равна 3.
2. Элементы 1, 2 и 3 отмечены, поэтому начинаем с 4. Переходы 4 → 5 → 6 → 4 образуют цикл (4 5 6) длины 3.
3. Сумма длин равна 3 + 3 = 6. Она совпадает с числом элементов множества, значит, все элементы учтены.

Ответ: длины циклов — 3 и 3; число орбит — 2.

Задача 3

Преобразование множества {1, 2, 3, 4, 5, 6, 7, 8} задано циклами (1 3 5), (2 4), (6 7 8). В записи цикла каждый элемент переходит в следующий, а последний — в первый. Нужно указать орбиту каждого элемента и не принять разные начальные позиции за новые циклы.

1. Цикл (1 3 5) задаёт орбиту {1, 3, 5}; поэтому элементы 1, 3 и 5 принадлежат одной орбите длины 3.
2. Цикл (2 4) задаёт орбиту {2, 4}; оба элемента входят в одну орбиту длины 2.
3. Цикл (6 7 8) задаёт орбиту {6, 7, 8}; её длина равна 3. Сумма длин 3 + 2 + 3 = 8, поэтому разбиение полное.

Ответ: орбиты элементов 1, 3, 5 — {1, 3, 5}; элементов 2, 4 — {2, 4}; элементов 6, 7, 8 — {6, 7, 8}. Число орбит — 3.

Типичные ошибки

Ошибка — считать каждый стартовый элемент отдельной орбитой. Так происходит, если смотреть только на первый шаг и не замечать, что 1 и 2 ходят по одному циклу. Постройте переходы до возврата и объединяйте все элементы одного цикла в одну орбиту.

Ошибка — остановиться при первом повторении, не проверив возврат к началу. Повторившийся элемент может показаться случайной остановкой, хотя он показывает замыкание цикла. Проверьте всю цепочку и убедитесь, что повторился именно исходный элемент.

Ошибка — считать разный порядок записи разными орбитами. Записи (1 3 5), (3 5 1) и (5 1 3) описывают один и тот же круг переходов. Сравнивайте набор элементов и переходы, а не место, с которого началась запись.

Ошибка — не проверять полноту разбиения. При таком подходе можно пропустить элемент или включить его дважды. Отметьте элементы каждой орбиты и сложите длины: результат должен совпасть с размером исходного множества.

Связь с другими темами

До изучения орбит нужно уметь несколько раз применять заданное правило и читать таблицы соответствий. Эти навыки помогают внимательно прослеживать переходы и не путать исходный элемент с его образом. Полезно также уметь считать элементы в конечном множестве.

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

Что запомнить

• Орбиту получают повторным применением одного и того же преобразования.
• При перестановке конечного множества орбита замыкается в цикл.
• Орбиты одного преобразования не пересекаются.
• Каждый элемент множества входит ровно в одну орбиту.
• Число орбит — это число отдельных циклов.
• Сумма длин всех орбит равна числу элементов множества.