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