Построение диаграммы Хассе

[B@R5uk]

arseniiv в сообщении #1453088 писал(а):

мы включаем туда изоморфные подгруппы или собираем их в одну?

У меня программа глупая — находит все подгруппы и считает их разными, если они состоят из разных элементов.

[Dmitriy40]

B@R5uk в сообщении #1453084 писал(а):

$A\to B,\;A\to C,\;A\to D,\;A\to E,\;B\to C,\;B\to D,\;C\to D,\;E\to D$

ОК, для него волна из вершины $A$ перенумерует вершины по поколениям так:
$A_0\to B_1,\;A_0\to C_1,\;A_0\to D_1,\;A_0\to E_1$
всё, остальные рёбра "лишние" (ведут к уже пронумерованным вершинам), все вершины перенумерованы. Хассе вполне себе получилась. Сложность опять таки вовсе не кубическая, а линейная от полного количества рёбер (или в худшем случае квадратичная от количества вершин, рёбер из каждой вершины не может быть больше общего количества вершин -1).

[arseniiv]

B@R5uk в сообщении #1453094 писал(а):

У меня программа глупая — находит все подгруппы и считает их разными, если они состоят из разных элементов.

Ага, понятно, это даже чем-то хорошо. Например в $\mathbb Z_2\times\mathbb Z_3\times\mathbb Z_2$ подгруппа $\langle(0,0,1)\rangle\cong \mathbb Z_2$ — не подгруппа $\langle(1,0,0), (0,1,0)\rangle\cong \mathbb Z_2\times\mathbb Z_3$, а скученный граф о таком не даст судить.

[B@R5uk]

arseniiv в сообщении #1453088 писал(а):

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

Тут ещё есть вопрос затратности алгоритма по памяти. У меня есть пример группы с количеством элементов 660, у неё число подгрупп приблизительно такое же. Я пробный алгоритм хотел сначала сделать с использованием квадратной таблицы отношений порядка между вершинами графа, но как подумал об этом монстре — передумал. Впрочем, наверное, зря. Лучше затратиться по памяти, за то алгоритм будет простой и понятный. Всё равно группу такого размера, что эта таблица займёт порядка 1 ГБ за разумное время не посчитать.

-- 09.04.2020, 14:53 --

Dmitriy40 в сообщении #1453095 писал(а):

Хассе вполне себе получилась.

Нет, всё таки вы не понимаете, что требуется сделать. Нарисуйте на бумажке картинку.

[arseniiv]

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

-- Чт апр 09, 2020 17:01:58 --

(И следующий кандидат: разбиваем каким-то образом вершины на поколения и добавляем опять каким-то хитрым образом рёбра, идущие из старших поколений в младшие. Тут надо всё равно придумать хорошие способы и разбить на поколения, и породить рёбра, чтобы некоторые графы не перевешивали, и опять изначально не очевидно, насколько всё плохо может быть.)

-- Чт апр 09, 2020 17:03:51 --

Ага, эта тема ожидаемо гуглится.

[Dmitriy40]

B@R5uk
Вы просили диаграмму Хассе, она упорядочивает вершины по поколениям (ярусам, этажам), удаляя рёбра идущие не между соседними поколениями. Волна именно всё это и делает, назначает вершинам поколения и перебором всех рёбер из вершины удаляя лишние.
Если Вы хотели чего-то другого, ну ... да, не понял.

[B@R5uk]

Dmitriy40, я вам даже картинку нарисовал:

$$\xymatrix{ &D\\ C\ar[ur]\\ &&E\ar[uul]\\ B\ar[uu]\ar@{-->}[uuur]\\ &A\ar[ul]\ar[uur]\ar@{-->}[uuul]\ar@{-->}[uuuu] }$$

Пунктирные стрелки — это те соотношения порядка, которые являются следствиями других соотношений порядка. Например, из двух соотношений $A\to B$ и $B\to C$ следует $A\to C$, поэтому последнее не является ключевым, и в диаграмме Хассе соответствующая стрелка не рисуется. Все сплошные же стрелки являются необходимыми. Например, $C\to D$ или $E\to D$ нельзя получить ни из каких других соотношений порядка.

-- 09.04.2020, 15:40 --

(Оффтоп)

arseniiv в сообщении #1453096 писал(а):

Например в $\mathbb Z_2\times\mathbb Z_3\times\mathbb Z_2$

Что-то это плохой пример, так как вырождается в $\mathbb{Z}_6\times\mathbb{Z}_2$. Тут надо или какой-нибудь $Dih_3\rtimes\mathbb{Z}_2$ или простецкий $\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2$. Судя по всему, нет группы ранга 3 12 порядка

[arseniiv]

(Оффтоп)

Да, я сначала думал про степени $\mathbb Z_2$, дёрнуло вот подразнообразить…

[B@R5uk]

arseniiv, я тем не менее довёл вашу идею до логического конца: взял группу $\mathbb{Z}^2_3\rtimes\mathbb{Z}_2$ и подобрал соотношения между образующими, чтобы ничего не сокращалось. У получившейся группы 28 подгрупп, включая несобственные. Из них 9 штук $\mathbb{Z}_2$, 4 кольца $\mathbb{Z}_3$, 12 групп диэдра порядка 6 и группа $\mathbb{Z}^2_3$, разумеется. Из каждой из этих 9 групп ведёт по 4 стрелочки в группы диэдра. В каждую группу диэдра приходит 3 стрелочки от $\mathbb{Z}_2$ и одна от $\mathbb{Z}_3$. От каждой $\mathbb{Z}_3$ в $\mathbb{Z}^2_3$ ведёт по стрелочке. Из подгрупп 2-го ранга (коих $12+1=13$) ведёт строчка в макушку графа (или как ещё обозвать вершину-антоним корню?). И из корня в каждое кольцо (коих $9+4=13$) тоже ведёт по стрелочке. Всего получается $13+4\times 4+9\times 4+13=78$ стрелочек. И это только диаграмма Хассе. В полном графе ещё 26 стрелочек.

Такой граф можно считать разреженным?

-- 09.04.2020, 17:59 --

Хотя, это не самый красивый пример, бывают диаграммы по-интересней, в частности вариант два с предыдущей страницы:

$$\xymatrix{ &&&&12\\ &13\ar[urrr]&&&14\ar[u]&&&15\ar[ulll]\\ 1\ar[ur]&&8\ar[ul]&&16\ar[ulll]\ar[u]\ar[urrr]&2\ar[ul]&7\ar[ull]&4\ar[u]&5\ar[ul]\\ &3\ar[ul]\ar[ur]\ar[urrr]&&&17\ar[u]&&&6\ar[ulll]\ar[ull]\ar[ul]\ar[u]\ar[ur]\\ &&&9\ar[ur]&11\ar[ulll]\ar[u]\ar[urrr]&10\ar[ul]\\ &&&&0\ar[ul]\ar[u]\ar[ur] }$$

[arseniiv]

B@R5uk в сообщении #1453134 писал(а):

Всего получается $13+4\times 4+9\times 4+13=78$ стрелочек. И это только диаграмма Хассе. В полном графе ещё 26 стрелочек.

Так, ну в полном ациклическом графе на 28 вершинах будет $28(28 - 1)/2 = 378$ стрелок, так что наверно ваш граф неплохо так разрежен, 28% заполнения.

-- Чт апр 09, 2020 20:35:26 --

Ну или мы можем не делить на два выше, просто заполнения выше 50% мы тогда не получим у корректных входных данных.