Вы здесь

Хроматические числа графов, жадные алгоритмы раскраски и их уточнения

Лекция
Предмет:
Дата записи:
23.11.14
Дата публикации:
28.11.14
Код для блога:

В лекции мы расскажем о хроматических числах графов, т.е. об экстремальных характеристиках графов, равных наименьшему количеству цветов, в которые можно так раскрасить вершины графов, чтобы между вершинами одного цвета не было ребер. Сперва речь пойдет о жадных раскрасках, и пафос будет в том, что даже они дают в определенном смысле весьма точные результаты. Затем мы поговорим об уточнениях жадных раскрасок. А под конец поговорим о раскрасках случайных подграфов в некоторых последовательностях графов.

Страница лекции на сайте Computer Science клуба