Тема 10. Орграфы

Понятие орграфа. Основание орграфа. Вершина орграфа. Изоморфные орграфы. Матрица смежности орграфа. Ориентированный маршрут в орграфе. Орцепь. Орциклы. Сильный орграф. Слабый орграф. Односторонний орграф. Несвязный орграф. Порожденный орграф. Матрицы орграфов. Ориентированные эйлеровы графы.

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18], [19].

Тема 11. Ориентированные ациклические графы и деревья

Понятие ациклических графов. Понятие ориентированных ациклических графов. Понятие дерева. Лес. Остово дерево. Коциклический ранг графа. Остов лес. Фундаментальная система циклов.

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18], [19].

Тема 12. Планарность и двойственность

Понятие планарного графа. Графы Куратовского. Точки сочленения, мосты, блоки. Двойственные графы. Лемма. Абстрактно двойственные графы.

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18], [19].

Тема 13. ОрганизПоиск на графах

Исследование лабиринта. Поиск в глубину. Поиск в ширину. Нахождение кратчайшего пути (алгоритм Дейкстры).

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18], [19].

2. Контрольные работы, их характеристика