1. Основные понятия теории графов

Неориентированный граф

Степень вершины

Изолированная вершина

k-регулярный граф

Теорема о сумме степеней вершин графа. Следствие.

Простой неориентированный граф

Полный граф и пустой граф. Дополнение графа

Ориентированный граф

Входящая и исходящая степень вершины

Простой ориентированный граф

Понятие смежности в неориентированном и ориентированном графе

Задание графа в памяти компьютера

Количество простых неориентированных графов на n вершинах

Изоморфизм графов

Непомеченный граф

Автоморфизм графа. Группа автоморфизмов

Число способов разметки непомеченного графа

Турнир

Понятие подграфа

Остовный подграф

Индуцированный подграф

Понятие маршрута и его длина

Понятие пути в графе. Простой путь

Цикл и простой цикл в графе

Связанность вершин в неориентированном графе

Компоненты связности в графе. Связный граф

Связность вершин в орграфе. Сильно и слабо связный граф.

Компонента сильной связности в орграфе. Граф компонент сильной связности

Понятие дерева и леса. Лист.

Число листов и число рёбер в дереве, построенном на n вершин.

Какой граф точно является деревом? Следствие.

Минимально связный граф