- Полином Жегалкина
- Лемма
о рукопожатиях, следствия. Число ребер в полном графе.
- Матрица смежности, матрица Кирхгофа и ее свойства, список ребер,
матрица инцидентности. Связность.
- Теорема о двухсторонней оценке числа ребер в обыкновенном графе.
- Спектр графа, регулярный граф. Дополнение графа.
- Центр графа.
- Теорема о числе маршрутов определенной длины в графе.
- Теорема о числе ребер в обыкновенном связном графе. Теорема о числе
ребер в произвольном графе.
- Теорема об алгебраических дополнениях в матрице Кирхгофа. Число остовов.
- Кодировка дерева. Двоичная кодировка.
- Число остовов в полном графе (с доказательством) и теорема Кэли.
- Дерево. Листья. Лес. Ярус. Ствол. Высота. Код Прюфера.
- Сеть. Алгоритм Форда-Фалкерсона.
- Двудольный граф. Покрытие. Максимальное и наибольшее покрытие. Перманент.
- Задача о назначениях. Венгерский алгоритм.
- Кратчайший путь в орграфе. Алгоритм Дейкстры.
- Хорда. Фундаментальные циклы. Матрица фундаментальных циклов.
- Остов минимального веса. Два алгоритма решения задачи.
- Планарность. Плоский граф. Жорданова кривая. Подразбиение.
Гомеоморфность.
Теорема Понтрягина-Куратовского.
- Теорема
Эйлера о плоском графе.
- Раскраски. Хроматический индекс и хроматическое число. Оценки. Теорема
о редукции (с доказательством)
- Ранг. Коранг.
- Число вершинной и реберной связности.
- Связность. Разрез, мост.
- Центроид. Теорема Жордана о центре и центроиде.
- Основание графа. Сильно связный граф. Евклидов граф.
- Гамильтоновы графы.
- Доминирующее множество. Число доминирования. Полностью зависимое и
полностью независимое множество вершин. Число вершинной независимости.
Реберная независимость. Теорема о связи независимости и доминирования.
- Реберный граф. Число ребер.
- Триангуляция.
|