18 февраля в 16:30 состоится очередное заседание семинара «Компьютерная алгебра». Руководитель семинара – д.ф.-м.н. С.А. Абрамов.
На заседании семинара будет представлен доклад на тему:
«Число всех неизоморфных ациклических графов с заданным числом вершин»
Автор доклада:
В.В.Тензина, механико-математический факультет МГУ им. М.В. Ломоносова
Аннотация
Ориентированный граф без ориентированных циклов называется ациклическим. Назовём ориентированный граф тривиальным, если всякое биективное отображение множества вершин графа в себя, сохраняющее рёбра, тождественно. В данной работе описывается метод подсчёта числа неизоморфных тривиальных ациклических графов без кратных рёбер с заданным числом вершин n. Этот метод основан на перечислении неизоморфных строгих порядков на множестве из n вершин. Для этого перечисления предложен алгоритм, использующий перечисление всех неизоморфных строгих порядков на множестве из n-1 элементов. Попутно вычисляется число всех неизоморфных строгих порядков, чья группа автоморфизмов тривиальна. Создано программное обеспечение на языке С++, реализующее вышеприведённые алгоритмы. По уже созданному перечислению всех неизоморфных строгих порядков осуществляется вычисление числа всех неизоморфных тривиальных ациклических графов с заданным числом вершин. Эти результаты могут быть использованы для вычисления некоторых характеристик множества всех топологических пространств с конечным числом точек.
Заседание семинара будет проходить в дистанционном режиме через Zoom. Ссылка для подключения будет направлена участникам семинара по электронной почте. По вопросу участия в семинаре просьба обращаться по электронной почте: moscowcaconf@gmail.com
