Математическая модель игры Доббль (4 стр)

Автор: Skyblade

Как построить проективную плоскость?

Графическое представление проективной плоскости выглядит интересно и наглядно, но как найти такую комбинацию точек, чтобы она обладала вышеописанными свойствами?
Проще всего - посетив сайты, где размещены предрасчитанные данные для проективных плоскостей разных порядков.

Например, для проективной плоскости 7 порядка можно посетить такую страницу: https://www.uwyo.edu/moorhouse/pub/planes/pg27.txt 
Там представлена матрица из чисел. Строки - это карточки (точки) в понятиях Доббля. Числа в строках - это порядковые номера символов (линий), начиная с нуля, которые нарисованы на каждой карточке (проходят через данную точку).

Также можно воспользоваться услугами математических пакетов, таких, как Matlab, чтобы построить матрицу инцидентности проективной плоскости. [2] [3]

Матрицы инцидентности

Одним из простейших примеров матрицы инцидентности может служить матрица размером 2х1 для неориентированного графа из двух вершин, соединённых одним ребром:

Рис. 14. Неориентированный граф из двух вершин, соединённых одним ребром, и его матрица инцидентности.

Более сложный пример графа и его матрицы инцидентности:

Рис. 15. Неориентированный граф с 4-мя вершинами и его матрица инцидентности.

Как видно из последнего примера, в матрице инцидентности графа в каждом столбце ровно две единицы, т.к. одно ребро соединяет две вершины. 

Проективная плоскость является гиперграфом, так как одна прямая (ребро) соединяет несколько точек (вершин). Поэтому в матрице инцидентности проективной плоскости единицы в каждом столбце встречаются \(n+1\) раз, где \(n\) - порядок проективной плоскости.

Для плоскости Фано, изображённой на рис. 9, матрица инцидентности будет иметь следующий вид:

Рис. 16. Матрица инцидентности плоскости Фано.

Для упрощения восприятия нули не показаны, а единицы заменены на символ Х.
В таком представлении проективной плоскости хорошо заметен принцип двойственности точек и прямых - прямая проходит ровно через 3 точки, и, в то же время, точка принадлежит ровно трём прямым.

Построение проективной плоскости перебором

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

Для всех столбцов
    Для всех строк
        Если в столбце стоит n+1 единиц, то перейти к следующему столбцу
        Если в строке стоит n+1 единиц, то перейти к следующей строке
        Для каждого предыдущего столбца Х
            Если в столбце Х на текущей строке стоит единица
            и
            Если уже есть совпадения в строках для столбца Х и текущего столбца,
                то перейти к следующей строке
        Поставить единицу
    Перейти на следующую строку
Перейти на следующий столбец

Следуя этому алгоритму, мы получим симметричную матрицу для плоскости Фано:

Рис. 17. Матрица инцидентности плоскости Фано, построенная по алгоритму псевдокода.

Эта матрица не совпадает с предыдущей. На самом деле, это неважно. 
Перестановка любых двух строк матрицы инцидентности равносильна перенумерации вершин графа. 
Перестановка любых двух столбцов матрицы инцидентности равносильна перенумерации рёбер графа (если их заранее пронумеровать).

#геймдизайн, #Доббль

5 мая 2017 (Обновление: 18 янв 2019)

Комментарии [4]