89
правок
Изменения
Новая страница: «{{Определение |neat = 1 |definition= '''Биномиальная модель случайного графа''' (англ. ''binomial random graph mo…»
{{Определение
|neat = 1
|definition= '''Биномиальная модель случайного графа''' (англ. ''binomial random graph model'') <tex>G(n, p)</tex> {{---}} модель, в которой каждое ребро входит в случайный граф независимо от остальных ребер с вероятностью <tex>p</tex>. <tex>G(n, p) = (\Omega_n, F_n, P_{n, p})</tex> {{---}} вероятностное пространство. <tex>|\Omega_n| = 2^{C^2_n}</tex>, <tex>P_{n, p}(G) = p^m(1 - p)^{C^2_n - m}</tex>, где <tex>m</tex> {{---}} число ребер в графе.
}}
{{Определение
|neat = 1
|definition= '''Равномерная модель случайного графа''' (англ. ''uniform random graph model'') <tex>G(n, m)</tex> {{---}} модель, в которой все графы с <tex>m</tex> ребрами равновероятны. <tex>G(n, m) = (\Omega_n, F_n, P_{n, m})</tex> {{---}} вероятностное пространство. <tex>|\Omega_n| = m</tex>, <tex>P_{n, m}(G) = \dfrac{1}{C^m_n}</tex>.
}}
{{Определение
|definition= Свойство <tex>A</tex> ассимптотически почти наверное истинно, если <tex>\lim\limits_{n \rightarrow \infty} p(n) = 1</tex>
}}
{{Определение
|definition= Свойство <tex>A</tex> ассимптотически почти наверное ложно, если <tex>\lim\limits_{n \rightarrow \infty} p(n) = 0</tex>
}}
== Существование треугольников в случайном графе ==
{{Теорема
|statement=Если <tex>p(n) = o(\dfrac{1}{n})</tex>, то <tex>G(n, p)</tex> а.п.н не содержит треугольников.
|proof=
Пусть <tex>T</tex> {{---}} число треугольников в графе, <tex>T_{i,j,k}</tex> {{---}} индикаторная случайная величина, равная <tex>1</tex>, если вершины <tex>i</tex>, <tex>j</tex> и <tex>k</tex> образуют треугольник.
Воспользуемся [[Неравенство Маркова| неравенством Маркова]]:
<tex>P(T > 0) = P(T \geqslant 1) \leqslant ET = \sum\limits_{i, j, k}T_{i, j, k}p^3 = C^3_np^3 \sim \dfrac{n^3}{6}p^3 \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
{{Теорема
|statement=Если <tex>p(n) = \omega(\dfrac{1}{n})</tex>, то <tex>G(n, p)</tex> а.п.н содержит треугольник.
|proof=
Пусть <tex>T</tex> {{---}} число треугольников в графе, <tex>T_{i,j,k}</tex> {{---}} индикаторная случайная величина, равная <tex>1</tex>, если вершины <tex>i</tex>, <tex>j</tex> и <tex>k</tex> образуют треугольник.
Воспользуемся [[Неравенство Маркова#thCheb| неравенством Чебышева]]:
<tex>P(T = 0) = P(T \leqslant 0) = P(ET - T \geqslant ET) \leqslant P(|ET - T| \geqslant ET) \leqslant \dfrac{DT}{(ET)^2}</tex>.
Найдем <tex>ET^2</tex>:
<tex>ET^2 = E(\sum\limits_{i, j, k}T_{i, j, k})^2= E(\sum\limits_{i, j, k}(T_{i, j, k})^2) + E(\sum\limits_{i, j, k, a, b, c}T_{i, j, k}T_{a, b, c}) =</tex>
<tex>= ET + (C^3_nC^3_{n - 3} + C^3_nC^2_{n - 3})p^6 + 3C^3_n(n - 3)p^5 \sim \dfrac{n^3p^3}{6} + (\dfrac{n^6}{36} + \dfrac{n^5}{4})p^6 + \dfrac{n^4}{2}p^5 \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36} + \dfrac{n^4p^5}{2} \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36}</tex>
<tex>DT = ET^2 - (ET)^2 \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36} - \dfrac{n^6p^6}{36} = \dfrac{n^3p^3}{6}</tex>
<tex>P(T = 0) \leqslant \dfrac{\dfrac{n^3p^3}{6}}{\dfrac{n^6p^6}{36}} = \dfrac{6}{p^3n^3} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>
}}
|neat = 1
|definition= '''Биномиальная модель случайного графа''' (англ. ''binomial random graph model'') <tex>G(n, p)</tex> {{---}} модель, в которой каждое ребро входит в случайный граф независимо от остальных ребер с вероятностью <tex>p</tex>. <tex>G(n, p) = (\Omega_n, F_n, P_{n, p})</tex> {{---}} вероятностное пространство. <tex>|\Omega_n| = 2^{C^2_n}</tex>, <tex>P_{n, p}(G) = p^m(1 - p)^{C^2_n - m}</tex>, где <tex>m</tex> {{---}} число ребер в графе.
}}
{{Определение
|neat = 1
|definition= '''Равномерная модель случайного графа''' (англ. ''uniform random graph model'') <tex>G(n, m)</tex> {{---}} модель, в которой все графы с <tex>m</tex> ребрами равновероятны. <tex>G(n, m) = (\Omega_n, F_n, P_{n, m})</tex> {{---}} вероятностное пространство. <tex>|\Omega_n| = m</tex>, <tex>P_{n, m}(G) = \dfrac{1}{C^m_n}</tex>.
}}
{{Определение
|definition= Свойство <tex>A</tex> ассимптотически почти наверное истинно, если <tex>\lim\limits_{n \rightarrow \infty} p(n) = 1</tex>
}}
{{Определение
|definition= Свойство <tex>A</tex> ассимптотически почти наверное ложно, если <tex>\lim\limits_{n \rightarrow \infty} p(n) = 0</tex>
}}
== Существование треугольников в случайном графе ==
{{Теорема
|statement=Если <tex>p(n) = o(\dfrac{1}{n})</tex>, то <tex>G(n, p)</tex> а.п.н не содержит треугольников.
|proof=
Пусть <tex>T</tex> {{---}} число треугольников в графе, <tex>T_{i,j,k}</tex> {{---}} индикаторная случайная величина, равная <tex>1</tex>, если вершины <tex>i</tex>, <tex>j</tex> и <tex>k</tex> образуют треугольник.
Воспользуемся [[Неравенство Маркова| неравенством Маркова]]:
<tex>P(T > 0) = P(T \geqslant 1) \leqslant ET = \sum\limits_{i, j, k}T_{i, j, k}p^3 = C^3_np^3 \sim \dfrac{n^3}{6}p^3 \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
{{Теорема
|statement=Если <tex>p(n) = \omega(\dfrac{1}{n})</tex>, то <tex>G(n, p)</tex> а.п.н содержит треугольник.
|proof=
Пусть <tex>T</tex> {{---}} число треугольников в графе, <tex>T_{i,j,k}</tex> {{---}} индикаторная случайная величина, равная <tex>1</tex>, если вершины <tex>i</tex>, <tex>j</tex> и <tex>k</tex> образуют треугольник.
Воспользуемся [[Неравенство Маркова#thCheb| неравенством Чебышева]]:
<tex>P(T = 0) = P(T \leqslant 0) = P(ET - T \geqslant ET) \leqslant P(|ET - T| \geqslant ET) \leqslant \dfrac{DT}{(ET)^2}</tex>.
Найдем <tex>ET^2</tex>:
<tex>ET^2 = E(\sum\limits_{i, j, k}T_{i, j, k})^2= E(\sum\limits_{i, j, k}(T_{i, j, k})^2) + E(\sum\limits_{i, j, k, a, b, c}T_{i, j, k}T_{a, b, c}) =</tex>
<tex>= ET + (C^3_nC^3_{n - 3} + C^3_nC^2_{n - 3})p^6 + 3C^3_n(n - 3)p^5 \sim \dfrac{n^3p^3}{6} + (\dfrac{n^6}{36} + \dfrac{n^5}{4})p^6 + \dfrac{n^4}{2}p^5 \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36} + \dfrac{n^4p^5}{2} \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36}</tex>
<tex>DT = ET^2 - (ET)^2 \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36} - \dfrac{n^6p^6}{36} = \dfrac{n^3p^3}{6}</tex>
<tex>P(T = 0) \leqslant \dfrac{\dfrac{n^3p^3}{6}}{\dfrac{n^6p^6}{36}} = \dfrac{6}{p^3n^3} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>
}}
