Дискретный анализ 3. Унициклические графы (продолжение). Гамильтоновы графы
Автор: Лекторий ФПМИ
Загружено: 2019-09-19
Просмотров: 1615
Описание:
0:00 Начало разговора. Напоминание и продолжение теоремы об асимптотике числа u_n унициклических графов на n вершинах
10:30 лемма 1
12:37 факт из анализа
31:55 гамильтоновы графы
35:37 признак Дирака (упражнение)
39:09 признак Эрдеша-Хвáтала (мотивировка)
40:38 (опр.) независимое множество вершин графа
42:47 (опр.) α(G) - число независимости графа (= размер самого большого независимого множества)
43:41 (опр.) ω(G) - кликовое число (= размер самой большой клики)
45:34 (опр.) (греческая буква каппа) κ(G) - вершинная связность
46:44 (опр.) порожденный (индуцированный) подграф
51:14 признак Эрдеша-Хвáтала (формулировка)
52:58 пример графа, подчиняющегося признаку Эрдеша-Хватала, но не признаку Дирака
====================
Лекция от 17.09.2019
Лектор - А.М. Райгородский
Снимал, монтировал - Юманов
Повторяем попытку...
Доступные форматы для скачивания:
Скачать видео
-
Информация по загрузке:
