Хроматические числа графов, жадные алгоритмы раскраски и их уточнения
В лекции мы расскажем о хроматических числах графов, т.е. об экстремальных характеристиках графов, равных наименьшему количеству цветов, в которые можно так раскрасить вершины графов, чтобы между вершинами одного цвета не было ребер. Сперва речь пойдет о жадных раскрасках, и пафос будет в том, что даже они дают в определенном смысле весьма точные результаты. Затем мы поговорим об уточнениях жадных раскрасок. А под конец поговорим о раскрасках случайных подграфов в некоторых последовательностях графов.
Страница лекции на сайте Computer Science клуба
АвторАндрей Райгородский
ОрганизаторComputer Science клуб при ПОМИ РАН
Онлайн-курсы по программированию
3
Машинное обучение для анализа текстов
От бизнес-идеи к ее реализации: учимся инновационному предпринимательству с нуля.
С платными опциями
Разработка игры-платформера на Defold: базовый уровень
Создайте свой первый платформер с нуля! За 7 недель вы не просто освоите движок Defold, а пройдете весь путь геймдев-разработчика: от кода и анимаций до дизайна и сюжета.
Бесплатный
Python для начинающих
Курс посвящен основам программирования на языке Python — одном из самых популярных и понятных языков, идеально подходящих для первого знакомства с IT.
Бесплатный