244
правки
Изменения
Нет описания правки
# Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.
# Докажите, что если связный граф $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).
# Найдите математическое ожидание и дисперсию степени вершины в биномиальной модели $G(n, p)$.
# Равномерная модель $G(n, m)$ - каждый граф с $n$ вершинами и $m$ ребрами равновероятен. Найдите математическое ожидание степени вершины в равномерной модели $G(n, m)$.
# Найдите дисперсию степени вершины в равномерной модели $G(n, m)$.
# Найдите вероятность, что граф в равномерной модели $G(n, m)$ является деревом ($m = n - 1$).
# Найдите вероятность, что граф в биномиальной модели $G(n, p)$ является деревом.
# Найдите вероятность, что граф в равномерной модели $G(n, m)$ является гамильтоновым циклом ($m = n$).
# Найдите вероятность, что граф в биномиальной модели $G(n, p)$ является гамильтоновым циклом.
# Оцените центральный биномиальный коэффициент ${2n \choose n}$ снизу величиной порядка $c \frac {4^n}{\sqrt{n}}$, используя формулу Стирлинга.
# Рассмотрим число ребер $m$, такое что $m(n) \to \infty$ и ${n \choose 2} - m(n) \to \infty$, а также $p(n) = \frac {m(n)}{n \choose 2}$. Докажите, что вероятность того, что $G(n, p)$ имеет ровно $m$ ребер есть $\Omega(m^{-0.5})$.
# Рассмотрим свойство $A$, а и такие же $m(n)$ и $p(n)$, как в предыдущей задаче. Докажите, что $P(G(n, m) \in A) \le C \sqrt{m} P(G(n, p) \in A)$.
# Рассмотрим следующую модель генерации случайного графа. Сначала проведем каждое ребро с вероятностью $\frac 12$. Затем, для каждой пары вершин, между которыми не было проведено ребро на первом шаге, проведем ребро с вероятностью $\frac 13$. Предложите более простое описание этой модели в терминах моделей Эрдёша-Реньи.
# Свойство случайного графа называется, монотонным, если оно сохраняется при добавлении ребра. Рассмотрим монотонное свойство $A$ при фиксированном размере графа $n$. Докажите, что $P(G(n, p) \in A)$ возрастает при возрастании $p$.
# Придумайте такое свойство, что вероятность, что $G(n, \frac 12)$ обладает этим свойством, стремится к $\frac 14$.
# Придумайте такое свойство, что вероятность, что $G(n, \frac 12)$ обладает этим свойством, стремится к $\frac 13$.
# Пусть для некоторого свойства $A$ существует две функции $p_1(n)$ и $p_2(n)$, что для графа $G(n, p_1(n))$ свойство $A$ а.п.н. не выполняется, а для $G(n, p_2(n))$ свойство $A$ а.п.н. выполняется. Докажите, что существует функция $\tilde p(n)$, что для случайного графа $G(n, \tilde p(n))$ свойство $A$ выполняется с вероятностью, стремящейся к $\frac 12$.
# Подберите $p(n)$ и приведите последовательности случайных величин $X_n$ для $G(n, p)$, что $EX_n \to \infty$, но $\mathcal{P}(X_n = 0) \nrightarrow 0$.
# Докажите, что $G(n, \frac {2\ln n}{n})$ а.п.н. не содержит вершин степени 0.
