1.История развития и области применения теории графов.
2.Теоретико-множественное определение и геометрическая интерпретация графа, связь между ними.
3.Ориентированный, неориентированный и смешанный графы. Обратный орграф и соотнесённый неориентированный граф.
4.Смежность и инцидентность вершин и рёбер. Задание графа с помощью отношений смежности и инцидентности. Кратные рёбра и параллельные дуги. Направленный граф.
5.Основные типы графов: конечный, простой, мультиграф, псевдограф, помеченный, полный, насыщенный, нуль-граф, k-дольный и полный k-дольный, звезда.
6.Изоморфизм графов. Инвариант графа. Подграф и надграф. Остовный и порождённый подграфы.
7.Степень вершины в неориентированном графе. Изолированная и висячая вершины. Теорема о сумме степеней вершин неориентированного графа и следствие из неё. Регулярный неориентированный граф.
8.Полустепени исхода и захода вершины в орграфе. Изолированная вершина, вход и выход. Степень вершины в орграфе. Теорема о сумме полустепеней исхода и захода в орграфе. Регулярный орграф.
9.Матричная форма задания графа и её значение. Матрицы смежности вершин неориентированного и ориентированного графов и их свойства. Критерий изоморфизма графов на языке матриц смежности их вершин. Ранг графа.
10.Матрицы инцидентности неориентированного и ориентированного графов и их свойства. Критерий изоморфизма графов на языке матриц инцидентности. Список рёбер графа.
11.Удаление вершины и ребра. Добавление ребра. Операция подразделения ребра графа и обратная ей. Гомеоморфизм графов.
12.Операция дополнения графа и её свойства. Самодополнительный граф. Теорема о матрице смежности вершин дополнения графа.
13.Операция объединения графов и её свойства. Теорема о матрице смежности вершин объединения графов и следствие из неё.
14.Операция пересечения графов и её свойства. Пустой граф. Теорема о матрице смежности вершин пересечения графов и следствие из неё.
15.Операция соединения графов, её применение и свойства.
16.Операция композиции графов и её свойства. Теорема о матрице смежности вершин композиции графов и замечание к ней.
17.Операция декартова произведение графов и её свойства. Теорема о матрице смежности вершин декартова произведения графов, следствие из неё и замечание. n-мерные кубы.
18.Операция прямого произведения графов и её свойства. Теорема о матрице смежности вершин прямого произведения графов, следствие из неё и замечание.
19.Геометрические графы в n-мерном евклидовом пространстве. Геометрическая реализация графа в n-мерном евклидовом пространстве. Теорема о реализуемости графов в трёхмерном пространстве.
20.Плоский и планарный графы. Геометрический граф на поверхности. Укладка графа на поверхности. Теорема об укладке графа на сфере. Применение свойства планарности. Проблема четырёх красок.
21.Свойство планарности и гомеоморфизм графов. Теорема Понтрягина-Куратовского. Графы К5 и К3,3. Планарность орграфа.
22.Цепи и циклы в неориентированном графе и их основные виды. Связные вершины в неориентированном графе. Связный неориентированный граф. Компонента связности неориентированного графа. Теорема о свойствах компонент связности неориентированного графа и следствие из неё. Мост в неориентированном графе.
23.Пути и контуры в ориентированном графе и их основные виды. Понятия сильной и односторонней связности для орграфов. Сильно связная компонента ориентированного графа. Критерий сильной связности орграфа.
24.Понятия дерева, ациклического графа, леса. Применения графов-деревьев. Теорема об основных свойствах деревьев. Ориентированное дерево и сеть сборки.
25.Теорема о числе концевых вершин в дереве. Понятие концевого ребра. Теорема А. Кэли о числе помеченных деревьев с заданным числом вершин. Построение кодовой последовательности дерева и восстановление дерева по его коду.
26.Каркас в неориентированном графе. Критерий существования каркаса в неориентированном графе. Нагруженный граф. Вес ребра (дуги). Задача о средствах сообщения.
27.Вес каркаса. Минимальный каркас. Правило экономичности или алгоритм Краскала и его обоснование.
28.Задача о кёнигсбергских мостах на языке теории графов. Эйлеровы цепь, цикл, путь, контур, граф. Другие задачи, связанные с эйлеровыми графами. Критерий Л. Эйлера существования эйлерова цикла в связном неориентированном графе.
29.Алгоритм Флёри нахождения эйлерова цикла в связном неориентированном графе и его обоснование. Второй критерий существования эйлерова цикла в связном неориентированном графе.
30.Критерий существования открытой эйлеровой цепи в связном неориентированном графе. Критерий существования эйлерова контура в сильно связном орграфе. Теорема об эквивалентных условиях для существования эйлерова контура в сильно связном орграфе. Критерий существования открытого эйлерова пути в сильно связном орграфе.
31.Головоломка «Кругосветное путешествие» У.Р. Гамильтона. Гамильтоновы цепь, цикл, путь, контур, граф. Аналогия между эйлеровыми и гамильтоновыми циклами и различие в степени сложности задач их нахождения. Задача коммивояжёра.
32.Внутренне устойчивое и полностью зависимое множества вершин. Максимальное независимое и наибольшее независимое множества вершин. Задача о восьми ферзях. Критерий максимальности внутренне устойчивого множества вершин. Число внутренней устойчивости графа.
33.Функция алгебры логики и её таблица истинности. Важные логические функции от одной и двух переменных. Суперпозиция логических функций и формула. Булевы формулы. Теорема о представлении логических функций булевыми формулами. Булева алгебра логических функций. Правило старшинства логических операций. Основные свойства булевых операций.
34.Элементарные конъюнкции (дизъюнкции). ДНФ, КНФ и их взаимные преобразования друг в друга. СДНФ и СКНФ. Импликанта и простая импликанта логической функции. Сокращённые ДНФ и КНФ и их получение. Минимальные ДНФ и КНФ и способы их получения. Метод испытания импликант.
35.Метод К. Магу нахождения максимальных внутренне устойчивых множеств вершин графа. Критерий внутренней устойчивости множества вершин в графе. Применение независимых множеств вершин графов в теории информации.
36.Внешне устойчивое множество вершин. Минимальное доминирующее и наименьшее доминирующее множества вершин. Задача о пяти ферзях. Число внешней устойчивости графа.
37.Метод К. Магу нахождения минимальных внешне устойчивых множеств вершин графа. Критерий внешней устойчивости множества вершин в графе. Применение наименьших доминирующих множеств вершин графов.
38.Ядро графа. Теорема о максимальной внутренней устойчивости ядра графа. Теорема о ядре в неориентированном графе и следствие из неё. Алгоритм построения ядра в неориентированном графе.
39.Прикладная задача о максимальной пропускной способности системы магистралей. Понятия сети, пропускной способности дуги, источника и стока. Транспортная сеть. Поток в транспортной сети и его величина. Разрез в транспортной сети и его пропускная способность. (s, t)-путь и его дуги.
40.Пара множеств. Лемма о свойствах функции, заданной на паре множеств. Лемма о соотношении величины потока и пропускной способности разреза.
41.Теорема Форда-Фалкерсона о величине максимального потока и следствие из неё.
42.Алгоритм Форда-Фалкерсона построения максимального потока и разреза с минимальной пропускной способностью в транспортной сети. Теорема о корректности алгоритма Форда-Фалкерсона.
43.Понятие множества. Примеры множеств. Элементы множества. Пустое множество. Подмножество. Собственные и несобственные подмножества. Равенство множеств. Конечные и бесконечные множества. Обозначения множеств и их элементов.
44.Способы задания множеств. Множество-степень или булеан множества. Корректность записи множества. Некоторые логические символы и их использование в теории множеств.
45.Операция объединения множеств и её свойства.
46.Операция пересечения множеств и её свойства.
47.Операция разности множеств и её свойства.
48.Универсальное множество и его свойства. Диаграмма Эйлера-Венна. Операция дополнения множества и её свойства.
49.Разбиение множества.
50.Понятие кортежа. Компоненты и длина кортежа. Упорядоченные n-ки. Равенство кортежей. Прямое произведение множеств.
51.Степень множества. Вещественные плоскость и трёхмерное пространство как степени множества. Понятие декартова произведения. Проектирование кортежей и множеств.
52.n-арная операция на множестве. Алгебра, её носитель, тип и сигнатура. Булева алгебра множеств. Булевы операции над множествами.
53.Дистрибутивность пересечения относительно объединения множеств. Дистрибутивность объединения относительно пересечения множеств. Методы доказательства тождеств алгебры множеств.
54.Тождества де Моргана. Понятие булевой алгебры. Операция симметрической разности множеств и её свойства.
55.Взаимно-однозначное соответствие между двумя множествами. Равномощные множества. Примеры.
56.Мощность конечного множества. Критерий равномощности конечных множеств. Общее число взаимно-однозначных соответствий для двух n-элементных множеств.
57.Теорема о мощности декартова произведения конечных множеств и следствие из неё о мощности степени конечного множества. Теорема о мощности булеана конечного множества. Число всех k-элементных подмножеств n-элементного множества.
58.Счётное множество. Счётность множеств целых и рациональных чисел. Счётность степени множества натуральных чисел. Свойства счётных множеств.
59.Несчётное множество. Теорема Г. Кантора. Мощность континуум. Континуальные множества. Диагональный метод Кантора.
60.Свойства несчётных множеств. Доказательство равномощности интервала (0,1) и полуинтервала (0,1]. Доказательство равномощности интервала (0,1) и отрезка [0,1].
61.Доказательство равномощности интервалов (0,1) и (a,b) с помощью центральной проекции. Доказательство континуальности множества всех вещественных чисел.
62.Континуальность булеана счётного множества. Несуществование множества максимальной мощности. Парадокс Кантора «множество всех множеств» и его разрешимость.
63.Соответствие между двумя множествами. Область отправления, область прибытия, график соответствия. Область определения и область значений соответствия. Отображение. Сюръективное соответствие. Образ и прообраз элемента. Образ и прообраз множества. Инъективное соответствие. Функциональное соответствие. Биективное соответствие. Функция. Инъективная, сюръективная и биективная функции.
64.Обратное соответствие. Композиция соответствий. Примеры.
65.Образ элемента и множества при отображении. Отображение на множество. Равные отображения. Виды отображений. Примеры.
66.Преобразование множества. Степень преобразования множества. Генеалогическое дерево.
67.Область определения и область значений функции. Аргумент и значение функции. Функция-константа. Тождественная функция. Вещественная функция. Композиция функций. n-местная функция. Суперпозиция функций. Формула.
68.Способы задания функций. Примеры. Некоммутативность композиции функций.
69.Сужение функции на множество. Обратная функция. Несуществование обратной функции и обратная функция к сужению функции на множество. Лемма об инъекции и сюръекции.
70.Критерий существования обратной функции. Свойства функций и их композиций. Теорема о связи свойств инъективности и сюръективности функции на конечном множестве.
71.Понятие функционала и его рассмотрение на примере. Использование функционалов в задачах управления. Оптимальное управление. Понятие брахистохроны.
72.Понятие оператора. Оператор дифференцирования. Операторы в задачах управления.
73.Термин «отношение». Понятие бинарного отношения. n-арное отношение. Понятие признака. Способы задания бинарных отношений. Матрица и граф бинарного отношения.
74.Операции над отношениями. Обратное отношение. Шесть основных свойств отношений. Примеры.
75.Отношение эквивалентности. Примеры отношений эквивалентности. Система классов эквивалентности. Индекс разбиения. Примеры систем классов эквивалентности.
76.Отношение порядка и его разновидности: нестрогий и строгий порядки. Сравнимость по отношению порядка. Полностью и частично упорядоченные множества. Примеры отношений порядка.
77.Отношение доминирования. Примеры отношений доминирования.