210
правок
Изменения
Нет описания правки
# Докажите, что $\sum\limits_{u}\lceil\log(1+|A(u)|)\rceil = O(n + m)$.
# Готовимся к алгоритму линейной верификации MST. Введем операцию на множествах целых чисел: $A \downarrow B = \{b \in B | \exists a \in A : a < b \mbox{ and there is no } b′ \in B \mbox{ with } a < b′ < b\}$. Докажите, что $A\downarrow B \subset B$, $|A \downarrow B| \le |A|$, $(A\cup B)\downarrow C = (A \downarrow C) \cup (B \downarrow C)$, $A \downarrow (B \cup C) \subset (A \downarrow B) \cup (A \downarrow C)$.
# Докажите, что если $A \downarrow B = \varnothing$, то $A \downarrow C = A \downarrow (C \setminus B)$.
# Докажите, что если $A \downarrow B \subset C \subset B$, то $A \downarrow B = A \downarrow C$.
# Докажите, что если $\sup(B \cap C) < \inf(B \setminus C)$, то $A \downarrow (B \cap C) = (A \downarrow B) \cap C$ (будем считать, что $\sup\varnothing = -\infty$, $\inf\varnothing = +\infty$).
# Докажите, что если $A \subset B$, то $A \downarrow C = A \downarrow (B \downarrow C)$.
