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