2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Перечисление классов эквивалентности (см. внутри)
Сообщение01.08.2021, 13:30 


01/08/21
2
Доброго дня, уважаемые математики!
Нужна ваша помощь в решении исследовательской задачи.

Задача такая: Есть множества из двух, трех, ... N. элементов. Требуется классифицировать, перечислить бинарные отношения на этих множествах. Понятно, что множество всевозможных отношений на множестве мощности N имеет мощность $2^{N^2}$. Для $N = 2$ отношений будет 16. Перечислил, нашел среди них эквивалентности, доминирования. Все усложнилось, когда я захотел учесть симметрию относительно перестановок элементов исходного множества. Пришлось перебирать. Для двухэлементного множества таких отношений 6: $\{\},\{aRb\},\{aRa,aRb\}, \{aRa,aRb,bRb\},\{aRb,bRb\},\{aRa,bRb,aRb,bRa\}$. Для 3х-элементного множества перечислить отношения не представляется возможным, всего таких отношений 512. Тем более непосильно искать среди них симметричные относительно перестановок, коих 6.
Постановка задачи, как я понимаю, может сводиться к перечислению классов эквивалентности квадратных ${N} \times {N}$ бинарных матриц, где матрицы считаются эквивалентными, если получаются друг из друга перестановкой строк и столбцов, либо к перечислению смешанных псевдографов с N вершинами. Хочется как-то продвинуться в решении в общем виде, но теоретической подготовки мне не хватает. Нашел статью Enumeration of mixed graphs 1966 года, но в рассматриваемых там графах нет петель. Как думаете, если решение не публиковалось, реально это самому решить?

Возможно подобная задача уже встречалась, и решение известно. В любом случае, буду благодарен за комментарии.

 Профиль  
                  
 
 Re: Перечисление классов эквивалентности (см. внутри)
Сообщение01.08.2021, 13:47 
Заслуженный участник
Аватара пользователя


16/07/14
8335
Цюрих
Для двух элементов довольно много потеряли - например $\{a\,\mathcal\,b, b\,\mathcal\,a\}$. Всего должно быть 10: 3 несвязных, 3 с циклом, и 4 связных без цикла. См. также A000595.

 Профиль  
                  
 
 Re: Перечисление классов эквивалентности (см. внутри)
Сообщение01.08.2021, 14:44 


01/08/21
2
mihaild в сообщении #1527821 писал(а):
Для двух элементов довольно много потеряли - например $\{a\,\mathcal\,b, b\,\mathcal\,a\}$. Всего должно быть 10: 3 несвязных, 3 с циклом, и 4 связных без цикла. См. также A000595.

Да, ошибся, действительно 10.
Цитата:
Equivalently, the number of digraphs on n unlabeled nodes with loops allowed but no more than one arc with the same start and end node.
как я понимаю - это именно то, что нужно. По ссылке на OEIS нашел литературу по вопросу. Спасибо!

P.S.Вот искомые отношения на 2х элементах:
$\emptyset$, $\{aa\}$,$\{ab\}$,$\{aa,bb\}$,$\{ab,ba\}$,$\{aa,ab\}$,$\{aa,ba\}$,$\{aa,ab,ba\}$,$\{aa,ab,bb\}$,$\{aa,bb,ab,ba\}$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group