Случайные графы — различия между версиями
м |
|||
(не показаны 4 промежуточные версии этого же участника) | |||
Строка 45: | Строка 45: | ||
<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> | <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> | ||
+ | }} | ||
+ | |||
+ | == Связность графа == | ||
+ | |||
+ | {{Лемма | ||
+ | |id=lemma1 | ||
+ | |statement=Если <tex>c \geqslant 3</tex>, <tex>n \geqslant 100</tex>, <tex>p = \dfrac{c\ln n}{n}</tex>. Тогда <tex>P(G - связен) \rightarrow 1</tex>. | ||
+ | |proof= | ||
+ | Пусть <tex>X</tex> {{---}} индикаторная величина, равная <tex>0</tex>, если <tex>G</tex> связен, и <tex>k</tex>, если <tex>G</tex> содержит <tex>k</tex> компонент связности. | ||
+ | |||
+ | <tex>X_i</tex> {{---}} число компонент связности размера <tex>i</tex>. | ||
+ | |||
+ | <tex>X_{a_1,a_2, \dots , a_i} = 1</tex>, если <tex>a_1,a_2, \dots , a_i</tex> {{---}} компонента связности. | ||
+ | |||
+ | <tex>X_i = \sum\limits_{a_1,a_2, \dots , a_i} X_{a_1,a_2, \dots , a_i}</tex> | ||
+ | |||
+ | <tex>EX_i = \sum\limits_{a_1,a_2, \dots , a_i} EX_{a_1,a_2, \dots , a_i} = C_n^iEX_{1, 2, \dots, i} = C_n^i P(1, 2, \dots, i - комп.связности) \leqslant C_n^i (1 - p)^{i(n - i)}</tex>. | ||
+ | |||
+ | <tex>EX \sum\limits_{i = 1}^{n - 1} EX_i \leqslant \sum\limits_{i = 1}^{n - 1} C_n^i(1 - p)^{i(n - i)}</tex> | ||
+ | |||
+ | Последняя сумма симметрична (слагаемые при <tex>i = k</tex> и <tex>i = n - k</tex> равны), кроме того слагаемое при <tex>i = 1</tex> {{---}} наибольшее (для доказательства достаточно рассмотреть отношения слагаемых при <tex>i \leqslant \dfrac{n}{8}</tex> и <tex>\dfrac{n}{8} < i \leqslant \dfrac{n}{2}</tex>). | ||
+ | |||
+ | Оценим сверху первое слагаемое <tex>n(1 - p)^{n - 1}</tex>: | ||
+ | |||
+ | <tex>n(1 - p)^{n - 1} \leqslant ne^{-p(n - 1)} \leqslant ne^{\frac{-3 (n - 1) \ln n}{n}}</tex> | ||
+ | |||
+ | <tex>n \geqslant 100</tex>, поэтому <tex>\dfrac{n - 1}{n} > 0.9</tex>. | ||
+ | |||
+ | <tex>ne^{\frac{-3 (n - 1) \ln n}{n}} < e^{-2.7\ln n} = \dfrac{1}{n^{2.7}}</tex> | ||
+ | |||
+ | <tex>\sum\limits_{i = 1}^{n - 1} C_n^i(1 - p)^{i(n - i)} \leqslant \sum\limits_{i = 1}^{n - 1}\dfrac{1}{n^{2.7}} < \dfrac{n}{n^{2.7}} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex> | ||
+ | |||
+ | |||
+ | }} | ||
+ | |||
+ | {{Лемма | ||
+ | |id=lemma2 | ||
+ | |statement=Если <tex>c \geqslant 3</tex>, <tex>n \geqslant 100</tex>, <tex>p = \dfrac{c\ln n}{n}</tex>. Тогда <tex>P(G - связен) > 1 - \dfrac{1}{n}</tex>. | ||
+ | }} | ||
+ | |||
+ | {{Теорема | ||
+ | |statement=<tex>p = \dfrac{c\ln n}{n}</tex>, тогда при <tex>c < 1</tex> граф а.п.н связен, при <tex>c > 1</tex> граф а.п.н не связен. | ||
}} | }} | ||
Строка 50: | Строка 92: | ||
{{Теорема | {{Теорема | ||
|id=th1 | |id=th1 | ||
− | |statement= Пусть <tex> | + | |statement= Пусть <tex>N_z</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | N_z(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>N_z \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>, то <tex>A</tex> а.п.н ложно. |
|proof= | |proof= | ||
Воспользуемся [[Неравенство Маркова | неравенством Маркова]]: | Воспользуемся [[Неравенство Маркова | неравенством Маркова]]: | ||
− | <tex>P( | + | <tex>P(N_z > 0) = P(N_z \geqslant 1) \leqslant EZ \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>. |
}} | }} | ||
{{Теорема | {{Теорема | ||
|id=th2 | |id=th2 | ||
− | |statement= Пусть <tex> | + | |statement= Пусть <tex>N_z</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | N_z(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>EN_z \rightarrow \infty</tex>, при <tex>n \rightarrow \infty</tex>, и <tex>EZ^2 = (EZ)^2(1 + o(1))</tex> то <tex>A</tex> а.п.н истинно. |
|proof= | |proof= | ||
Воспользуемся [[Неравенство Маркова#thCheb | неравенством Чебышева]]: | Воспользуемся [[Неравенство Маркова#thCheb | неравенством Чебышева]]: | ||
− | <tex>P( | + | <tex>P(N_z = 0) = P(N_z \leqslant 0) = P(EN_z - N_z \geqslant EN_z) \leqslant P(|EN_z - N_z| \geqslant EN_z) \leqslant \dfrac{DN_z}{(EN_z)^2} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>. |
}} | }} | ||
+ | |||
+ | == Графы имеющие диаметр два == | ||
+ | {{Теорема | ||
+ | |statement=Пусть рассматривается свойство графа иметь диаметр два. Тогда <tex>p = \sqrt{2} \sqrt{\dfrac{\ln n}{n}}</tex> {{---}} порог. | ||
+ | |proof= | ||
+ | Назовем вершины <tex>u</tex> и <tex>v</tex> плохой парой, если <tex>dist(u, v) > 2</tex>. <tex>B_{i, j}</tex> {{---}} индикаторная величина, равная <tex>1</tex>, если <tex>i</tex> и <tex>j</tex> плохая пара. | ||
+ | <tex>N_z = \sum\limits_{i, j} B_{i,j}</tex> | ||
+ | <tex>P(B_{i, j}) = (1 - p)(1 - p^2)^{n - 2}</tex> | ||
+ | |||
+ | Сначала докажем, что при <tex>c > sqrt{2}</tex>, граф а.п.н не имеет диаметр два. Для этого оценим матожидание <tex>N_z</tex>. | ||
+ | <tex>EN_z = C_n^2(1 - p)(1 - p^2)^{n - 2} \approx \dfrac{n^2}{2}(1 - c\sqrt{\dfrac{\ln n}{n}})(1 - \dfrac{c^2\ln n}{n})^{n - 2} \leqslant \dfrac{n^2}{2}e^{-c^2\ln n} = \dfrac{n^{2 - c^2}}{2}</tex> | ||
+ | |||
+ | При <tex>c > \sqrt{2}</tex> последнее выражение стремится к <tex>0</tex>, по [[#th1 | первой теореме ]] граф а.п.н. не имеет диаметр два. | ||
+ | |||
+ | Рассмотрим <tex>c < \sqrt{2}</tex>: | ||
+ | |||
+ | <tex>EN_z^2 = E(\sum B_{i, j})^2 = E\sum B_{i,j}^2 + E\sum B_{i,j}B_{k,l} = EN_z + \sum EB_{i,j}B_{k,l}</tex> | ||
+ | |||
+ | Рассмотрим сумму <tex>\sum EB_{i,j}B_{k,l}</tex>: | ||
+ | |||
+ | Если <tex>i</tex>, <tex>j</tex>, <tex>k</tex> и <tex>k</tex> различны, то <tex>EB_{i,j}B_{k,l} \leqslant (1 - p^2)^{2(n - 4)} \leqslant n^{-2c^2}(1 + o(1))</tex>. | ||
+ | |||
+ | <tex>\sum EB_{i,j}B_{k,l} \leqslant n^{4 - 2c^2}(1 + o(1))</tex> | ||
+ | |||
+ | <tex>EB_{i,j}B_{i,l} = (1 - p + p(1 - p)^2)^{n - 3} \approx (1 - 2p^2)^{n - 3} = (1 - 2c^2\dfrac{\ln n}{n})^{n - 3} \approx e^{-2c^2 \ln n} = n^{-2c^2}</tex> | ||
+ | |||
+ | <tex>\sum EB_{i,j}B_{i,l} \leqslant n^{3 - 2c}</tex> | ||
+ | |||
+ | В итоге: <tex>EN_z^2 \leqslant n^{2 - c^2} + n^{4 - 2c^2} + n^{3 - 2c^2}. Из этого следует, что <tex>EN_z \leqslant (EN_z)^2(1 + o(1))</tex>, а значит граф а.п.н имеет диаметр два при <tex>c > \sqrt{2}</tex>. | ||
+ | }} | ||
+ | |||
== См. также == | == См. также == | ||
Строка 70: | Строка 143: | ||
* [[Дисперсия случайной величины]] | * [[Дисперсия случайной величины]] | ||
* [[Математическое ожидание случайной величины]] | * [[Математическое ожидание случайной величины]] | ||
+ | |||
+ | == Источники информации == | ||
+ | * [https://www.coursera.org/learn/sluchajnye-graphy/ Coursera {{---}} Онлайн-курс] | ||
+ | * [https://en.wikipedia.org/wiki/Chernoff_bound Wikipedia {{---}} Random graphs] | ||
+ | * Avrim Blum, John Hopcroft, and Ravindran Kannan. «Foundations of Data Science» {{---}} «Cambridge University Press», 2013 г. {{---}} 245-260 стр. {{---}} ISBN 978-1108485067 | ||
+ | |||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]] |
Версия 21:19, 2 декабря 2019
Определение:
Биномиальная модель случайного графа (англ. binomial random graph model) вероятностное пространство . , , где — число ребер в графе.
— модель, в которой каждое ребро входит в случайный граф независимо от остальных ребер с вероятностью . —
Определение:
Равномерная модель случайного графа (англ. uniform random graph model)
— модель, в которой все графы с ребрами равновероятны. — вероятностное пространство. , .
Определение: |
Свойство | ассимптотически почти наверное истинно, если
Определение: |
Свойство | ассимптотически почти наверное ложно, если
Содержание
Существование треугольников в случайном графе
Теорема: |
Если , то а.п.н не содержит треугольников. |
Доказательство: |
Пусть — число треугольников в графе, — индикаторная случайная величина, равная , если вершины , и образуют треугольник.Воспользуемся неравенством Маркова: , при . |
Теорема: |
Если , то а.п.н содержит треугольник. |
Доказательство: |
Пусть — число треугольников в графе, — индикаторная случайная величина, равная , если вершины , и образуют треугольник.Воспользуемся неравенством Чебышева: . Найдем :
, при |
Связность графа
Лемма: |
Если , , . Тогда . |
Доказательство: |
Пусть — индикаторная величина, равная , если связен, и , если содержит компонент связности.— число компонент связности размера . , если — компонента связности.
.
Последняя сумма симметрична (слагаемые при и равны), кроме того слагаемое при — наибольшее (для доказательства достаточно рассмотреть отношения слагаемых при и ).Оценим сверху первое слагаемое :
, поэтому . , при |
Лемма: |
Если , , . Тогда . |
Теорема: |
, тогда при граф а.п.н связен, при граф а.п.н не связен. |
Теоремы о связи вероятности и матожидания
Теорема: |
Пусть — число объектов в графе . — свойство. Тогда, если , при , то а.п.н ложно. |
Доказательство: |
Воспользуемся неравенством Маркова: , при . |
Теорема: |
Пусть — число объектов в графе . — свойство. Тогда, если , при , и то а.п.н истинно. |
Доказательство: |
Воспользуемся неравенством Чебышева: , при . |
Графы имеющие диаметр два
Теорема: |
Пусть рассматривается свойство графа иметь диаметр два. Тогда — порог. |
Доказательство: |
Назовем вершины и плохой парой, если . — индикаторная величина, равная , если и плохая пара.Сначала докажем, что при , граф а.п.н не имеет диаметр два. Для этого оценим матожидание .При первой теореме граф а.п.н. не имеет диаметр два. последнее выражение стремится к , поРассмотрим :
Рассмотрим сумму :Если , , и различны, то .
В итоге: , а значит граф а.п.н имеет диаметр два при . |
См. также
- Дискретная случайная величина
- Дисперсия случайной величины
- Математическое ожидание случайной величины
Источники информации
- Coursera — Онлайн-курс
- Wikipedia — Random graphs
- Avrim Blum, John Hopcroft, and Ravindran Kannan. «Foundations of Data Science» — «Cambridge University Press», 2013 г. — 245-260 стр. — ISBN 978-1108485067