ТГиК-2019-Лекция-28.10.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Комбинаторика разбиений

Сегодня мы рассмотрим количество способов представить число \(n\) в виде суммы других

\( n=a_1 + a_2 +...+ a_m\)

Пример

Пусть нам нужно представить число 6

\(6=1+1+1+1+1+1\\ 6=6\\ 6=2+1+1+1+1\\ 6=1+2+1+1+1\)

Обратим внимание на последние 2 разбиения. Если порядок важен, то это разные разбиения, а если не важен - одинаковые.

Разделим все разбиения на упорядоченные и неупорядоченные.

\( \mbox{Пусть } F(n; a_1, ..., a_m) - \mbox{ количество неупорядоченных разбиений} \\ f(n;a_1, ..., a_m) - \mbox{ количество упорядоченных разбиений} \)

Неупорядоченные разбиения

Рассмотрим 2 вида разбиений: те, в которых \(a_1\) есть, и те, в которых его нет. \((1)\)

Для тех, в которых \(a_1\) есть, рассмотрим небольшой пример для понимания дальнейших действий.

Пусть нам нужно разложить число 6, но в разбиении точно участвует число 2, то есть \(6=2+...\)

Многоточие - это ведь число 4. То есть дальше нам предстоит раскладывать число 4 с помощью тех же самых чисел, которые используются для разложения числа 6.\((2)\)

Из этого примера (2) и нашего разделения (1) выведем формулу\[F(n; a_1, ..., a_m) = F(n-a_1; a_1, ..., a_m) + F(n; a_2, ..., a_m) \]

Это будет рекурсия.

Упорядоченные разбиения

Принцип прост: мы фиксируем позицию и смотрим слагаемые, которые могут быть на этой позиции. Получим\[f(n;a_1, ..., a_m) = \sum^{m}_{i=1}{f(n-a_i; a_1, a_2. ..., a_m)} \]

Специальные случаи

Специальные случаи выглядят следующим образом\[F(n; 1, ..., n) \\ f(n;1, ..., n)\]

Применяются следующие обозначения

\(F(n; 1, ..., n)=p(n) \\ f(n;1, ..., n)=q(n)\)

Упорядоченные разбиения

Следующая формула выводится из предыдущего пункта для данного специального случая\[q(n)=\sum^{n-1}_{i=1}{q(i)}+1 \mbox{(замечание: при a_i = n получим единицу)}\]

Распишем подробно несколько начальных случаев, чтобы выявить закономерность. Для каждого \(i\) рассчитаем количество способов, которыми можно записать это число. Это и будет \(q_i\)

\(q_1=1 \mbox{, так как число 1 можно представить только одним способом: 1=1}\\ q_2=2 \mbox{, так как число 2 можно представить двумя способами: 2=1+1 и 2=2}\\ q_3=q_1+ q_2+1=4\\ q_k = 2^{k-1} \)

Следовательно, формулу можно записать так \(q(n)=\sum^{n-1}_{i=1}{q(i)}+1 = \sum^{n-2}_{i=0}{2^{i}}+1 = \mbox{ Здесь обратите внимание на рис.1. Из выявленного там результата получается ответ} = 2^{n-1}\)

\(\Longrightarrow f(n;1, ..., n) = 2^{n-1} \)

Неупорядоченные разбиения

Если для предыдущего пункта мы получили конкретный ответ, для данного случая у нас есть асимптотика

\(F(n; 1,2,...,n) = p(n) \sim \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}} \)

Формула в правой части - формула Харди-Рамануджана

Деревья

Рис.1. Вершины и "соседи"

Степень вершины - это количество рёбер, присоединенных к этой вершине.

\(deg(v) = | \left \{ e \in E | v \in e \right \} |\)

Теорема. Любое дерево, в котором есть хотя бы 2 вершины, содержит вершину степени 1.

Доказательство

Доказательство проведём от противного.

1) Пусть есть дерево \(T : \forall \mbox{ } v \in V_{T}\mbox{ } deg(v) \geqslant 2 \)

\(V_{T} = \left \{v_1, v_2, ..., v_n \right \} \)

2) Возьмём вершину \(v_1\) Так как степень вершины больше 2, то "сосед" вершины обязательно найдётся (рис.1. пункт а)

Аналогично для вершины \(v_2\), так как степень вершины больше 2, также найдётся "сосед" (рис.1. пункт б)

Аналогично для вершины \(v_3\) найдётся "сосед", причём он не совпадает с \(v_1\) и \(v_2\), так как иначе мы получим цикл, а это будет уже не дерево по определению (рис.1 пункт в)

3) Вершин - конечное число. Дойдём до вершины \(v_n\). Теперь ребро должно пойти назад. Получим цикл (рис.1 пункт г). Следовательно, получим граф, который не является деревом. Противоречие с предположением

Рис.2. Удаление вершин

Новое определение дерева

  • Пусть есть дерево \(T_n \).

Из теоремы можно сделать следующий вывод: в дереве \(T_n \) можно найти вершину \(v_n \in V_{T_n} : deg(v_n)=1 \) Удалим данную вершину вместе со связным ребром из \(T_n \) (рис. 2 пункт А) и получим новое дерево \(T_{n-1} \) (рис.2 пункт Б)

Аналогично в этом дереве можно найти вершину \(v_{n-1} \in V_{T_{n-1}} : deg(v_{n-1})=1 \) Удалим данную вершину вместе со связным ребром из \(T_{n-1} \) и так далее (рис.2 пункты В и Г). В конце у нас останется дерево из одной вершины \(T_1 \): это будет 1 вершина и 0 рёбер.

В конце - 1 вершина и 0 рёбер, поэтому в начале, в исходном дереве \(|V_{T_n}| = |E_{T_n}|+1 \)

  • Предположим, что дерево можно описать так: дерево - это граф, в котором \(|V|= |E|+1 \)
Рис.3. Пример для предположения

Для того, чтобы принять это определение, нам нужно доказать, что оно эквивалентно нашему начальному определению, а именно: дерево - это связный граф без циклов. То есть нужно доказать, что, если выполняется \(|V|= |E|+1 \), циклов в графе не будет.

Хмм, а что если привести пример такого графа, чтобы выполнялось и \(|V|= |E|+1 \), и были циклы? Обратим внимание на рис.3. Такой граф действительно существует.

  • Значит, выбранное нами определение не подходит. Заметим, что на рис.3 2 компоненты связности. Выберем новое определение: пусть дерево - это связный граф, в котором \(|V|= |E|+1 \)

Эквивалентность определений дерева

Рис.4. Граф с циклом и полученный связный граф

\((1):\) Дерево - это связный граф без циклов.

\((2):\) Дерево - это связный граф, в котором \(|V|= |E|+1 \)

Доказательство эквивалентности определений

\((1) \Longrightarrow (2):\) уже было приведено выше. Мы следовали первому определению как образцу.

\((2) \Longrightarrow (1):\)

1) Нам нужно доказать, что в графе, который является связным и в котором \(|V|= |E|+1 \), нет циклов. Доказательство проведём от противного.

2) Пусть есть G - связный граф, в G есть цикл и \(|V|= |E|+1 \)

3) Когда в графе есть цикл, это значит, что между двумя вершинами можно пойти двумя разными путями. Стало быть, можно удалить ребро (-а) с сохранением связности (рис. 4)

4) Удалим \(k\) рёбер. У нас всё ещё останется связный граф, но теперь он будет без циклов. Для связных графов без циклов было доказано до этого, что \(|V|= |E|+1 \)

5) \(k=|E'| - |E| = \mbox{ Количество вершин при удалении рёбер осталось прежним! } = |V| -1-|V|+1=0 \)

Получаем противоречие.

Рис.5. Обратная процедура

Ещё одно определение дерева

Рассмотрим обратную процедуру. Пусть у нас есть вершина без рёбер (рис.5 пункт А). Берём новую вершину и и связываем с какой-либо предыдущей вершиной (рис.5 пункты Б, В)

Назовём граф деревом, если он получается из одной вершины последовательностью операций добавления вершины, связанной ребром с одной из предыдущих вершин.

Применение

Рассмотрим разбиение множества A\[A=A_1 \sqcup A_2 \sqcup ... \sqcup A_m \]

Пусть есть некоторая абстрактная структура данных. Назовём её Лес не пересекающихся множеств (англ. Dispoint Set Union, сокр DSU). Она умеет делать 2 операции:

1) Операция Eq

Пусть есть элементы \( a_1, a_2\). Они находятся в одном подмножестве или в различных?

2) Операция Unite

Объединить 2 подмножества

Пусть есть некоторый граф G, обозначим DSU(n) - d.

Задача: есть несколько несвязанных друг с другом вершин. Как их объединить?

Решение (псевдокод)

result = n;
for e из E // e={v,u}
 if !(d.Eq(v,u)) 
{ result--;
d.Unite(v,u);}

Реализация DSU

Рис.6. root(v)

Разберёмся с этой "абстрактной структурой данных". Объявим DSU так:

1) \(root(v)\)

Зададим операцию \(root(v)\) следующим образом:в компоненте связности выбираем некоторую "главную" вершину. Для всех элементов данной компоненты связности эта "главная" вершина одинакова. Именно её и будет выводить операция \(root(v)\) (рис.6)
2) \(unite(v,u)\)

Рис.7

Рассмотрим "лес для 15 вершин" на рис.7. Заметим, что у каждой вершины 1 предок. Будем хранить всё в массиве.

root

Пусть root - элемент, который сам себе родитель. Реализация:

def root(v):
while parents(v)!=v
 v = parents(v);
return v;

unite

Реализация unite:

def unite(v,u):
parent(root(v))=root(u);

Схема проста: возьмём 2 root'а и сделаем одного родителем другого. Это медленная реализация.

Эвристики

Эвристика рангов

Зададим массив rank, где rank[i]=глубина дерева с корнем в вершине i

Сделаем код для unite оптимальнее. В той реализации не было принципа, по которому кто-то становился родителем. Создадим же его. Чей rank больше, тот и будет родителем при объединении.

def unite(v,u):
if rank(root(v)) > rank(root(u)) 
  parent(root(u)) = root(v);
else if rank(root(v)) < rank(root(u)) 
  parent(root(v)) = root(u);
else if rank(root(v)) == rank(root(u)) 
  {parent(root(u)) = root(v);
rank(root(v))+=1;}

Максимальная сложность этого алгоритма - \(\log n\)

Эвристика сжатия путей

Для всех, кто встретился, поменяем родителя на "главную" вершину

def root(v):
r=v;
while r!=parent(r):
 r=parent(r);

while v!=parent(v)
{s=parent(v);
parent(v)=r;
v=s;}
return r;

Оценка сложности операции на m элементов

1) \(\log^{*}{(m)}\)

Что это такое?

Возьмём логарифм от числа m - \( \log{m} \). Потом логарифм от этого логарифма - \( \log{(\log{m})} \). Далее будем брать логарифм от получившегося логарифма до тех пор, пока аргумент не будет меньше или равен 0. Количество этих логарифмов и есть \(\log^{*}{(m)}\) \[ \underbrace {\log{(\log{(...\log{m})})}}_{\log^{*}{(m)}}\]

Пример

Пусть \(\log^{*}_{2}{(m)}=3\). Каково m? m = \(4\).

Пусть \(\log^{*}_{2}{(m)}=4\). Каково m? m = \(2^4\).

2) Обратная функция Аккермана \(A^{-1}{(m)}\)