Дискретная математика: введение#
Источник: Хаггарти - Дискретная математика для программистов
“Дискретный” - составленный из отдельных частей.
Дискретная математика изучает множества конечной/счетной мощности и определенные на них структуры (кортежи, таблицы, графы). Компьютер можно смоделировать в виде дискретной математической системы. Чтобы понимать, как эта система устроена, мы этот предмет и изучаем.
Пример моделирования#
Поставим задачу выделить подмножество дорог, соединяющее все города между собой, суммарная длина которых будет минимальной. (Например, какие дороги надо отремонтировать, чтобы минимизировать стоимость ремонта?)
расстояние (в км) |
Вл |
Нах |
Усс |
Арт |
Арс |
См |
Шк |
Пог |
Пар |
Фок |
|---|---|---|---|---|---|---|---|---|---|---|
Владивосток |
172 |
98 |
45 |
239 |
75 |
66 |
195 |
160 |
118 |
|
Находка |
209 |
132 |
350 |
98 |
109 |
306 |
55 |
57 |
||
Уссурийск |
77 |
144 |
113 |
104 |
97 |
198 |
156 |
|||
Артем |
220 |
36 |
26 |
175 |
121 |
78 |
||||
Арсеньев |
255 |
246 |
209 |
340 |
298 |
|||||
Смоляниново |
11 |
208 |
98 |
43 |
||||||
Шкотово |
199 |
96 |
54 |
|||||||
Пограничный |
295 |
252 |
||||||||
Партизанск |
104 |
|||||||||
Фокино |
Формальная постановка задачи#
Имеем полный граф из 10 вершин.
Неформально, граф - это сеть из вершин, соединенных ребрами. Вершины изображают города, а ребра - дороги между ними. Каждое ребро помечено числом, называемым весом ребра.
Таким образом, в абстрактной формулировке нам нужно, имея таблицу весов ребер графа, найти его минимальное остовное дерево.
Определение. Остовным деревом графа \(G\) называют его подграф \(G'\), включающий все вершины графа \(G\), для которого выполняются условия:
\(G'\) связен: между любыми двумя вершинами \(G'\) существует путь в \(G'\)
\(G'\) ацикличен: в графе \(G'\) нет замкнутых путей (циклов)
Связный ациклический граф называется деревом.
Стоимостью остовного дерева назовем сумму весов его ребер.
Остовное дерево, имеющее минимально возможную стоимость (среди всевозможных остовных деревьев графа \(G\)), называется минимальным остовным деревом графа \(G\).
Алгоритм Прима#
Вход: граф \(G\)
Выход: минимальное остовное дерево графа \(G\), заданное как подмножество ребер
Шаг 1. Инициализация:
Шаг 1.1. Выбрать произвольную вершину \(u_0\) графа \(G\)
Шаг 1.2. Найти в множестве ребер \(\{(u_0, v) \colon v \text{ - вершина графа }G\}\) ребро с минимальным весом: \(d(u_0, v) \to \min\limits_v = d(u_0, v_0)\).
Шаг 1.3. Присоединить ребро \((u_0, v_0)\) к остовному дереву:
\(E' \leftarrow \{(u_0, v_0)\}; \quad V' \leftarrow \{u_0, v_0\}\)
Шаг 2. Цикл по числу вершин:
Положим \(k = 1\).
Пока не все вершины графа \(G\) присоединены к остовному дереву (т.е. \(V' \neq V\)), выполнять шаги:
Шаг 2.1. Найти в множестве рёбер \(\{(u, v) \colon u \in V', \; v \notin V', \; (u, v) \in E \}\) ребро \((u_k, v_k)\) с минимальным весом: \(d(u, v) \to \min\limits_{\substack{u \in V' \\ v \notin V' \\ (u, v) \in E}} = d(u_k, v_k)\)
Шаг 2.2. Присоединить ребро \((u_k, v_k)\) к остовному дереву; увеличить \(k\) на \(1\):
\(E' \leftarrow E' \cup \{(u_k, v_k)\}; \quad V' \leftarrow V' \cup \{v_k\}; \quad k \leftarrow k + 1\)
Шаг 3. Выдать ответ: граф \(G' = (V', E')\) - это минимальное остовное дерево графа \(G = (V, E)\).
Пример работы алгоритма#
\(u_0 = \text{Владивосток}\)
\(v_0 = \text{Артем}\)
\(d(u_0, v_0) = 45\)
\(u_1 = \text{Артем}\)
\(v_1 = \text{Шкотово}\)
\(d(u_1, v_1) = 26\)
\(u_2 = \text{Шкотово}\)
\(v_2 = \text{Смоляниново}\)
\(d(u_2, v_2) = 11\)
\(u_3 = \text{Смоляниново}\)
\(v_3 = \text{Фокино}\)
\(d(u_3, v_3) = 43\)
\(u_4 = \text{Фокино}\)
\(v_4 = \text{Находка}\)
\(d(u_4, v_4) = 57\)
\(u_5 = \text{Артем}\)
\(v_5 = \text{Уссурийск}\)
\(d(u_5, v_5) = 77\)
\(u_6 = \text{Шкотово}\)
\(v_6 = \text{Партизанск}\)
\(d(u_6, v_6) = 96\)
\(u_7 = \text{Уссурийск}\)
\(v_7 = \text{Пограничный}\)
\(d(u_7, v_7) = 97\)
\(u_8 = \text{Уссурийск}\)
\(v_8 = \text{Арсеньев}\)
\(d(u_8, v_8) = 144\)
Стоимость минимального остовного дерева равна \(45 + 26 + 11 + 43 + 57 + 77 + 96 + 97 + 144 = 596\)
Вопрос: Если граф \(G\) содержит \(n\) вершин и \(m\) ребер, то сколько вершин и ребер содержит остовное дерево графа \(G\)?
Упражнение. Выполните алгоритм Прима для подграфа, состоящего из 5 первых городов: Владивосток, Находка, Уссурийск, Артем, Арсеньев. Заполните таблицу \(u_k\; v_k, \; k = 0, 1, 2, 3\). Вычислите стоимость остовного дерева.
Пока работоспособность этого алгоритма для любого заданного графа - для нас магия; поэтому в разделе “Графы” мы строго проанализируем алгоритм и докажем его корректность.
Именно понимание алгоритмов, а не “умение” перепечатать готовый псевдокод на языках программирования делает вас хорошим программистом.
В доказательстве корректности алгоритма Прима используется метод математической индукции, которому посвящен наш первый раздел.