Зимняя школа 2021: Александр Антоненко: Представление графов

Лекция доцента ОНУ им. И.И.Мечникова Александра Антоненко на тему "Представление графов" (базовый уровень) в рамках Зимней Школы Looksery 2021 по олимпиадному программированию.
Онлайн, 30.01.2021, в 16:00

Содержание:

00:00 Граф как математическая абстракция объектов реальности
07:37 Определение графа - множество вершин и ребер и их задание в компьютере числами
10:57 Примеры ребер - разница между графом и его изображением на плоскости
09:35 Терминология - степени вершин
19:13 Терминология - обыкновенный граф, количество ребер обыкновенного графа, пустой граф, дерево, полный граф
29:09 Представление графов - матрица смежности
41:11 Представление графов - матрица инциндентности
44:24 Представление графов - списки смежности
56:10 Представление графов - список ребер
01:00:33 Выводы относительно эффективного представления графов
01:02:17 Неявное хранение графа - лабиринт
01:10:11 Реализация матрицы смежности (C++)
01:27:22 Особенности обработки типа bool и vector элементов типа bool
01:39:18 Реализация списков смежности (C++)
01:56:44 Просмотр таблицы результатов и заключительные рекомендации
1) Контест — https://www.e-olymp.com/uk/contests/19434
2) Cлайды лекции — https://drive.google.com/file/d/1gMsTisZViL8tBlApl7FLp6ydAxK5VL9S/view?usp=sharing Данные слайды основаны на презенации Александра Александровича Кубенского http://www.myshared.ru/slide/202443/, она же http://amse.ru/courses/algorithms2/present/8_Graphs.ppt из курса http://amse.ru/courses/algorithms2/
3) Страница Зимней Школы в группе Google — https://groups.google.com/g/acm-onu-facult/c/PdxzRm576Tw

Видео Зимняя школа 2021: Александр Антоненко: Представление графов канала Alexander Antonenko