- •Оглавление
- •Введение
- •Комбинаторика в задачах
- •Основной принцип комбинаторики
- •Размещения с повторениями
- •Размещения без повторений
- •Разбиения множеств
- •Перестановки
- •Сочетания (без повторений)
- •Свойства биномиальных коэффициентов
- •Сочетания с повторениями
- •Разные задачи
- •Производящие функции
- •Использование рекуррентных соотношений
- •Формула включений и исключений
- •Комбинаторные величины при больших значениях параметров
- •Множества и функции
- •Множества и простейшие операции над ними
- •Булеан множества
- •Прямое произведение множеств
- •Отношения на множествах
- •Отображения (функции)
- •Мощность множеств
- •Счетные множества
- •Некоторые свойства бесконечных множеств
- •Вопросы для самопроверки
- •Упражнения
- •Основы теории графов
- •Основные понятия
- •Компьютерные представления графов
- •Маршруты и связность
- •Кратчайшие пути в графах
- •Деревья
- •Кодирование деревьев
- •Центр дерева
- •Минимальное остовное дерево (остов)
- •Эйлеровы графы
- •Гамильтоновы графы
- •Графовые векторы
- •Паросочетания и реберные покрытия
- •Паросочетания в двудольных графах
- •Правильная нумерация вершин графа
- •Сетевые графики
- •Потоки в сетях
- •Вопросы для самопроверки
- •Упражнения
- •Рекомендуемая литература
- •Предметный указатель
Вопросы для самопроверки
Что такое граф? Из чего он состоит? Какие виды графов вы знаете?
Какие вершины, дуги называются смежными? Инцидентными?
Какие графы называются изоморфными?
Что такое подграф? Какие виды подграфов вы знаете?
Что такое степень вершины? Полустепень входа и выхода?
Чему равна сумма степеней вершин графа?
Какие графы называются смежным и дополнительным к данному?
Как строятся матрицы смежности и инциденций графа?
Что такое маршрут, цепь, цикл, простая цепь, простой цикл?
Какие вершины называются достижимыми? Взаимно достижимыми?
Что такое компонента сильной связности (связности)?
Как строится матрица достижимости?
Как определяется взвешенный граф?
Что такое лес? Дерево?
Какими свойствами обладают деревья?
Сколько существует неизоморфных помеченных деревьев с данным числом вершин?
Что такое радиус, диаметр, центр графа?
Как устроен центр дерева?
Что такое минимальное остовное дерево взвешенного графа?
Что такое эйлеров цикл, эйлеров путь, эйлеров граф, полуэйлеров граф?
Каков критерий эйлеровости графа?
Что такое гамильтонов цикл, гамильтонов путь, гамильтонов граф, полугамильтонов граф?
Как формулируется теорема Дирака?
Как формулируется задача коммивояжера?
В чем идея методов поиска с возвращением и ветвей и границ?
Что такое графовый вектор?
Как проверить, что вектор является графовым?
Как устроен графовый вектор дерева?
Что такое паросочетание? Максимальное паросочетание?
Что такое реберное покрытие? Минимальное реберное покрытие?
Как связаны максимальное паросочетание и минимальное реберное покрытие
Что такое полное паросочетание в двудольном графе?
Каков критерий существования полного паросочетания в двудольном графе?
Что такое правильная нумерация вершин и в каких графах она существует?
Что такое сетевой график?
Какие пути в сетевом графике называются критическими?
Что такое поток в сети? Разрез сети?
Как связаны максимальный поток и минимальный разрез?
Упражнения
Существует ли неориентированный граф, степени всех вершин которого различны?
Постройте неориентированный граф, степени вершин которого равны 2,2,2,3,3,4,5. Существует ли такой граф?
Постройте все неизоморфные неориентированные графы, у которых 4, 5, 6 вершин. Тот же вопрос для ориентированных графов с 4 вершинами.
Докажите, что среди 6 человек найдется либо трое попарно знакомых, либо трое попарно не знакомых. А среди 5? Какое минимальное число людей надо взять, чтобы среди них нашлись либо двое попарно знакомых, либо двое попарно не знакомых? (Последний вопрос шуточный)
Докажите или опровергните изоморфизм данных пар графов.
Постройте дополнительные и смежные графы для данных графов.
Сколько существует неизоморфных помеченных графов с p вершинами?
Докажите, что смежный граф изоморфен исходному тогда и только тогда, когда он является объединением непересекающихся циклов.
Докажите, что число дуг графа, смежного к Г, равно
.Постройте матрицы смежности и инциденций для данных графов при различной нумерации вершин и дуг. Решите обратную задачу.
Докажите теорему Теорема 15.
Докажите теорему Теорема 16.
Найдите компоненты сильной связности графов, заданных матрицами смежности.
Проверьте или опровергните, что граф, заданный матрицей смежности, дерево.
Запишите код данного дерева.
Восстановите дерево по коду.
Найдите эксцентриситеты всех вершин данных графов (полного, двудольного, цикла, цепи и др.), найдите их радиус, диаметр и центр.
Найдите минимальное остовное дерево данных неориентированных взвешенных графов.
Установите, является ли данный вектор эйлеровым (полуэйлеровым) и при положительном заключении постройте эйлеров цикл (эйлерову цепь).
Постройте все гамильтоновы циклы данного графа, если они существуют.
Решите задачу коммивояжера для данных взвешенных графов.
Установите, является ли данный вектор графовым и при положительном заключении постройте соответствующий граф.
Найдите в данном графе максимальное паросочетание и минимальное реберное покрытие.
Постройте полное паросочетание в данном двудольном графе или докажите, что оно не существует.
Постройте критические пути в данном сетевом графике.
Найдите в графе при заданных начальной и конечной вершинах максимальный поток и минимальный разрез.
