Конгруэнции диграфов
ВВЕДЕНИЕ
Граф является математической абстрактной структурой, имеющей отражение во многих реальных объектах. Он используется для демонстрации принципов работы множества вещей – от бытовых до больших промышленных механизмов, например, с решением транспортных задач, задач о потоках в сети нефтепроводов, в программировании и теории игр, теории передачи сообщений. Теория графов имеет применения и в таких областях, как экономика, психология и биология.
В данной работе рассматривается определенный подкласс графов: направленные графы, являющиеся частным случаем ориентированных графов, и свойства их решёток конгруэнций. Более подробно будут рассматриваться численные характеристики решётки конгруэнций диграфов. Актуальность данной работы обусловлена кажущимся недостатком исследований по данной теме. Конгруэнциям различных типов графов посвящено некоторое число работ коллег из Саратовского университета. Так, уже были изучены и описаны такие классы графов, как цепи, турниры (в том числе бы
СОДЕРЖАНИЕ
ВВЕДЕНИЕ 3
1 Основные определения 5
2 Построение решётки конгруэнций диграфа в программном виде 10
2.1 Описание и реализация использованных алгоритмов 10
2.2 Разработка программного продукта 12
2.3 Демонстрация работы ПО 13
2.4 Описание механизмов отслеживания корректности ввода данных 19
3 Статистическое исследование 23
3.1 Получение общих данных и их исследование 23
3.1.1 Статистические данные по всем диграфам 24
3.1.2 Теоретические результаты исследования диграфов 26
3.2 Исследование турниров 29
3.2.1 Теоретические результаты исследования турниров 32
3.3 Исследование графов-цепей 34
3.3.1 Теоретические результаты исследования графов-цепей 41
3.4 Исследование графов-циклов 43
3.4.1 Теоретические результаты исследования графов-циклов 46
ЗАКЛЮЧЕНИЕ 49
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 51
ПРИЛОЖЕНИЕ А Исходный код разработанного ПО 53
ПРИЛОЖЕНИЕ Б Исходный код для создания базы конгруэнций 74
ПРИЛОЖЕНИЕ В Статистика по диграфам с числом вершин 6 76
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1 Богомолов, А. М. Алгебраические основы теории дискретных систем / А. М. Богомолов, В. Н. Салий. – М.: Наука. Физматлит, 1997. – 368 с.
2 Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. – М.: Наука, 1990. – 383 с.
3 Харари, Ф. Теория графов / Ф. Харари; пер. В. П. Козырева. М.: Мир, 1973. – 302 с.
4 Киреева, А. В. Конгруэнции турниров / А.В. Киреева // Студенты – ускорению научного прогресса: Сб. студ. науч. раб. – Саратов: Издательство Саратовского университета, 1990. – С. 3–5.
5 Фомина, Е. О. Конгруэнции цепей и циклов: автореф. дис. … канд. ф.-м. наук // Е. О. Фомина. – Москва, 2013. – 17 с.
6 Мирзаянов, М. Р. О минимальных сильно связных конгруэнциях ориентированных цепей / М. Р. Мирзаянов // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. – Саратов: Издательство Саратовского университета, 2006. – С. 104–114.
7 Богомолов, А. М. Несколько задач из алгебры дискретных систем / А. М. Богомолов, В. Н. Салий. // Материалы X Междунар. конф. по проблемам теоретич. кибернетики, Методы и системы технической диагностики. – Саратов: Издательство Саратовского университета, 1993. – С. 32–34.
8 Киреева А. В. О конгруэнциях корневых деревьев / А. В. Киреева // XI Всесоюз. конф. по проблемам теоретической кибернетики. – Волгоград: Тез. докл., 1990. – Ч. 1. С. 23.
9 Кабанов М. А. Функциональные конгруэнции ориентированных графов / М. А. Кабанов // Упорядоч. множества и решетки. – Саратов: вып. 11, 1995. – С. 15–23.
10 Числа Стирлинга второго рода [Электронный ресурс] : Викиконспекты студентов университета ИТМО / URL: https://neerc.ifmo.ru/wiki/index. php?title=Числа_Стирлинга_второго_рода (дата обращения 09.01.2023). Загл. с экрана. Яз. рус.
11 Числа Белла [Электронный ресурс] : Викиконспекты студентов университета ИТМО / URL: https://neerc.ifmo.ru/wiki/index. php?title=Числа_Белла (дата обращения 09.01.2023). Загл. с экрана. Яз. рус.
12 Graph format
Получающаяся последовательность максимальных ширин решёток описывает последовательность наибольших чисел Стирлинга второго порядка из n по всем k. Получающаяся последовательность максимальных рангов решёток описывает последовательность наибольшему числу Белла для этого n. [15]
Докажем, что максимальная решётка конгруэнций может имеет ширину, равную точно S(n, k), наибольшая по всем k, и ранг, равный точно числу Белла Bn.
Предположим, что решётка имеет ширину, меньше, чем указанное значение. Это предположение сразу же противоречит условию, так как по методу математической индукции в полученных результатах ширина так же должна быть меньше максимального числа Стирлинга 2 порядка. Аналогично ранг решётки не может быть меньше числа Белла.
Предположим, что решётка может больше по ширине, чем указанные значения. Это предположение противоречит условию сразу из 2 рассуждений – во-первых