- •Содержание
- •1 Элементы теории множеств. Комбинаторика. 5
- •Математическая логика: Булева аллгебра 88
- •Теория алгоритмов 129
- •Теория графов 162
- •Математическая логика: Исчисления высказываний и предикатов 207
- •Элементы теории множеств. Комбинаторика.
- •Введение
- •Примеры задач.
- •Задача о расположении конвертов
- •Задача о Ханойской башне
- •Базовые обозначения
- •Правило суммы и правило произведения
- •Основы теории множеств
- •Понятие множества
- •Парадокс Рассела
- •Подмножества
- •Операции над множествами
- •Диаграммы Эйлера-Венна
- •Прямое произведение множеств
- •Бинарные отношения и функции
- •Бинарные отношения
- •Функции
- •Специальные бинарные отношения: Отношение эквивалентности
- •Специальные бинарные отношения: Отношение порядка
- •Лексикографический порядок
- •Выборки с повторениями и без повторений
- •Размещения и сочетания
- •Треугольник Паскаля
- •Связь сочетаний и (0,1)-векторов
- •Перебор сочетаний
- •Бином Ньютона
- •Мультимножества
- •Связь мультимножеств и (0,1)-векторов
- •Полином Ньютона
- •Разбиения множеств.
- •Приложение: программа перебора сочетаний
- •Перестановки
- •Понятие перестановки
- •Группа перестановок
- •Циклы перестановки
- •Тип перестановки
- •Разложения и разбиения натуральных чисел
- •Разложения натуральных чисел
- •Разбиения натуральных чисел
- •Принцип включения-исключения
- •Принцип включения-исключения
- •Задача о беспорядках
- •Мощность объединения множеств
- •Число целочисленных решений системы неравенств
- •Математическая логика: Булева аллгебра
- •Булева алгебра. Функции алгебры логики.
- •Булевы функции
- •Формулы
- •Основные тождества
- •Разложение функции по переменным
- •Дизъюнктивная и конъюнктивная нормальные формы
- •Полином Жегалкина
- •1 ⊕ X1 ⊕ x2x3 - полином Жегалкина.
- •Полнота системы функций
- •Функции, сохраняющие ноль
- •Функции, сохраняющие единицу
- •Двойственность
- •Монотонность
- •Линейность
- •Критерий полноты системы функций
- •Теория алгоритмов
- •Машины Тьюринга
- •Понятие алгоритма
- •Машина Тьюринга
- •Способы записи машины Тьюринга
- •Стандартные конфигурации
- •Вычислимые функции
- •Алгоритмически неразрешимые задачи
- •Сложность алгоритма
- •Полиномиальная сводимость
- •Классы задач в форме распознавания свойств
- •4 Теория графов
- •4.1 Определения графа
- •Общее определение
- •Виды графов
- •Обыкновенный граф
- •Примеры графов
- •Графы Бержа
- •4.2 Изоморфизм графов
- •4.2.1 Инварианты графа
- •Операции
- •Основные операции над графами
- •Подграфы
- •Дополнение графа
- •Маршруты и связность
- •Деревья
- •Матрицы, связанные с графом
- •Матрица смежности
- •Матрица инцидентности
- •Список ребер
- •Обходы графов
- •Эйлеров цикл
- •Гамильтонов цикл
- •Задачи и алгоритмы
- •Остов минимального веса
- •Алгоритм 4.8.1 (Алгоритм Краскала).
- •Задача коммивояжера
- •Задача о клике
- •Задача о вершинном покрытии
- •Задача о гамильтоновом цикле
- •Снова задача коммивояжера
- •Алгоритм дерева
- •Математическая логика: Исчисления высказываний и предикатов
- •Исчисление высказываний
- •Пример задачи логики высказываний
- •Формальные теории
- •Формальная теория исчисление высказываний
- •Теоремы исчисления высказываний
- •Теорема о полноте исчисления высказываний
- •Независимость аксиом исчисления высказываний
- •Исчисление предикатов
- •Пример задачи логики предикатов
- •Формальная теория исчисление предикатов
- •Алфавит.
- •Формулы.
- •Аксиомы.
- •Правила вывода.
- •Интерпретация
- •Литература
Гамильтонов цикл
Определение 4.7.3 . Гамильтоновым циклом в графе G называется цикл, который проходит через все вершины графа ровно по одному разу.
Определение 4.7.4 . Граф G называется гамильтоновым графом, если в нем есть гамильтонов цикл.
Определение гамильтонова графа похоже на определение эйлерова графа, но здесь нет такого удобного критерия для определения, является ли граф гамильтоновым. Как мы покажем позже, проверка графов на гамильтоновость является N P -полной задачей.
Задачи и алгоритмы
Остов минимального веса
Задача 4.8.1 . Пусть имеется n населенных пунктов и между некоторыми из них проложены не асфальтированные дороги известной длины. Необходимо заасфальтировать часть дорог таким образом, чтобы была возможность проехать по новой дороге из любого пункта в любой другой, и при этом, чтобы суммарная длина заасфальтированных дорог была минимальной.
Сформулируем задачу на языке графов.
Задача 4.8.2 . Дан граф G = (V, E) и весовая функция W , сопоставляющая каждму ребру положительное значение:
W : E → R+.
Будем считать весом любого подграфа H графа G суммарный вес его ребер:
W (H) = \
e∈E(H)
W (e).
Требуется найти такой связный остовной подграф G1 = (V, E1), чтобы его вес W (G1) был минимальным из весов всех остовных подграфов.
Очевидно, искомый подграф - дерево. С одной стороны он должен быть связен. С другой, если бы в нем имелся хотябы один цикл, мы смогли бы удалить любое ребро этого цикла и получить подграф, удовлетворяющий нашим требованиям, но меньшего веса.
Пример минимального остовного дерева для взвешенного графа приведен на рисунке 45.
8
3 4
1 4 5 4
2 6
4 5 5
4 7 7
5 3
6 6 5 5 9
8
Рисунок 45: Остов миниального веса
Приведем алгоритм решения этой задачи.
Алгоритм 4.8.1 (Алгоритм Краскала).
Пусть G = (V, E), |V | = n, W : E → R+.
e1 = arg mine∈E W (e).
i = 1; Gi = (V, Ei) = On + e1.
while(i < n − 1){
ei+1 = arg min
e∈E,
в Gi + e нет циклов
Gi+1 = Gi + ei+1; i = i + 1;
}
W (e);
На каждом шаге этого алгоритма мы выбираем самое "легкое" ребро графа, при добавлении которого у нас не образуется циклов вместе с уже выбранными ранее ребрами. Процесс завершается, когда мы выберем
n − 1 ребро. Чтобы убедиться, что этот алгоритм решает задачу об
остове минимального веса, нужно показать, что 1) мы действительно можем довести процесс до конца (всегда найдется такое n − 1 ребро);
построенный граф будет деревом; 3) это дерево будет минимальным по весу из всех остовных деревьев G.
Теорема 4.8.1 . Пусть граф G - связный граф. Тогда алгоритм Краскала строит минимальное остовное дерево.
Доказательство. 1) Во-первых, покажем, что агоритм всегда позволяет построить граф Gn−1.
Пусть на некотором шаге i (i < n−1) мы не смогли выбрать следующее
ребро ei+1. Значит не существует ни одного такого ребра e ∈ E, что в
Gi + e нет циклов.
Граф Gi не имеет циклов по построению. Если бы граф Gi был связен, то по теореме 4.5.1 в нем было бы n − 1 ребро. Так как i < n − 1, граф
Gi не является связным.
Пусть H произвольная компонента связности графа G. Поскольку граф G связен, в нем существует ребро e = (u, v), соединяющее некоторую вершину u компоненты H с вершиной v, которая не принадлежит H.
По нашему предположению, Gi + e будет иметь цикл. Этот цикл должен проходить по ребру e (иначе цикл был бы и в графе Gi). Но тогда этот цикл состоит из маршрута между вершинами u и v и ребра (u, v). То есть в графе Gi должен быть маршрут между вершинами u и v и они обе принадлежать одной компоненте связности H ?!
Покажем, что построенный в алгоритме граф Gn−1 есть дерево.
Действительно, выбирая каждое ребро мы проверяем, что у нас не должно появляться циклов. Когда мы выберем n − 1 ребро, по теореме
4.5.1 они образуют связный граф без циклов - остовное дерево графа G.
Наконец докажем, что построено дерево минимального веса.
Пусть Wmin(G) - вес минимального остовного дерева графа G. Пусть
S = {T | T = (V, E(T )) - остовное дерево грава G, W (T ) = Wmin(G)}.
Пусть T ∗ остовное дерево менимального веса, которое имеет наибольшее
число общих ребер с графом Gn−1:
T ∗ = arg max |E(Gn−1) ∩ E(T )|.
T ∈S
Будем доказывать от противного. Пусть Gn−1 не является минимальным остовным деревом. Тогда T ∗ не совпадает с Gn−1.
Пусть ei - первое ребро в Gn−1, которого нет в T ∗:
ei = (u, v) ∈ E(Gn−1) : ei ∈/ E(T ∗), и ∀j < i ⇒ ej ∈ E(T ∗).
Рассмотрим граф T ∗ + ei. В нем обязательно есть цикл C, так как T ∗ уже был связным графом - имел маршрут между вершинами u и v. Так как в графе Gn−1 нет циклов, в цикле C есть хотябы одно ребро et,
которого нет в Gn−1.
Рассмотрим граф T ∗ + ei − et. В этом графе нет циклов и он связен.
Значит T ∗ + ei − et остовное дерево. Вес T ∗ + ei − et не может быть меньше
веса минимального остовного дерева.
W (T ∗) + W (ei) − W (et) = W (T ∗ + ei − et) ≥ W (T ∗). (D)
Следовательно
W (ei) ≥ W (et). (∗)
Посмотрим с другой стороны. На i-том шаге алгоритма мы выбирали ребро ei как ребро минимального веса из всех невыбранных ребер, не образующих циклов с ребрами ej , j < i. Все ребра ej , j < i входят и в
дерево T ∗, а значит и ребро et не образует с ними цикла. Таким образом,
на i-том шаге алгоритма ребро et было кандидатом на выбор и было бы
выбрано, если бы W (et) < W (ei). Следовательно
W (ei) ≤ W (et). (∗∗)
Из неравенств (∗) и (∗∗) следует, что W (ei) = W (et) и по формуле (D)
W (T ∗ + ei − et) = W (T ∗) + W (ei) − W (et) = W (T ∗) = Wmin(G).
То есть T ∗ + ei − et является остовным деревом минимального веса. При этом у графа T ∗ + ei − et на одно общее ребро с графом Gn−1 больше, чем у T ∗, что противоречит выбору T ∗.
Противоречие вызвано предположением, что Gn−1 не является деревом минимального веса. Следовательно Gn−1, полученный с помощью алгоритма Краскала, есть минимальное остовное дерево, что и требовалось доказать.
D
Замечание 4.8.1 . Заметим, что алгоритм Краскала является алгоритмом полиномиальной сложности. Не будем доказывать это строго. Для этого потребовалось бы определять, какие операции мы считаем элементарными, описывать алгоритм в терминах этих операций и подсчитывать их число в худшем случае в зависимости от размеров задачи. Рассмотрим лишь возможность выполнения за полиномиальное время основных действий алгоритма.
В основном цикле алгоритма ровно n − 1 шаг. Самым трудоемким
пунктом в этом цикле является выбор ребра, который можно
разделить на два основных действия:
Выбор ребра e минимального веса.
Проверка, появится ли цикл в графе после добавления ребра e.
Можно однократно стоставить список ребер, упорядоченных по весу (алгоритм сортировки имеет сложность порядка n · log n). Тогда будем
каждый раз брать самое легкое ребро и удалять его из списка. Всего за все итерации цикла мы в худшем случае переберем все ребра.
Пусть e = (u, v) - ребро под вопросом. Необходимо определить, появится ли в графе Gi + e цикл. Достаточно проверить, был ли в графе Gi маршрут между вершинами u и v.
Будем приписывать метки вершинам начиная с вершины u и далее
все смежные с уже помеченными вершинами. Остановимся, если смежных с помеченными непомеченных вершин больше нет (рис. 46). Максимум нам удастся пометить i + 1 вершину, так как больше соединено ребрами быть не может. По окончании процесса нам останется только проверить, есть ли метка у вершины v. Если есть, в графе Gi + e присутствовал бы цикл. Если нет, ребро e может быть выбрано в качестве ei+1.
Итого, нам потребуется порядка n · log n действий, чтобы
отсортировать ребра, не более m действий выбора легких ребер, для
Рисунок 46: Проверка наличия маршрута между вершинами
каждого из которых нужно проверить наличие цикла, и порядка
const ·(n − 1) других действий
Замечание 4.8.2 . Этот алгоритм относится к так называемым жадным алгоритмам. Суть жадных алгоритмов состоит в том, чтобы на каждом шаге выбирать элемент с минимальным (или максимальным) значением некоторого параметра в итоге получая оптимальное решение.
Пример 4.8.1 . Легко убедиться, что жадный алгоритм применим не всегда. Например, рассмотрим задачу нахождения минимума суммы двух целых чисел с условием на значение их произведения.
x + y → min,
x · y = 30, x, y ∈ {2, 3, 5, 6, 10, 15}.
Очевидно, что решением этой задачи являются числа 5 и 6. В то же время следуя жадной стратегии мы должны были бы сначала выбрать самое маленькое значение x = 2, а затем подобрать наименьшее
значение для y, для которого выполняется условие x · y = 30 - y = 15.
Решение (2, 15) очевидно не является минимумом.
Жадный алгоритм здесь не дал правильного ответа.
N P -полные задачи теории графов