Викиконспекты - Вклад участника [ru]

Алгоритм Шибера-Вишкина

2012-06-21T16:37:42Z

109.188.219.181: /* Обработка запроса */

''Алгоритм Шибера-Вишкина'' применяется для нахождения наименьшего общего предка двух вершин в дереве.
Он использует <tex>O(n)</tex> времени на подготовку и затем отвечает на каждый запрос за <tex>O(1)</tex>.

==Идея алгоритма==
Основная идея алгоритма следующая.

# Если бы дерево, в котором нужно искать <tex>LCA</tex> было бы цепочкой, можно было бы найти <tex>LCA(u, v)</tex> просто взяв ту вершину, которая находится в дереве выше.
# Если дерево {{---}} полное двоичное дерево высоты <tex>h</tex>, то можно сопоставить каждой вершине битовый вектор длиной <tex>h</tex> (целое число от <tex>0</tex> до <tex>2^h-1</tex>) и с помощью битовых операций над этими векторами найти <tex>LCA(u, v)</tex>

Тогда, представив данное дерево как полное двоичное дерево, в каждой вершине которого находится цепочка, можно
научиться искать <tex>LCA(v, u)</tex> в нем за <tex>O(1)</tex>.

==Подготовка==
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обрабатывается текущая вершина, затем {{---}} поддеревья.
Пусть <tex>\operatorname{order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.

Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем,
что вершина является и своим предком, и своим потомком.

{{Утверждение
|statement=Пусть <tex>u</tex> {{---}} вершина из поддерева <tex>v</tex>. Тогда
<tex>\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{order}</tex>, <tex>\operatorname{order} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{order}v + 1</tex>, то <tex>\operatorname{order} u</tex> {{---}} отрезок <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>.
}}

Покроем дерево путями. А именно, сопоставим каждой вершине <tex>v</tex> число <tex>\operatorname{inlabel} v</tex> такое, что прообраз каждого <tex>\operatorname{inlabel} v</tex> в <tex>T</tex> связен и является простым путем от какой-то вершины вниз до листа.

{{Утверждение
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{inlabel} v = \operatorname{order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
Пусть есть вершина <tex>u' \in S(i)</tex> такая, что <tex>\operatorname{order} u' = k'2^b</tex>.
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{inlabel} v</tex> выбран неверно.
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>\operatorname{order} u \hdots 2^{max}</tex>.

Рассмотрим два случая.

'''Первый случай''' <tex>\operatorname{inlabel} v = \operatorname{order} v</tex>
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inlabel}</tex> отличаются
от <tex>\operatorname{inlabel} v</tex>.

'''Второй случай''' <tex>\operatorname{inlabel} v = \operatorname{order} u</tex>, <tex>u \in S(v), u \ne v</tex>
Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{inlabel} w = \operatorname{inlabel} v = \operatorname{order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inlabel} v' = \operatorname{inlabel} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое.
}}

{{Утверждение
|statement=<tex>\operatorname{inlabel} v = 2^i (\frac{\operatorname{order} v + \operatorname{size} v}{2^i})</tex>, где <tex>i = \lfloor\log_2 (\operatorname{order} v \oplus (\operatorname{order} v + \operatorname{size} v)) \rfloor + 1</tex>
|proof=
Посмотрим на <tex>A = \operatorname{order} v \oplus (\operatorname{order} v + \operatorname{size} v)</tex>.
Посмотрим на позицию самой правой единицы <tex>l</tex> в <tex>A</tex>.

Так как в <tex>\operatorname{order} v</tex> там еще <tex>0</tex>, а в <tex>\operatorname{order} v + \operatorname{size} v</tex> {{---}} уже единица, то в отрезке <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v]</tex> есть число, кратное <tex>2^l</tex>.

Докажем, что нет чисел, кратных <tex>2^{l+1}</tex>. Пусть такое число нашлось. Тогда <tex>l</tex>-й бит менялся хотя бы два раза, а значит, менялся
<tex>l+1</tex>-й бит. А значит, самый значащий отличающийся бит в <tex>\operatorname{order} v</tex> и в <tex>\operatorname{order} v + \operatorname{size} v</tex> больше, чем <tex>l</tex>-й.

Заметим, что функция <tex>\lfloor \log_2 a \rfloor + 1</tex> просто выделяет номер самого значашего единичного бита.

Функция <tex>2^l\frac{a}{2^l}</tex> обнуляет все биты младше <tex>l</tex>-го.

Чтобы получить из отрезка число, кратное <tex>2^l</tex>, будучи уверенными, что оно там есть, достаточно обнулить <tex>l</tex> битов в правой границе отрезка.
}}

==Обработка запроса==
Пусть <tex>x</tex>, <tex>y</tex> {{---}} вершины в исходном дереве <tex>LCA</tex> которых необходимо найти. Если <tex>\operatorname{inlabel} x = \operatorname{inlabel} y</tex>, то они принадлежат одному простому пути, а следовательно ответом на запрос является <tex>x</tex>, если <tex>\operatorname{level} x \le \operatorname{level} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям. Найдем <tex>b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>.

{{Утверждение
|statement= <tex>LCA(\operatorname{inlabel} x, \operatorname{inlabel} y) = 2^i((2(\frac x{2^{i+1}})) \,|\, 1)</tex>, где <tex>i = \log(\operatorname{inlabel} x \oplus \operatorname{inlabel} y)</tex>
|proof= Пусть <tex>i</tex> {{---}} индекс самой правой единицы в двоичном представлении <tex>b</tex>. Из того, что <tex>b</tex> общий предок <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex> в полном двоичном дереве следует, что <tex>l-i</tex> левых бит, совпадающих в <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>, должны быть такими же и в <tex>b</tex>, а так как <tex>b</tex> наименьший общий предок, то <tex>i</tex> {{---}} минимальный такой индекс. То есть <tex>i</tex> самый левый бит, в котором различаются <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>. А двоичное представление <tex>b</tex> состоит из <tex>l-i</tex> левых бит <tex>\operatorname{inlabel} x</tex> (или <tex>\operatorname{inlabel} y</tex>), единички и <tex>i</tex> нулей.
}}

Алгоритм Шибера-Вишкина

2012-06-21T16:36:57Z

109.188.219.181: /* Подготовка */

''Алгоритм Шибера-Вишкина'' применяется для нахождения наименьшего общего предка двух вершин в дереве.
Он использует <tex>O(n)</tex> времени на подготовку и затем отвечает на каждый запрос за <tex>O(1)</tex>.

==Идея алгоритма==
Основная идея алгоритма следующая.

# Если бы дерево, в котором нужно искать <tex>LCA</tex> было бы цепочкой, можно было бы найти <tex>LCA(u, v)</tex> просто взяв ту вершину, которая находится в дереве выше.
# Если дерево {{---}} полное двоичное дерево высоты <tex>h</tex>, то можно сопоставить каждой вершине битовый вектор длиной <tex>h</tex> (целое число от <tex>0</tex> до <tex>2^h-1</tex>) и с помощью битовых операций над этими векторами найти <tex>LCA(u, v)</tex>

Тогда, представив данное дерево как полное двоичное дерево, в каждой вершине которого находится цепочка, можно
научиться искать <tex>LCA(v, u)</tex> в нем за <tex>O(1)</tex>.

==Подготовка==
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обрабатывается текущая вершина, затем {{---}} поддеревья.
Пусть <tex>\operatorname{order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.

Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем,
что вершина является и своим предком, и своим потомком.

{{Утверждение
|statement=Пусть <tex>u</tex> {{---}} вершина из поддерева <tex>v</tex>. Тогда
<tex>\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{order}</tex>, <tex>\operatorname{order} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{order}v + 1</tex>, то <tex>\operatorname{order} u</tex> {{---}} отрезок <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>.
}}

Покроем дерево путями. А именно, сопоставим каждой вершине <tex>v</tex> число <tex>\operatorname{inlabel} v</tex> такое, что прообраз каждого <tex>\operatorname{inlabel} v</tex> в <tex>T</tex> связен и является простым путем от какой-то вершины вниз до листа.

{{Утверждение
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{inlabel} v = \operatorname{order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
Пусть есть вершина <tex>u' \in S(i)</tex> такая, что <tex>\operatorname{order} u' = k'2^b</tex>.
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{inlabel} v</tex> выбран неверно.
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>\operatorname{order} u \hdots 2^{max}</tex>.

Рассмотрим два случая.

'''Первый случай''' <tex>\operatorname{inlabel} v = \operatorname{order} v</tex>
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inlabel}</tex> отличаются
от <tex>\operatorname{inlabel} v</tex>.

'''Второй случай''' <tex>\operatorname{inlabel} v = \operatorname{order} u</tex>, <tex>u \in S(v), u \ne v</tex>
Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{inlabel} w = \operatorname{inlabel} v = \operatorname{order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inlabel} v' = \operatorname{inlabel} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое.
}}

{{Утверждение
|statement=<tex>\operatorname{inlabel} v = 2^i (\frac{\operatorname{order} v + \operatorname{size} v}{2^i})</tex>, где <tex>i = \lfloor\log_2 (\operatorname{order} v \oplus (\operatorname{order} v + \operatorname{size} v)) \rfloor + 1</tex>
|proof=
Посмотрим на <tex>A = \operatorname{order} v \oplus (\operatorname{order} v + \operatorname{size} v)</tex>.
Посмотрим на позицию самой правой единицы <tex>l</tex> в <tex>A</tex>.

Так как в <tex>\operatorname{order} v</tex> там еще <tex>0</tex>, а в <tex>\operatorname{order} v + \operatorname{size} v</tex> {{---}} уже единица, то в отрезке <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v]</tex> есть число, кратное <tex>2^l</tex>.

Докажем, что нет чисел, кратных <tex>2^{l+1}</tex>. Пусть такое число нашлось. Тогда <tex>l</tex>-й бит менялся хотя бы два раза, а значит, менялся
<tex>l+1</tex>-й бит. А значит, самый значащий отличающийся бит в <tex>\operatorname{order} v</tex> и в <tex>\operatorname{order} v + \operatorname{size} v</tex> больше, чем <tex>l</tex>-й.

Заметим, что функция <tex>\lfloor \log_2 a \rfloor + 1</tex> просто выделяет номер самого значашего единичного бита.

Функция <tex>2^l\frac{a}{2^l}</tex> обнуляет все биты младше <tex>l</tex>-го.

Чтобы получить из отрезка число, кратное <tex>2^l</tex>, будучи уверенными, что оно там есть, достаточно обнулить <tex>l</tex> битов в правой границе отрезка.
}}

==Обработка запроса==
Пусть <tex>x</tex>, <tex>y</tex> {{---}} вершины в исходном дереве <tex>LCA</tex> которых необходимо найти. Если <tex>\operatorname{inlabel} x = \operatorname{inlabel} y</tex>, то они принадлежат одному простому пути, а следовательно ответом на запрос является <tex>x</tex>, если <tex>\operatorname{level} x \le \operatorname{level} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям. Найдем <tex>b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>.

{{Утверждение
|statement= <tex>\operatorname{inlabel} LCA(x, y) = 2^i((2(\frac x{2^{i+1}})) \,|\, 1)</tex>, где <tex>i = \log(\operatorname{inlabel} x \oplus \operatorname{inlabel} y)</tex>
|proof= Пусть <tex>i</tex> {{---}} индекс самой правой единицы в двоичном представлении <tex>b</tex>. Из того, что <tex>b</tex> общий предок <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex> в полном двоичном дереве следует, что <tex>l-i</tex> левых бит, совпадающих в <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>, должны быть такими же и в <tex>b</tex>, а так как <tex>b</tex> наименьший общий предок, то <tex>i</tex> {{---}} минимальный такой индекс. То есть <tex>i</tex> самый левый бит, в котором различаются <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>. А двоичное представление <tex>b</tex> состоит из <tex>l-i</tex> левых бит <tex>\operatorname{inlabel} x</tex> (или <tex>\operatorname{inlabel} y</tex>), единички и <tex>i</tex> нулей.
}}

Алгоритм Шибера-Вишкина

2012-06-21T15:19:57Z

109.188.219.181: /* Обработка запроса */

''Алгоритм Шибера-Вишкина'' применяется для нахождения наименьшего общего предка двух вершин в дереве.
Он использует <tex>O(n)</tex> времени на подготовку и затем отвечает на каждый запрос за <tex>O(1)</tex>.

==Идея алгоритма==
Основная идея алгоритма следующая.

# Если бы дерево, в котором нужно искать <tex>LCA</tex> было бы цепочкой, можно было бы найти <tex>LCA(u, v)</tex> просто взяв ту вершину, которая находится в дереве выше.
# Если дерево {{---}} полное двоичное дерево высоты <tex>h</tex>, то можно сопоставить каждой вершине битовый вектор длиной <tex>h</tex> (целое число от <tex>0</tex> до <tex>2^h-1</tex>) и с помощью битовых операций над этими векторами найти <tex>LCA(u, v)</tex>

Тогда, представив данное дерево как полное двоичное дерево, в каждой вершине которого находится цепочка, можно
научиться искать <tex>LCA(v, u)</tex> в нем за <tex>O(1)</tex>.

==Подготовка==
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обходится текущая вершина, затем {{---}} поддеревья.
Пусть <tex>\operatorname{order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.

Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем,
что вершина является и своим предком, и своим потомком.

{{Утверждение
|statement=Пусть <tex>u</tex> {{---}} вершина из поддерева <tex>v</tex>. Тогда
<tex>\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{order}</tex>, <tex>\operatorname{order} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{order}v + 1</tex>, то <tex>\operatorname{order} u</tex> {{---}} отрезок <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>.
}}

Покроем дерево путями. А именно, сопоставим каждой вершине <tex>v</tex> число <tex>\operatorname{inlabel} v</tex> такое, что прообраз каждого <tex>\operatorname{inlabel} v</tex> в <tex>T</tex> связен и является простым путем от какой-то вершины вниз до листа.

{{Утверждение
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{inorder} v = \operatorname{order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
Пусть есть вершина <tex>u' \in S(i)</tex> такая, что <tex>\operatorname{order} u' = k'2^b</tex>.
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{inorder} v</tex> выбран неверно.
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>\operatorname{order} u \hdots 2^{max}</tex>.

Рассмотрим два случая.

'''Первый случай''' <tex>\operatorname{inorder} v = \operatorname{order} v</tex>
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inorder}</tex> отличаются
от <tex>\operatorname{inorder} v</tex>.

'''Второй случай''' <tex>\operatorname{inorder} v = \operatorname{order} u</tex>, <tex>u \in S(v), u \ne v</tex>
Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{inorder} w = \operatorname{inorder} v = \operatorname{order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inorder} v' = \operatorname{inorder} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое.
}}

==Обработка запроса==
Пусть <tex>x</tex>, <tex>y</tex> {{---}} вершины в исходном дереве <tex>LCA</tex> которых необходимо найти. Если <tex>\operatorname{inlabel} x = \operatorname{inlabel} y</tex>, то они принадлежат одному простому пути, а следовательно ответом на запрос является <tex>x</tex>, если <tex>\operatorname{level} x \le \operatorname{level} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям. Найдем <tex>b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>.

{{Утверждение
|statement= <tex>\operatorname{inlabel} (((x >> (i + 1)) << 1) | 1) << i</tex>, где <tex>i = \log(\operatorname{inlabel} x \oplus \operatorname{inlabel} y)</tex>
|proof= Пусть <tex>i</tex> {{---}} индекс самой правой единицы в двоичном представлении <tex>b</tex>. Из того, что <tex>b</tex> общий предок <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex> в полном двоичном дереве следует, что <tex>l-i</tex> левых бит, совпадающих в <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>, должны быть такими же и в <tex>b</tex>, а так как <tex>b</tex> наименьший общий предок, то <tex>i</tex> {{---}} минимальный такой индекс. То есть <tex>i</tex> самый левый бит, в котором различаются <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>. А двоичное представление <tex>b</tex> состоит из <tex>l-i</tex> левых бит <tex>\operatorname{inlabel} x</tex> (или <tex>\operatorname{inlabel} y</tex>), единички и <tex>i</tex> нулей.
}}

Алгоритм Шибера-Вишкина

2012-06-21T14:56:27Z

109.188.219.181: /* Подготовка */

''Алгоритм Шибера-Вишкина'' применяется для нахождения наименьшего общего предка двух вершин в дереве.
Он использует <tex>O(n)</tex> времени на подготовку и затем отвечает на каждый запрос за <tex>O(1)</tex>.

==Идея алгоритма==
Основная идея алгоритма следующая.

# Если бы дерево, в котором нужно искать <tex>LCA</tex> было бы цепочкой, можно было бы найти <tex>LCA(u, v)</tex> просто взяв ту вершину, которая находится в дереве выше.
# Если дерево {{---}} полное двоичное дерево высоты <tex>h</tex>, то можно сопоставить каждой вершине битовый вектор длиной <tex>h</tex> (целое число от <tex>0</tex> до <tex>2^h-1</tex>) и с помощью битовых операций над этими векторами найти <tex>LCA(u, v)</tex>

Тогда, представив данное дерево как полное двоичное дерево, в каждой вершине которого находится цепочка, можно
научиться искать <tex>LCA(v, u)</tex> в нем за <tex>O(1)</tex>.

==Подготовка==
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обходится текущая вершина, затем {{---}} поддеревья.
Пусть <tex>\operatorname{order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.

Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем,
что вершина является и своим предком, и своим потомком.

{{Утверждение
|statement=Пусть <tex>u</tex> {{---}} вершина из поддерева <tex>v</tex>. Тогда
<tex>\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{order}</tex>, <tex>\operatorname{order} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{order}v + 1</tex>, то <tex>\operatorname{order} u</tex> {{---}} отрезок <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>.
}}

Покроем дерево путями. А именно, сопоставим каждой вершине <tex>v</tex> число <tex>\operatorname{inlabel} v</tex> такое, что прообраз каждого <tex>\operatorname{inlabel} v</tex> в <tex>T</tex> связен и является простым путем от какой-то вершины вниз до листа.

{{Утверждение
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{inorder} v = \operatorname{order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
Пусть есть вершина <tex>u' \in S(i)</tex> такая, что <tex>\operatorname{order} u' = k'2^b</tex>.
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{inorder} v</tex> выбран неверно.
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>\operatorname{order} u \hdots 2^{max}</tex>.

Рассмотрим два случая.

'''Первый случай''' <tex>\operatorname{inorder} v = \operatorname{order} v</tex>
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inorder}</tex> отличаются
от <tex>\operatorname{inorder} v</tex>.

'''Второй случай''' <tex>\operatorname{inorder} v = \operatorname{order} u</tex>, <tex>u \in S(v), u \ne v</tex>
Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{inorder} w = \operatorname{inorder} v = \operatorname{order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inorder} v' = \operatorname{inorder} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое.
}}

==Обработка запроса==
Пусть <tex>x</tex>, <tex>y</tex> {{---}} вершины в исходном дереве <tex>LCA</tex> которых необходимо найти. Если <tex>\operatorname{inlabel} x = \operatorname{inlabel} y</tex>, то они принадлежат одному простому пути, а следовательно ответом на запрос является <tex>x</tex>, если <tex>\operatorname{level} x \le \operatorname{level} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям. Найдем <tex>b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>.

{{Утверждение
|statement= <tex>\operatorname{inlabel} (((x >> (i + 1)) << 1) | 1) << i</tex>, где <tex>i = \log(\operatorname{inlabel} x \oplus \operatorname{inlabel} y)</tex>
|proof= ?
}}

Алгоритм Шибера-Вишкина

2012-06-21T14:53:34Z

109.188.219.181:

''Алгоритм Шибера-Вишкина'' применяется для нахождения наименьшего общего предка двух вершин в дереве.
Он использует <tex>O(n)</tex> времени на подготовку и затем отвечает на каждый запрос за <tex>O(1)</tex>.

==Идея алгоритма==
Основная идея алгоритма следующая.

# Если бы дерево, в котором нужно искать <tex>LCA</tex> было бы цепочкой, можно было бы найти <tex>LCA(u, v)</tex> просто взяв ту вершину, которая находится в дереве выше.
# Если дерево {{---}} полное двоичное дерево высоты <tex>h</tex>, то можно сопоставить каждой вершине битовый вектор длиной <tex>h</tex> (целое число от <tex>0</tex> до <tex>2^h-1</tex>) и с помощью битовых операций над этими векторами найти <tex>LCA(u, v)</tex>

Тогда, представив данное дерево как полное двоичное дерево, в каждой вершине которого находится цепочка, можно
научиться искать <tex>LCA(v, u)</tex> в нем за <tex>O(1)</tex>.

==Подготовка==
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обходится текущая вершина, затем {{---}} поддеревья.
Пусть <tex>\operatorname{order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.

Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем,
что вершина является и своим предком, и своим потомком.

{{Утверждение
|statement=Пусть <tex>u</tex> {{---}} вершина из поддерева <tex>v</tex>. Тогда
<tex>\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{order}</tex>, <tex>\operatorname{order} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{order}v + 1</tex>, то <tex>\operatorname{order} u</tex> {{---}} отрезок <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>.
}}

Покроем дерево путями. А именно, сопоставим каждой вершине <tex>v</tex> число <tex>\operatorname{inlabel} v</tex> такое, что прообраз каждого <tex>\operatorname{inlabel} v</tex> в <tex>T</tex> связен и является простым путем от какой-то вершины вниз до листа.

{{Утверждение
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{inorder} v = \operatorname{order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
Пусть есть вершина <tex>u' \in S(i)</tex> такая, что <tex>\operatorname{order} u' = k'2^b</tex>.
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{inorder} v</tex> выбран неверно.
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>\operatorname{order} u \hdots 2^{max}</tex>.

Рассмотрим два случая.
''Первый случай'' <tex>\operatorname{inorder} v = \operatorname{order} v</tex>
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inorder}</tex> отличаются
от <tex>\operatorname{inorder} v</tex>.

''Второй случай'' <tex>\operatorname{inorder} v = \operatorname{order} u</tex>, <tex>u \in S(v), u \ne v</tex>
Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{inorder} w = \operatorname{inorder} v = \operatorname{order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inorder} v' = \operatorname{inorder} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое.
}}

==Обработка запроса==
Пусть <tex>x</tex>, <tex>y</tex> {{---}} вершины в исходном дереве <tex>LCA</tex> которых необходимо найти. Если <tex>\operatorname{inlabel} x = \operatorname{inlabel} y</tex>, то они принадлежат одному простому пути, а следовательно ответом на запрос является <tex>x</tex>, если <tex>\operatorname{level} x \le \operatorname{level} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям. Найдем <tex>b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>.

{{Утверждение
|statement= <tex>\operatorname{inlabel} (((x >> (i + 1)) << 1) | 1) << i</tex>, где <tex>i = \log(\operatorname{inlabel} x \oplus \operatorname{inlabel} y)</tex>
|proof= ?
}}

Алгоритм Шибера-Вишкина

2012-06-21T14:52:16Z

109.188.219.181:

''Алгоритм Шибера-Вишкина'' применяется для нахождения наименьшего общего предка двух вершин в дереве.
Он использует <tex>O(n)</tex> времени на подготовку и затем отвечает на каждый запрос за <tex>O(1)</tex>.

==Идея алгоритма==
Основная идея алгоритма следующая.

# Если бы дерево, в котором нужно искать <tex>LCA</tex> было бы цепочкой, можно было бы найти <tex>LCA(u, v)</tex> просто взяв ту вершину, которая находится в дереве выше.
# Если дерево {{---}} полное двоичное дерево высоты <tex>h</tex>, то можно сопоставить каждой вершине битовый вектор длиной <tex>h</tex> (целое число от <tex>0</tex> до <tex>2^h-1</tex>) и с помощью битовых операций над этими векторами найти <tex>LCA(u, v)</tex>

Тогда, представив данное дерево как полное двоичное дерево, в каждой вершине которого находится цепочка, можно
научиться искать <tex>LCA(v, u)</tex> в нем за <tex>O(1)</tex>.

==Подготовка==
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обходится текущая вершина, затем {{---}} поддеревья.
Пусть <tex>\operatorname{order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.

Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем,
что вершина является и своим предком, и своим потомком.

{{Утверждение
|statement=Пусть <tex>u</tex> {{---}} вершина из поддерева <tex>v</tex>. Тогда
<tex>\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{order}</tex>, <tex>\operatorname{order} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{order}v + 1</tex>, то <tex>\operatorname{order} u</tex> {{---}} отрезок <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>.
}}

Покроем дерево путями. А именно, сопоставим каждой вершине <tex>v</tex> число <tex>\operatorname{inlabel} v</tex> такое, что прообраз каждого <tex>\operatorname{inlabel} v</tex> в <tex>T</tex> связен и является простым путем от какой-то вершины вниз до листа.

{{Утверждение
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{inorder} v = \operatorname{order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
Пусть есть вершина <tex>u' \in S(i)</tex> такая, что <tex>\operatorname{order} u' = k'2^b</tex>.
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{inorder} v</tex> выбран неверно.
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>\operatorname{order} u \hdots 2^{max}</tex>.

Рассмотрим два случая.
''Первый случай'' <tex>\operatorname{inorder} v = \operatorname{order} v</tex>
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inorder}</tex> отличаются
от <tex>\operatorname{inorder} v</tex>.

''Второй случай'' <tex>\operatorname{inorder} v = \operatorname{order} u</tex>, <tex>u \in S(v), u \ne v</tex>
Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{inorder} w = \operatorname{inorder} v = \operatorname{order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inorder} v' = \operatorname{inorder} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое.
}}

==Обработка запроса==
Пусть <tex>x</tex>, <tex>y</tex> {{---}} вершины в исходном дереве <tex>LCA</tex> которых необходимо найти. Если <tex>\operatorname{inlabel} x = \operatorname{inlabel} y</tex>, то они принадлежат одному простому пути, а следовательно ответом на запрос является <tex>x</tex>, если <tex>\operatorname{inlabel} x \le \operatorname{inlabel} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям. Найдем <tex>b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>.

{{Утверждение
|statement= <tex>\operatorname{inlabel} (((x >> (i + 1)) << 1) | 1) << i</tex>, где <tex>i = \log(\operatorname{inlabel} x \oplus \operatorname{inlabel} y)</tex>
|proof= ?
}}

Алгоритм Шибера-Вишкина

2012-06-21T14:24:10Z

109.188.219.181:

Алгоритм Шибера-Вишкина

2012-06-21T14:21:11Z

109.188.219.181:

Opi1sumu

2012-06-21T08:53:42Z

109.188.219.181: /* Описание алгоритма */

==Описание задачи==
Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить
в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно одному.
Для каждой работы известно время, до которого её необходимо выполнить. Необходимо успеть выполнить как можно больше работ.

==Описание алгоритма==
Отсортируем работы в порядке невозрастания дедлайнов.

{{Утверждение
|statement=Если в оптимальном расписании можно сделать <tex>k</tex> работ, то можно сделать первые <tex>k</tex> работ.
|proof=Пусть в оптимальном расписании были сделаны работы <tex>i_1, i_2, \ldots, i_k</tex>. Докажем, что существует
оптимальное расписание, в котором сделаны работы <tex>1, 2, \ldots, k</tex>. Пусть работы <tex>i_1, i_2, \ldots, i_k</tex>
тоже отсортированы в порядке неубывания дедлайна. Тогда <tex>d_{i1} \le d_1, d_{i2}\le d_2, \ldots, d_{ik}\le d_{k}</tex>.
Тогда, если заменить во всём расписании работу <tex>i_j</tex> на работу <tex>j</tex>, то она, тем более, будет выполнена.
}}

{{Определение
|definition=Обозначим за ''тайм-слот t'' множество из не более, чем <tex>m</tex> различных чисел {{---}}
номера работ, которые мы хотим выполнить в момент времени <tex>t</tex>.
}}

Введем тайм-слот для каждого момента времени от <tex>0</tex> до <tex>d_n</tex>.
Каждую работу будем пытаться сделать как можно позже. Будем рассматривать работы в порядке невозрастания дедлайнов.
<tex>i</tex>-ю работу попытаемся добавить в тайм-слоты с номерами от <tex>d_i - m + 1</tex> по <tex>d_i</tex>.
После добавления некоторые тайм-слоты могли переполниться (тайм-слот переполнился, если в нём уже находилось
<tex>m</tex> работ, и в него добавили <tex>m+1</tex>-ю).
Для переполнившегося тайм-слота найдём найдем самый правый левее него тайм-слот, который ещё не переполнился и перекинем работу,
которой там еще нет, в него. Так как в нем меньше элементов, то, по принципу Дирихле, это можно сделать.

{{Утверждение
|statement=Следуя этому алгоритму, расписания не существует тогда и только тогда, когда
переполнился нулевой тайм-слот.
|proof=
<tex>\Rightarrow</tex>
Расписания не существует, а значит, никакой алгоритм его не найдет.

<tex>\Leftarrow</tex>
Пусть при добавлении <tex>k+1</tex>-й работы произошло переполнение нулевого тайм-слота.

Рассмотрим алгоритм добавления в тайм-слоты: работа <tex>i</tex> добавляется в тайм-слоты <tex>[d_i - m + 1; d_i]</tex>, после чего из переполнившихся работы перебрасываются в более ранние. Временно разрешим хранить в тайм-слоте сколь угодно много работ: отменим перебрасывание. Посмотрим на то, что получилось. Так как работу нельзя выполнять одновременно на двух станках, то ни одну единицу работы отсрочить нельзя. Будем рассматривать тайм-слоты в порядке уменьшения времени. Если в очередном тайм-слоте <tex>t</tex> в данный момент больше, чем <tex>m</tex> работ, то остаток нужно перекинуть на какие-то более ранние тайм-слоты. Заметим, что выгоднее перекинуть на наиболее поздние тайм-слоты: более ранние тайм-слоты могут понадобиться для перекидываний с тайм-слотов, идущих раньше просматриваемого. .

Также заметим, что алгоритм перекидывания работ таков, что итоговое распределение количеств работ в соответствующих тайм-слотах не зависит от того, в каком порядке обрабатывались переполнившиеся тайм-слоты.

При рассмотрении очередного переполнившегося тайм-слота мы необходимо должны куда-то перекинуть несколько работ из него. Так как перекидывание происходит в тайм-слот с наибольшим допустимым временем, то то, что неоходимо перекинуть что-то из нулевого, влечет то, что не существует расписания, в котором можно успеть выполнить все эти работы
}}

Опираясь на это утверждение, можно найти максимальное количество работ, которое можно выполнить. Обозначим его за <tex>k</tex>.

Сведем задачу построения распинания по построенным тайм-слотам к задаче о покрытии двудольного графа минимальным
количеством паросочетаний.

Построим двудольный граф. В левой доле вершинам будут соответствовать работы, в правой {{---}} времена. Соответственно, в левой доле будет <tex>n</tex> вершин, в правой {{---}} <tex>d_{max}</tex>. Ребро между работой <tex>i</tex> и временем <tex>t</tex> будет, если работа <tex>i</tex> есть в тайм-слоте <tex>t</tex>.

Рассмотрим какое-то паросочетание <tex>M</tex> в этом графе. Оно соответствует корректному расписанию работ на одной машине: ни одна работа не выполняется два раза, и ни в один момент времени не выполняется более одной работы.

Тогда, если мы сможем построить множество мощности <tex>m</tex> такое, что каждое ребро находится хотя бы в одном из паросочетаний, то оно будет соответствовать тому, что каждая работа обработана на каждом станке, а значит, составлено корректное расписание для этих <tex>k</tex> работ.

Достроим граф до регулярного степени <tex>m</tex>. Достраивать будем следующим образом. Каждая вершина в левой доле имеет степень <tex>m</tex>, так как каждая работа представлена в <tex>m</tex> тайм-слотах. В правой доле степень каждой вершины не больше <tex>m</tex>, так как в тайм-слоте не может быть больше, чем <tex>m</tex> работ. Значит, в левой доле не больше вершин, чем в правой.
Добавим в левую долю фиктивных вершин, чтобы количества вершин в левой и правой долях сравнялись. После чего просто будем добавлять ребра между вершинами, степень которых еще меньше <tex>m</tex>. Для покрытия этого графа паросочетаниями воспользуемся тем фактом, что регулярный двудольный граф степени <tex>d</tex> можно покрыть <tex>d</tex> паросочетаниями.

При помощи построения паросочетаний было построено расписание для тех <tex>k</tex> работ, которые можно успеть сделать. Так как остальные работы уже нельзя успеть, расписание для них можно составить произвольное. Например, выполнять их по очереди после выполнения первых <tex>k</tex> работ.

==Оценка сложности алгоритма==
Рассмотрим добавление очередной работы в тайм-слоты. За <tex>O(t)</tex> найдём переполнившийся тайм-слот и за <tex>O(m)</tex> перекинем из него элемент. Так как <tex>t=O(nm)</tex>, итоговая сложность этой части {{---}} <tex>O(n^2m)</tex>.

Достроение графа до регулярного делается за <tex>O(E)</tex>, где <tex>E</tex> {{---}} количество ребер в нем. Количество ребер в регулярном двудольном графе <tex>E = Vd</tex>, где <tex>V</tex> {{---}} количество вершин в одной из долей, а <tex>d</tex> {{---}} степень. Количество вершин в правой доле {{---}} <tex>O(t) = O(nm)</tex>. Значит, граф будет построен за <tex>O(nm^2)</tex>, так как степень каждой вершины {{---}} <tex>m</tex>.

Сложность последней фазы зависит от того, каким алгоритмом граф разбивается на паросочетания. Использовав, например, алгоритм Куна, можно добиться сложности <tex>O(m \cdot M) = O(m \cdot n^3m^3)</tex>. Итоговая сложность алгоритма {{---}} <tex>O(n^3m^4)</tex>.