Основные понятия.
Основные определения.
Способы задания графов.
Подграфы и дополнения.
Марщруты, цепи, пути и циклы.
Связность и компоненты графа.
Операции над графами.
Специальные графы.
Точки сочленения и разделимые графы.
Изоморфизм и 2- изоморфизм.
Деревья, разрезающие множества и циклы.
Деревья, остовы и кодеревья.
Элементарные свойства деревьев.
Корневые деревья.
Перечисление(оценки числа) деревьев.
Ранг и цикломатическое число.
Базисные циклы.
Разрезающие множества.
Разрез.
Базисные разрезающие множества.
Остовы, циклы и разрезающие множества.
Эйлеровы и гамильтоновы графы.
Эйлеровы (и полуэйлеровы) графы.Теорема Эйлера.
Гамильтоновы (и полугамильтоновы) графы.Теорема Дирака.
Графы и векторные пространства.
Группы и поля.
Векторное пространство графа.
Размерность подпространств циклов и разрезов.
Связь между подпространствами циклов и разрезов.
Ортогональность подпространств циклов и разрезов.
Ориентированные графы.
Графы и отношения.
Ориентированные и корневые деревья.
Ориентированные эйлеровы графы.
Ориентированные остовы и ориентированные эйлеровы цепи.
Ориентированные гамильтоновы графы.
Ациклические ориентированные графы.
Турниры.
Цепи Маркова.
|
|
|
Матрицы графов.
Матрица инциденций.
Матрица разрезов.
Цикломатическая матрица.
Соотношение ортогональности.
Подматрицы матриц разрезов, инциденций и циклов.
Унимодулярные матрицы.
Число остовов. Теорема Кэли.
Матрица смежности.
Планарность и двойственность.
Планарные (плоские) графы.
Теорема Эйлера о плоских графах и её следствия о непланарности графов
K3,3 и K5.
Теорема Понтрягина-Куратовского и другие характеризации планарности.
Графы на других поверхностях.
Двойственные графы. Планарность и двойственность.
Связность и паросочетания.
Связность или вершинная связность.
Реберная связность.
Теорема Менгера.
Паросочетания в двудольных графах. Теорема Холла и её следствия.
Покрытия и раскраски.
Независимые множества и вершинные покрытия.
Реберные покрытия.
Реберная раскраска и хроматический индекс.
Вершинная раскраска и хроматическое число.
Хроматические многочлены.
Теорема о пяти красках(доказательство).
Раскрашивание карт. Теорема о четырех красках.
Введение в теорию матроидов.
Основные определения.
Примеры матроидов.
|
|
|
Фундаментальные свойства.
Матроиды и теория графов.
Матроиды и “жадный” алгоритм.
Алгоритмы на графах.
Транзитивное замыкание. ( Алгоритмы Уоршолла и Уоррена.)
Обходы графов в глубину и ширину.
Кратчайшие пути. (Алгоритм Дейкстры.)
Алгоритм построения эйлерова цикла. (Алгоритм Флойда.)
Вычисление хроматического числа графа. (Алгоритм перебора с возвратами.)
Построение минимального остова графа. (Алгоритмы Крускала и Прима-Дейкстры.)
Потоки в траспортных сетях. Теорема Форда-Фалкерсона о максимальном потоке в транспортной сети. Помечающий алгоритм нахождения максимального потока в транспортной сети.
Нахождение максимальных внутренне устойчивых и минимальных внешне устойчивых множеств. (Алгоритмы Магу.)
Дата добавления: 2018-05-12; просмотров: 204; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!