Матричные представления графов. Матрица смежности. Матрица инциденций. Матрица циклов. Точки сочленения, мосты и блоки. Графы блоков и графы точек сочленения. Описание деревьев. Теорема о числе всех деревьев. Остовные деревья. Теорема о числе всех остовных деревьев. Центры и центроиды в дереве. Деревья блоков и точек сочленения. Независимые циклы и коциклы. Матроиды.
ТЕМА 3. ЗАДАЧИ СОПОСТАВЛЕНИЯ ГРАФОВ, РАСКРАСКИ, ПЛАНАРНОСТЬ (4 часов)
Изоморфизм, гомоморфизм, автоморфизм графов. Алгоритмы сопоставления графов. Теоремы и оценки, относящиеся к хроматическим числам. Точные алгоритмы раскраски. Планарность графов. Алгоритм проверки планарности.
ТЕМА 4. ЗАДАЧИ ПОИСКА ГАМИЛЬТОНОВЫХ И ЭЙЛЕРОВЫХ ЦИКЛОВ. КРАТЧАЙШИЕ ЦЕПИ И ПУТИ. ОСТОВНЫЕ ДЕРЕВЬЯ. ДЕРЕВЬЯ ШТЕЙНЕРА (8 часов)
Эйлеровы циклы: алгоритм построения. Эйлеровы циклы и задача о китайском почтальоне. Гамильтоновы циклы. Алгебраический метод. Простая задача планирования. Задача поиска наикратчайшего гамильтонова цикла. Задача поиска кратчайшей цепи (пути) между парой заданных вершин. Алгоритм Дейстры. Задача поиска между каждой парой вершин. Алгоритм Флойда. Остовные деревья. Алгоритм построения всех остовных деревьев. Алгоритмы построения наикратчайшего остовного дерева. Задача Штейнера и подходы к ее решению.
