СОДЕРЖАНИЕ 2
ВВЕДЕНИЕ 4
1. Основные понятия теории гиперграфов 6
1.1 Понятие гиперграфа 6
1.2 Примеры гиперграфов 8
1.3 Способы задания гиперграфов 9
1.3.1 Алгебраический способ задания гиперграфов 9
1.3.2 Матричный способ задания гиперграфов 10
1.4 Виды гиперграфов 11
2. Вывод формул для подсчета количества автоморфизмов
гиперграфов особого вида 14
2.1 Однореберный гиперграф 14
2.2 Строго k-пересекающийся гиперграф с ребрами разной
мощности 15
2.3 Строго t-пересекающийся гиперграф с равномощными
ребрами 17
3.Описание программного продукта 20
3.1. Требования, предъявляемые к программному продукту. 20
3.2. Описание архитектуры приложения 21
3.3 Описание интерфейса приложения 27
4. Результат работы программы. Тестовые примеры 29
4.1. Тестовый пример строго k-пересекающегося гиперграфа с
ребрами разной мощности 29
4.2. Тестовый пример строго k-пересекающегося гиперграфа с
ребрами одинаковой мощности 33
4.3 Тестовый пример нестрого k-пересекающегося гиперграфа 37
ЗАКЛЮЧЕНИЕ 40
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 41
ПРИЛОЖЕНИЕ А 43
В последнее время наблюдается возросший интерес к изучению задач и методов теории гиперграфов [1]. Это связано с тем, что гиперграфы нашли применение в задачах управления большими системам, при моделировании и проектировании электрических систем, компьютерных сетей, процессов, при обработке изображений и во многих других сферах. К тому же гиперграф — это естественное обобщение графа (ребрами гиперграфа являются произвольные подмножества его вершин), конечной плоскости, разбиения множества. Многие авторы значительное внимание уделяли исследованию полугрупп эндоморфизмов и полугрупп автоморфизмов графов и гиперграфов [2,3], так как, исследуя свойства таких полугрупп отображений, можно изучать свойства исходного объекта. Так, применению методов теории групп при изучении графов посвящены известные работы Р.Фрухта, Ф.Харари, Г.Сабидусси и многих других (см., например, [4]). Методы алгебры и комбинаторики применяются и при исследовании гиперграфов [5,6].
Цель выпускной квалификационной работы - найти комбинаторные формулы для расчета количества автоморфизмов гиперграфов некоторых классов. Объектами исследования являются гиперграфы особого вида, а предметом исследования - автоморфизмы таких гиперграфов.
Для достижения цели данной работы были поставлены следующие задачи:
- изучить основные понятия теории гиперграфов;
- построить и проанализировать различные виды гиперграфов;
- вывести формулы, которые позволят точно рассчитать количество автоморфизмов для гиперграфа изучаемого класса;
- применить полученные формулы для расчета числа автоморфизмов на конкретных примерах;
- разработать приложение, предназначенное для расчета количества автоморфизмов гиперграфов особого вида.
Выпускная квалификационная работа состоит из четырех разделов, введения, заключения и списка литературы.
В первом разделе излагаются основные понятия теории гиперграфов и теории множеств, изучаются основные способы представления гиперграфов, также дается обзор областей применения теории гиперграфов.
Во втором разделе содержатся анализ основных видов гиперграфов, вывод формул для вычисления количества автоморфизмов гиперграфов рассматриваемых классов, примеры применения полученных формул.
В третьем разделе приводится описание программного продукта и содержание основных файлов разработанного приложения.
В четвертом разделе показаны результаты тестирования приложения на примерах.
В приложении содержится код разработанного программного продукта.
В последнее время наблюдается возросший интерес к изучению задач и методов теории гиперграфов. Гиперграфы нашли широкое применение в задачах управления большими системами, в логистике, при моделировании компьютерных сетей, электрических и телекоммуникационных систем и во многих других сферах. Кроме того, теорию гиперграфов изучают многие отечественные и зарубежные ученые, она является предметом их научного интереса.
В ходе выполнения выпускной квалификационной работы были применены знания по теории множеств и теории групп, были изучены основные понятия теории гиперграфов, выведены формулы для расчета количества автоморфизмов строго k-пересекающихся гиперграфов с ребрами разной мощности, а также для строго k-пересекающихся гиперграфов с ребрами одинаковой мощности, разработано приложение, предназначенное для расчета количества автоморфизмов гиперграфов этих классов. Разработанный программный продукт может быть использован в качестве учебного пособия для студентов, обучающихся на математических и технических специальностях, изучающих специальные курсы по дисциплине «Дискретная математика», при изучении таких важных понятий как граф, гиперграф и их автоморфизмы.
Результаты данной работы были представлены на VI Международной юбилейной научной конференции «Проблемы управления, обработки и передачи информации», а также на XV Международной научно-практической конференции «Проблемы управления в социально-экономических и технических системах» (работа была отмечена дипломом 2 степени), и опубликованы в сборниках трудов этих конференций [14-15].
