|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Оценка хроматического числа графов без треугольниковкурсовая работа (Бакалавр)
- Научный руководитель: Половников В.С.
- Автор: Адилов С.Ш.,
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Филиал МГУ в г. Ташкент
- Год защиты: 2017
- Курс: 3
- Аннотация: Поиск хроматического числа графов является одной из самых просто формулируемых и сложно решаемых задач в теории графов. Хорошо известна гипотеза о 4-х красках, которых достаточно для правильной раскраски произвольного планарного графа. В связи со сложностью доказательства теорем для произвольных графов, исследователи обратили внимание на классы графов, для которых нахождение хроматического числа оказывается проще. Например, для планарных графов без треугольников выполняется теорема Грёча о 3-раскрашиваемости. В целом для графов без треугольников известна конструкция Мычельского, позволяющая строить графы со сколь угодно большим хроматическим числом. Однако при этом количество вершин растёт экспоненциально. Адылову С.Ш. была поставлена задача исследовать минимальность графов, получаемых конструкцией Мычельского. То есть верно ли, что граф M5 является минимальным по количеству вершин 5-раскрашиваемым графом без треугольников. Про M4 (граф Грёча) факт минимальности известен. Санжару удалось с помощью ограниченного перебора на компьютере показать отсутствие 5-раскрашиваемых графов среди произвольных графов без треугольников до 14 порядка включительно (у графа M4 11 вершин, а граф M5 имеет 23 вершины).
- Добавил в систему: Половников Владимир Сергеевич