Основи теорії графів. Відкрита лекція 17/12/2021
Автор: Oleksandr Mokliachuk
Загружено: 2021-12-19
Просмотров: 719
Відкрита лекція була проведеня для групи ОФ-11 ФМФ КПІ.
Структура лекції:
0:00:00 - Вступ, історія теорії графів
0:03:55 - Базові означення
0:19:31 - Способи задання графів
0:32:37 - Основні види графів
0:39:51 - Операції над графами
0:50:55 - Ізоморфізм графів
0:55:13 - Алгоритм Гавела-Хакімі
1:07:35 - Зв'язність графів
1:23:53 - Ейлерові графи
1:29:17 - Розв'язок задачі про кенігзбергські мости
У лекції розглянуто основні поняття теорії графів. Наведена коротка історична довідка про виникнення теорії. Наведено базові означення, поняття графу, мультиграфу та орграфу. Розглянуто основні методи задання графів - діаграма, матриці суміжності та інцидентності, множинний перелік, послідовність степенів. Наведено основні операції, що можуть бути виконані на графах. Введено поняття ізоморфних графів, розглянуто проблему розв'язності задачі побудови графу за послідовністю степенів, алгоритм Гавела-Хакімі. Також вводиться поняття зв'язності графів. Розглядається ейлеровість графів, критерії ейлеровості та напівейлеровості, а також розв'язок класичної задачі про мости Кенігсбергу, що лягла в основу теорії графів.
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
