Планарные графы

Вторник, 24 ноября 2020
Онлайн, занятие в zoom
Список тем / 25 записей
    1.
    Элементарная комбинаторика
    2.
    Сочетания
    3.
    Принцип включений-исключений
    4.
    Очень принципиальная практика
    5.
    Частично упорядоченные множества
    6.
    Принцип включений-исключений
    7.
    Группа перестановок
    8.
    Группа перестановок
    9.
    Разбиения числа в сумму слагаемых
    10.
    Разбиения числа в сумму слагаемых
    11.
    Рекуррентные соотношения. Числа Каталана и числа Белла
    12.
    Разбиения, производящие функции и рекурренты
    13.
    Методы линейной алгебры в комбинаторике
    14.
    Рекуррентные соотношения
    15.
    Основы теории графов
    16.
    Рекуррентные последовательности и линейная алгебра в комбинаторике
    17.
    Ориентированные графы
    18.
    Линейная алгебра в комбинаторике
    19.
    Раскраски графов
    20.
    Теория графов: вершины и рёбра
    21.
    Паросочетания и покрытия
    22.
    Ориентированные графы
    23.
    Планарные графы
    24.
    Паросочетания и планарные графы
    25.
    Разбор дополнительных заданий

Слайды с лекции

discrete_math_lecture_241120.pdf

Описание

Планарные и плоские графы. Формула Эйлера и следствия из нее. Понятие двойственного графа. Критерий раскрашиваемости граней в 2 цвета. Раскраска вершин планарного графа в 5 цветов. Гипотеза о четырех красках: формулировка, эквивалентность Тейта (б/д), обсуждение компьютерного доказательства. Теорема Куратовского (б/д).