|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Решение задач на графах с помощью нейронных сетей.дипломная работа (Бакалавр)
- Научный руководитель: Половников В.С.
- Автор: Адилов С.Ш.
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2018
- Аннотация: Хроматическое число графа, то есть минимальное количество красок, которые необходимы для правильной вершинной раскраски графа, издавна является предметом изучения. Хорошо известна проблема четырёх красок. Задача раскраски графов сложна и имеет практическое применение в проектировании интегральных схем, а также в теории кодирования и других областях. В работе Санжара Адилова изучается связь хроматического числа графов с их толщиной (минимальным числом планарных графов, объединение которых даёт исходный граф) и обхватом (длиной минимального цикла). Связь обхвата и хроматического числа произвольного графа была изучена венгерским математиком Палом Эрдёшем, который доказал, что для любого положительного k существует граф с обхватом g ≥ k и хроматическим числом χ(G) ≥ k. Другими словами, существуют графы со сколь угодно большими обхватом и хроматическим числом. Однако выяснилось, что при наложении ограничений на толщину графа, удаётся доказать оценку сверху на хроматическое число. Например, широко известно, что планарные графы (толщина 1) допускают правильную раскраску в 4 цвета, а для бипланарных графов (толщины не более 2) без треугольников выпускник кафедры МаТИС Роман Ищенко доказал, что их хроматическое число не превосходит 8. В своей выпускной работе Санжар обобщил результаты для бипланарных графов на случай произвольного обхвата, показал, что, начиная с обхвата 10, все бипланарные графы 5-раскрашиваемы. Далее Адилов С. Ш. с помощью этой же техники получил оценку хроматического числа графов произвольной заданной толщины k и обхвата g.
- Добавил в систему: Половников Владимир Сергеевич