 | ||
|
| ||
|
| ||
|
| ||
|
| ||
|
| ||
|
| ||
|
| ||
Руководители проекта:
Березин А.В.
Келлин Н.С.
Участники проекта, в разное время принимавшие участие в нем:
Вабищевич Н.
Кругляков М.
Воронцов А.
Забегаев А.
Бархота А.
Меркулова Е.
Кулага В.
Корнилина А. и многие другие.
В отличие от многих других, данный проект наработал результаты, обладающие реальной научной ценностью. Поэтому здесь информация из отдельных отчётов участников перемешана и изложена в логическом порядке, как в учебнике. Иначе просто ничего не понять. Необходимый иллюстративный материал по возможности представлен в формате апплета 'Ломаные', дабы избежать нагромождения мелких, отвратительно многочисленных гифов.
Сразу должен предупредить, что я не претендую на сколько-нибудь полное знание развитой проектом теории ломаных, поэтому данный текст - не более чем введение. Каждому из участников придется либо мириться с таким отчетом, либо писать свой, имея в виду, что вербальная запись потока сознания недостаточна для столь высоких материй.
ИСН
ОПРЕДЕЛЕНИЯ:
Проектная ломаная (далее просто ломаная) - не менее чем 3-х звенная
замкнутая ломаная, каждая точка которой принадлежит не более чем 2-м ее
звеньям.
Ломаная вида (n,m) - n-звенная проектная ломаная, в которой каждое
звено помимо концов имеет m пересечений. Далее здесь рассматриваются
ломаные вида (n,1).
Нумерация ломаной - матрица m*n такая, что на месте (i,j) стоит номер
ребра пересекающего j-тое в i-той точке по направлению обхода. Для ломаной
(n,1) это одна строка.
Задача: исследовать все замкнутые ломаные вида (n,m), где n - количество звеньев, m - количество самопересечений на одно звено.
Подзадачи:
Указать, для каких n и m существуют такие ломаные;
Определить их количество или хотя бы оценить его асимптотику скорости
роста в зависимости от n;
Описать и классифицировать все ломаные для небольших значений n;
Найти критерий эквивалентности ломаных;
Придумать способ кодирования ломаных;
И способ построения ломаной по ее коду.
Особенно глубоко была рассмотрена задача о ломаных вида (n,1).
Прежде всего нужно как-то отсеять ломаные, которые можно считать одинаковыми. Для этого занумеруем ломаную, начиная с некоторого звена в некотором направлении. Если всего в ломаной n звеньев, то мы можем получить 2n (по одной в каждую сторону, начиная с каждого звена) нумераций (см. опр.), некоторые из которых совпадут. Если для двух ломаных эти множества эквивалентных нумераций совпадают, то такие ломаные называются комбинаторно одинаковыми. Зная одну нумерацию, можно восстановить все остальные. Если же две ломаные могут быть переведены друг в друга простыми преобразованиями (т.е. такими непрерывными преобразованиями плоскости, при которых пересекающиеся ребра остаются пересекающимися, и наоборот), то они называются геометрически одинаковыми. Первое понятие слабее, так как существуют примеры ломаных, эквивалентных друг другу комбинаторно и не эквивалентных геометрически. Множество всех комбинаторно одинаковых ломаных называется комбинаторным видом, аналогично определяется геометрический вид.
Сперва рассмотрим несколько банальных общих свойств ломаных вида (n,m):
Помимо изображения ломаной в виде графа и нумерации, существуют другие формы представления. Диаграмма - это граф, вершины которого соответствуют ребрам ломаной, а ребра - ее вершинам и точкам пересечения. Диаграмма ломаной (n,m) может быть нарисована в виде правильного n-угольника, в которой каждая вершина соединена диагоналями с m другими. Все грани ломаной в этом представлении изображены циклами ребро-диагональ-ребро-..., но некоторые такие циклы не соответствуют никакой грани. Диаграмма одинакова для всего комбинаторного вида. Комбинаторный вид однозначно задается диаграммой или нумерацией (любой из класса эквивалентных нумераций, количество которых равно 2n/s, где s - порядок группы комбинаторной симметрии, или симметрии диаграммы, что то же самое). Перенумерация ломаной с другого звена эквивалентна повороту диаграммы, а перенумерация в другую сторону - зеркальному отражению. Это значит, что две диаграммы, переводимые друг в друга поворотами и отражениями, суть одна диаграмма. Таким образом, глядя на диаграмму, легко визуально выявить симметрию нумерации, которая далеко не очевидна из цифровой записи последней. Симметрия самой ломаной, однако, не обязана быть такой же.
Структурная формула ломаной - это граф, двойственный ломаной (вершины переходят в грани и наоборот), если рассматривать ломаную как плоский граф (его вершины - не вершины ломаной, а точки самопересечения). Связанными оказываются те вершины С.Ф., которые соответствуют граням, имеющим общие ребра. Внешняя грань ломаной (т.е. вся оставшаяся плоскость) также отображена вершиной С.Ф. Общее число граней ломаной (=вершин С.Ф.) легко считается по теореме Эйлера для плоских графов и равно nm/2+2. Все грани С.Ф. являются четырехугольными и соответствуют точкам самопересечения ломаной. Порядком грани (а также соответствующей вершины С.Ф.) называется число вершин ломаной, находящихся на ее границе. В случае ломаных (n,1) валентность (число связей) вершины равна ее порядку. Сумма порядков всех граней равна 2nm, т.к. каждая вершина работает за две грани. Следует различать ребра разной кратности, что в некотором смысле напоминает химические формулы. Пора ввести понятие топологической эквивалентности, которой обладают две ломаные, имеющие одинаковую в смысле теории графов С.Ф. (с учетом предыдущего замечания). Эта эквивалентность промежуточна между двумя другими - слабее геометрической, сильнее комбинаторной. Так, две ломаные могут быть эквивалентны комбинаторно, но не топологически (например, разные топологические виды спаренной шестерки), а могут быть эквивалентны топологически, но не геометрически (например, разные геометрические виды любой нефакторизованной ломаной, начиная с 10-гармошки).
Факторизованными (или факторизуемыми) называются те ломаные, ребра которых можно разбить на два класса так, что в каждом из них ребра идут подряд и пересекаются только с ребрами того же класса. Простейшим примером является уже упомянутая двойная шестерка. Есть мнение, что с ростом n доля факторизованных ломаных растет.
Теперь заточим наше внимание на свойствах ломаных (n,1). Здесь четные ребра пересекаются только с нечетными. Если бы пересеклись два ребра одинаковой четности, то между ними осталась бы петля из нечетного количества ребер. А остальная часть ломаной должна была бы пересечь её чётное число раз, т.к. оба конца - с одной стороны петли (оба внутри или оба снаружи). Получилось противоречие.
Нумерации являются вектор-строками, то есть выражаются так же, как перестановки порядка n. Поэтому их иногда так и называют. Информация, заключенная в одной перестановке, избыточна. Сжать ее помогает тот факт, что четные ребра пересекаются только с нечетными. Достаточно записать разделенные на два номера ребер, пересекающихся со всеми нечетными в черед. Такая последовательность чисел называется краткой нумерацией. По ней однозначно востанавливается длинная (обычная) нумерация, причем автоматически подходящая под условие четности.
Не все длинные нумерации, удовлетворяющие условиям непересечения соседних звеньев и четности (будем называть их 0-правильными нумерациями, т.к. в дальнейшем появятся так называемые критерии первого, второго порядка и др., и подходящие под них нумерации будут называться 1-правильными и т.д.), описывают существующие ломаные.
Напомним, что n обязано быть четным числом больше двух. Для n=4 проектная ломаная не может существовать - это легко проверить. А для n=6 уже есть одна такая. Вот она. При нажатии на кнопки 'Short' и 'Long' выдаются соответственно краткая и длинная нумерации.
В конце книги приводится кадастр описанных ломаных. По традиции название дается комбинаторному виду, но основывается обычно на одном из геометрических видов. Из кадастра видно, что существуют серии ломаных, отличающихся количеством вставленных крестов (поскольку в дальнейшем появятся и другие серии, за такими закрепим название гомологических рядов). Простейший гомологический ряд, называемый гармошками, начинается с шестерки. Это гарантирует существование по крайней мере одной ломаной для каждого четного n, превосходящего 6.
Простейший критерий, позволяющий отсекать невозможные нумерации, в терминах диаграмм формулируется так: если две непересекающихся диагонали пересекает нечетное число диагоналей, то ломаной не существует.
| n | 6 | 8 | 10 | 12 | 14 |
| Комбинаторные виды | 1 | 1 | 2 | 4 | ... |
| Топологические виды | 1 | 1 | 2 | 5 | ... |
| Геометрические виды | 1 | 1 | 3 | 11 | ... |
| 0-правильные нумерации | 1 | 2 | 13 | 80 | 579 |
Разные топологические виды внутри одного комбинаторного существуют только для факторизованных ломаных; в случае нефакторизованных топологический и комбинаторный вид - одно и то же. Структурная формула - характеристика топологического вида - вполне задается диаграммой, дополненной (в случае факторизованных ломаных) указанием взаимного расположения фрагментов ломаной (внутрь/наружу). Общий вид такого описания не совсем ясен. Число разных вариантов здесь может быть весьма велико (порядка 2 в степени числа фрагментов). Структурные формулы разных топологических видов отличаются по расположению половинок относительно кратной связи.
Разные геометрические виды внутри одного топологического порождаются симметрически неэквивалентными вершинами структурной формулы, их число не более n/2+2. Каждая грань ломаной, кроме двойки (т.е. той, которая содержит две вершины), может послужить внешней гранью. Структурная формула с отмеченной вершиной, которая соответствует внешней грани, вполне задает геометрический вид.
Группа симметрии структурной формулы для известных ломаных имеет тот же порядок, что и группа симметрии диаграммы, но предположение об их изоморфизме не доказано (никто и не пытался). Выявить последнюю легче, т.к. диаграмма - плоская фигура, а структурная формула, если ее пространственная симметрия соответствует топологической, должна быть представлена нарисованной на сфере. Что касается самой ломаной, то ее симметрия равна симметрии позиции, в которой находится на структурной формуле вершина, соответствующая внешней грани.
Каждой ломаной можно поставить в соответствие некоторый узел. Если обвести ломаную веревкой, каждый раз в точках пересечения проходя то над, то под, получится т.н. альтернированный, или надподный узел. Шестерка дает хиральный узел, а восьмерка - нет, хотя сами ломаные, их структурные формулы и диаграммы в обоих случаях имеют плоскости симметрии. Было показано, что условие хиральности узла - отсутствие пары связанных симметрически эквивалентных вершин у структурной формулы. С заменой прямых на кривые также тесно связана задача о распрямимости: если существует замкнутая кривая на плоскости, имеющая nm точек самопересечения, то можно ли разбить ее на n кусков по m пересечений на каждом, которые затем спрямить - т.е. привести к ломаной (n,m)? Для m=2, а значит, и для m>2 показано, что ответ в общем случае отрицательный. Вопрос для ломаных (n,1) пока открыт.
Введем раскраску ломаной таким образом. Присвоим каждому ребру значение 1 или -1. Если ребро пересекается другим справа налево то "1", если слева направо то "-1". Теперь заменим цифру каждого четного звена на противоположную. Будем ассоциировать со значениями 1 и -1 разные цвета. Доказано, что пересекающиеся ребра раскрашены одинаково. Таким образом, цвет является характеристикой пары пересекающихся ребер ломаной, а значит, и диагонали диаграммы. Сложно раскрашиваются факторизованные ломаные. В них момент выбора между 1 и -1 присутствует более одного раза. Поххоже, для них надо разрабатывать теорию каких-то многозначных цветов (принимающих более чем два значения), а пока сказать нечего.
Выведены закономерности, позволяющие раскрасить произвольную диаграмму,
не зная вида ее ломаной. Все они доказываются легко, глядя на нарисованные
куски ломаной с отмеченным направлением. Итак:
две смежные диагонали
(т.е. такие, которые выходят из соседних вершин и входят в соседние вершины)
одинаково окрашены, независимо от того, пересекаются они, или нет;
диагональ, отсекающая диугольник, из которого выходят две смежные
диагонали, одного с ними цвета, если они пересекаются, и другого, если нет;
вообще, две диагонали окрашены одинаково, если имеется чётное число
диагоналей, пересекающих первую из них и не пересекающих вторую, и
наоборот. Всё это не относится к факторизованным ломаным, с ними хитрее.
Некоторые диаграммы не удается раскрасить, так как описанные правила приводят к противоречию. Такие диаграммы не соответствуют никаким ломаным.
С помощью раскрашенной диаграммы можно восстановить грани ломаной. Выше уже упоминалось, что грани ломаной изображаются на диаграмме циклами диагональ - сторона - диагональ... Введение раскраски позволяет определить, какие циклы соответствуют граням, а какие нет. Пусть диагонали раскрашены в красный и синий цвета. Выберем на диаграмме стартовую точку (находящуюся на какой-либо дуге, то есть соответствующую вершине ломаной) и начнем движение по диаграмме по часовой стрелке (выбор направления не влияет ни на что). Когда мы доберемся до диагонали, необходимо перейти по ней и продолжить движение по диаграмме в том же направлении, что и до того, если диагональ была синего цвета и в обратном, если красного. Поскольку цвета были выбраны произвольно, то, найдя все возможные грани этим способом, нужно инвертировать цвета (заменить синий на красный и наоборот) и повторить операцию. Исходя из одной и той же начальной точки, можно получить две грани, что логично: каждая вершина ломаной принадлежит двум различным граням. Записав вершины, через которые мы проходим в ходе генерации, получим описание грани. Повторив все вышеописанные операции для всех вершин ломаной, получим список граней, из которого останется только исключить повторяющиеся. Покажем, почему этот алгоритм дает верный результат. Рассмотрим два последовательных пересечения, принадлежащих одной грани. Пусть они имеют один и тот же цвет. Тогда по определению раскраски ломаных они разнонаправленны. При обходе грани соотношение направлений обхода грани и обхода ломаной либо меняется два раза (на обоих пересечениях), либо не меняется никогда. Аналогично, рассматривая пересечения разного цвета, можно убедиться, что соотношение направлений меняется только на одном из таких пересечений.
Определим понятие индекса грани. Рассмотрим некоторую ломаную. Выберем точку А внутри одной из ее граней и некоторую точку B на ломаной. Передвигая точку B вдоль ломаной, будем считать количество оборотов, которое сделает вектор АВ. Число оборотов, которые сделает этот вектор при полном обходе ломаной (с учетом направления, считая движение по часовой стрелке со знаком плюс, а против часовой стрелки - со знаком минус), будем называть индексом грани. Индекс внешней грани таким образом получается равным 0. Заметим, что поскольку направление обхода ломаной выбирается произвольно, индекс каждой грани определен с точностью до знака. Индексы соседних граней различаются на единицу (двойное соотношение). Индексы четырех граней, сходящихся в одной точке, связаны простым правилом (четверное соотношение): два из них, относящиеся к противолежащим граням, равны друг другу, а два другие на 1 больше и на 1 меньше их.
Набор индексов относится к конкретному геометрическому виду. У другого геометрического вида (внутри того же топологического вида) имеются тоже две индексации. Каждая из них связана с одной из индексаций данной ломаной соотношением: все индексы отличаются на одну и ту же константу. Индексы другого топологического вида отличаются неприятным образом.
Остаток от деления на 8 суммы индексов четырех граней, прилежащих к одному пересечению, определяет цвет этого пересечения. Рассмотрим два последовательных пересечения и расставим индексы примыкающих к ним граней согласно четверному соотношению (a, a-1 и т.д.). Если оба раза ломаная пересечена в одну сторону (справа налево или слева направо), т.е. пересечения разного цвета, то сумма индексов будет отличаться на 4, а если в разные стороны - она будет совпадать.
Можно по структурной формуле установить индексы. Одной из граней произвольно приписывается нулевой индекс, другой - неизвестный (x), и далее по четверному соотношению расставляются индексы остальных граней. В итоге определяется то значение x, которое не создает противоречий при таком заполнении. Однако уже найдены случаи, когда потребовалось вводить более одной неизвестной величины.
Словарь
| Альтернированный узел | Узел, в котором веревка попеременно проходит то сверху то снизу. |
| Великий Упс | Неретин |
| Веник | Структурная формула с вырезанной вершиной |
| Вид геометрический | Группа ломаных, инвариантных относительно простых преобразований и симметрии относительно прямой. |
| Вид комбинаторный | Группа ломаных, описываемых нумерацией. |
| Вставка креста | Процедура, позволяющая получить одну ломаную из другой. |
| Вставка ломаной | Процедура, позоляющая получать факторизуемые ломаные. |
| Гармошки | Особое семейство ломаных. |
| Граф Воронцов | Один из участников проекта, безвинно убитый Вабищевичем Николаем. |
| Граф неплоский | Граф, который нельзя изобразить на плоскости без самопересечений. |
| Граф плоский | Граф, который может быть изображен на плоскости без самопересечений. |
| Группа нумераций | Группа нумераций, замкнутая относительно операций сдвига и перенумерации |
| Диаграмма | Диаграмма Великого Упса / Неретина / Фроста - просто способ записи нумерации, делающий ее более наглядной. |
| Диугольник | Часть ломаной, ограниченная двумя пересечениями звеньев. |
| Загубленные идеи | 99.9999999999999999% идей. |
| Звездочки | Особое семейство ломаных, все ломаные в котором абсолютно симметричны, т.е. имеют только одну нумерацию. |
| Зеркало | Изменение нумерации при изменении направления обхода ломаной. |
| .И.С. | Некто Иван Сергеевич |
| Крест | Два пересекающихся звена. |
| Ломаная | Объект исследования проекта |
| Мафия | Основное занятие МКШовцев. |
| Младшая нумерация | Нумерация, нечетные элементы которой - наименьшие в группе |
| Моноугольник | Часть ломаной, ограниченная одним пересечением звеньев. |
| Мультиугольник | Часть ломаной, ограниченная несколькими пересечениями звеньев. |
| Неретин | И.С. |
| Николай Сергеевич Келлин | Человек, в совершенстве владеющий шаманством. |
| Нумерация | Комбинаторное описание ломаной, показывающее, какое звено с каким пересекается. |
| Перенумерация | См. Зеркало |
| Переходная диаграмма | Один из этапов эволюции диаграмм на пути к структурной формуле. |
| Проект | Неосновное занятие МКШовцев. |
| Простое преобразование | Движение вершин, при котором пересечения ребер сохраняются. |
| Раскраска | Один из видов шаманства, помогающий построить структурную формулу. |
| Сдвиг | Изменение нумерации при выборе другого начального звена. |
| Серединная фигура | Объект, определенный для ломаных вида (n,2), Множество серединных отрезков. |
| Структурная формула | Один из видов описания ломаной, показывающий, на какие грани ломаная разбивает плоскость и какие из них соединены. |
| Сюрикены | Особое семейство ломаных. |
| Триугольник | Часть ломаной, ограниченная тремя пересечениями звеньев. |
| ТСО | ТОТ САМЫЙ ОСТРОВ. |
| Ушки | Количество нумерации (Un) |
| Фрактальная ломаная | Плод воспаленного воображения Великого Упса. |
| Шаманство | Наиболее распространенный способ выведения формул. |
| n | Название | Геометрические виды | Симметрия диаграммы, структурной формулы и геом. видов |
| 6 | Шестерка | 1 | 6mm; 6m2; 3m |
| 8 | Восьмерка | 1 | 4mm; 42m; m, m |
| 10 | 10-звезда | 1 | 10mm; 10m2; 5m |
| 10-гармошка | 1, 2 | 2mm; 2mm; m, m | |
| 12 | 12-гармошка | 1, 2 | 2mm; 2mm; m, m |
Кадастр ломаных (n, 2) - пока весьма неполный.