|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ФИЦ ПХФ и МХ РАН |
||
Оценка обхвата бирегулярных двудольных графовкурсовая работа (Бакалавр)
- Научный руководитель: Половников В.С.
- Автор: Шульгина Е.А.,
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Филиал МГУ в г. Ташкент
- Год защиты: 2015
- Курс: 3
- Аннотация: В своей курсовой работе Шульгина Е.А. предприняла попытку описать строение всевозможных двудольных графов с одинаковыми степенями вершин в каждой доле (такие графы она назвала бирегулярными). Екатериной полностью были описаны графы с маленькими степеням вершин в обеих долях, отдельно рассмотрен класс графов-клеток, в данной терминологии (t,t)-бирегулярных графов. Доказаны нижние оценки для количества вершин в каждой доле (t,t)-бирегулярных графов обхвата 6 и 8, которые оказались частными случаями оценок числа вершин для графов Мура. Доказана нижняя оценка числа вершин для (t,s)-бирегулярных графов обхвата 6 при t<s, придуман и реализован эффективный алгоритм построения (t,s)-бирегулярных графов с минимальным количеством вершин при некоторых значениях t и s. Составлены программы на ЭВМ для генерации графов (в основе переборный-эвристический алгоритм), программы для поиска и подсчета числа 6-циклов и 4 циклов в графах.
- Добавил в систему: Половников Владимир Сергеевич