Случайные графы — различия между версиями
м (→Теоремы о связи вероятности и матожидания) |
|||
Строка 92: | Строка 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>. |
}} | }} | ||
Версия 21:12, 2 декабря 2019
Определение:
Биномиальная модель случайного графа (англ. binomial random graph model) вероятностное пространство . , , где — число ребер в графе.
— модель, в которой каждое ребро входит в случайный граф независимо от остальных ребер с вероятностью . —
Определение:
Равномерная модель случайного графа (англ. uniform random graph model)
— модель, в которой все графы с ребрами равновероятны. — вероятностное пространство. , .
Определение: |
Свойство | ассимптотически почти наверное истинно, если
Определение: |
Свойство | ассимптотически почти наверное ложно, если
Содержание
Существование треугольников в случайном графе
Теорема: |
Если , то а.п.н не содержит треугольников. |
Доказательство: |
Пусть — число треугольников в графе, — индикаторная случайная величина, равная , если вершины , и образуют треугольник.Воспользуемся неравенством Маркова: , при . |
Теорема: |
Если , то а.п.н содержит треугольник. |
Доказательство: |
Пусть — число треугольников в графе, — индикаторная случайная величина, равная , если вершины , и образуют треугольник.Воспользуемся неравенством Чебышева: . Найдем :
, при |
Связность графа
Лемма: |
Если , , . Тогда . |
Доказательство: |
Пусть — индикаторная величина, равная , если связен, и , если содержит компонент связности.— число компонент связности размера . , если — компонента связности.
.
Последняя сумма симметрична (слагаемые при и равны), кроме того слагаемое при — наибольшее (для доказательства достаточно рассмотреть отношения слагаемых при и ).Оценим сверху первое слагаемое :
, поэтому . , при |
Лемма: |
Если , , . Тогда . |
Теорема: |
, тогда при граф а.п.н связен, при граф а.п.н не связен. |
Теоремы о связи вероятности и матожидания
Теорема: |
Пусть — число объектов в графе . — свойство. Тогда, если , при , то а.п.н ложно. |
Доказательство: |
Воспользуемся неравенством Маркова: , при . |
Теорема: |
Пусть — число объектов в графе . — свойство. Тогда, если , при , и то а.п.н истинно. |
Доказательство: |
Воспользуемся неравенством Чебышева: , при . |
Графы имеющие диаметр два
Теорема: |
Пусть рассматривается свойство графа иметь диаметр два. Тогда — порог. |
Доказательство: |
Назовем вершины и плохой парой, если . — индикаторная величина, равная , если и плохая пара.Сначала докажем, что при , граф а.п.н не имеет диаметр два. Для этого оценим матожидание .При первой теореме граф а.п.н. не имеет диаметр два. последнее выражение стремится к , поРассмотрим :
Рассмотрим сумму :Если , , и различны, то .
В итоге: , а значит граф а.п.н имеет диаметр два при . |