2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Случайные графы.
Сообщение10.11.2015, 13:36 
Если в графе $G=(V,E)$ с $n$ вершинами минимальная степень вершины равна $\delta$, то

1) Для любого $p\in (0;1)$ существует такое множество вершин $A\subset V$, что в объединении $A$ и множества вершин, не соединенных с ни с какой вершиной из $A$

имеется не более $np+n(1-p)^{\delta+1}$ вершин.

2) Существует такое множество вершин $D \subset V$ , что любая вершина из $V \D$ соединена ребром с некоторой вершиной из $D$, при этом

$|D|\le n\cdot \dfrac{1+\ln(\delta +1)}{\delta+1}$

Рассмотрим первый пункт.

Я так понимаю, что любое возможное ребро из множества $A\subset V$ появляется независимо с вероятностью $0 < p < 1$.
То есть $p=p(v\in A)$ для каждой вершины $v\in A$

Вероятность того, что из $m$ ребер графа ровно $m$ окажутся в множестве $A$ равна $p^m(1-p)^{n-m}$

Пока что только такие идеи есть, больше не знаю за что зацепиться и как использовать минимальную степень вершины графа $\delta$

 
 
 
 Re: Случайные графы.
Сообщение10.11.2015, 15:53 
Поправка опечатки*

Вероятность того, что из $n$ ребер графа ровно $m$ окажутся в множестве $A$ равна $p^m(1-p)^{n-m}$

-- 10.11.2015, 15:54 --

Или же должно быть $C_n^mp^m(1-p)^{n-m}$?

 
 
 
 Re: Случайные графы.
Сообщение10.11.2015, 23:41 
Видимо я что-то совсем глупое написал или слишком узкая область на стыке теории графов и теории вероятностей?

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group