Жадный алгоритм раскраски графа. Теорема Эрдеша | Видеолекции Физтеха: Лекторий МФТИ - видеолекции по физике, математике, биологии, биоинформатике, информатике и другим дисциплинам

Оценки на хроматическое, кликовое число, число независимости, которые выполняются асимптотически почти наверное. Жадный алгоритм отыскания приближенного числа независимости, теоремы о качестве работы этого алгоритма. Обхват графа, теорема Эрдеша

Лекторы

Райгородский Андрей Михайлович

доктор физико-математических наук, профессор МФТИ и МГУ

Доктор физико-математических наук, заведующий кафедрой дискретной математики ФИВТ, научный руководитель бакалавриата кафедры "Анализ данных", главный редактор журнала Moscow Journal of Combinatorics and Number Theory.

Конспекты

Комментарий:

Осталось 512 из 512 символов.

Следующая лекция

МАТЕМАТИКА01:05:21

Теорема Эрдеша. Количество ребер в гиперграфе

10-я лекция из курса:

Дискретный анализ

Предыдущая лекция

МАТЕМАТИКА01:12:15

Связность G(n,p), гигантская компонента, характеристические числа G(n,p)

8-я лекция из курса:

Дискретный анализ

Московский физико-технический институт

Московский физико-технический институт (Физтех) – ведущий вуз России по подготовке высококвалифицированных специалистов по передовым направлениям науки и техники. Входит в топ 5 крупных рейтингов отечественных университетов. Отличительной чертой образовательного процесса МФТИ является система поиска и подготовки кадров – знаменитая «система Физтеха».

Скачайте наше мобильное приложение

iTunes

Google Play