Лекция АСД от 03.04

[admin]

Лекция по Алгоритмам и структурам данных от 03.04.2020

Тема: "Графы. Способы представления графов. Исследование свойств графов"

Материал:
1) Бабичев стр 289-305 https://www.babichev.org/books/AlgoBook.pdf
2) https://www.sites.google.com/site/teori ... rii-grafov
3) http://www.apmath.spbu.ru/ru/education/ ... ection.pdf

Доп.литература:
1) Оре О. Теория графов. — М.: Наука, 1968.
2) Уилсон Р. Введение в теорию графов. — М.: Мир, 1977.

Контрольные вопросы:
1). Примеры применения графов
2). Варианты задания графов
3) Что такое смешанный граф?
4) Характеристики графов
5) Что такое гиперграф? Приведите примеры
6) Как реализовать граф программно?
7) Что такое объектный граф?
8) Маршруты, цепи и циклы в графе. Цикломатическое число. Свойства маршрутов и циклов.
9) Теорема об оценке числа ребер графа через число вершин и число компонент связности
10) Мосты и разделяющие вершины. Признаки моста. Вершинная и реберная связности. N-связные графы. Следствие из теоремы об оценке числа ребер графа через число вершин и число компонент связности.
11) Обход графа. Теорема о поисках в ширину и глубину.