Подпишитесь на наши новости
Вернуться к началу с статьи up
 

ВЕРОЯ́ТНОСТНАЯ КОМБИНАТО́РИКА

  • рубрика

    Рубрика: Математика

  • родственные статьи
  • image description

    В книжной версии

    Том 5. Москва, 2006, стр. 176-177

  • image description

    Скопировать библиографическую ссылку:




Авторы: В. Ф. Колчин, В. Н. Сачков

ВЕРОЯ́ТНОСТНАЯ КОМБИНАТО́РИКА, раз­дел дис­крет­ной ма­те­ма­ти­ки, в ко­то­ром ме­то­ды тео­рии ве­ро­ят­но­стей при­ме­ня­ют­ся для изу­че­ния ком­би­на­тор­ных объ­ек­тов. В В. к. рас­смат­ри­ва­ют­ся так­же пе­ре­чис­ли­тель­ные за­да­чи ком­би­на­то­ри­ки и во­про­сы су­ще­ст­во­ва­ния ком­би­на­тор­ных объ­ек­тов с за­дан­ны­ми ха­рак­те­ри­сти­ка­ми.

При ис­поль­зо­ва­нии ве­ро­ят­но­ст­ных ме­то­дов для ре­ше­ния пе­ре­чис­ли­тель­ных за­дач ком­би­на­то­ри­ки на ко­неч­ном мно­же­ст­ве ком­би­на­тор­ных объ­ек­тов за­да­ёт­ся ве­ро­ят­но­ст­ное рас­пре­де­ле­ние и ис­сле­ду­ют­ся рас­пре­де­ле­ния ха­рак­те­ри­стик слу­чай­но­го ком­би­на­тор­но­го объ­ек­та из это­го мно­же­ст­ва. Ес­ли за­дан­ное рас­пре­де­ле­ние яв­ля­ет­ся рав­но­мер­ным, то ве­ро­ят­ность то­го, что не­ко­то­рая ха­рак­те­ри­сти­ка слу­чай­но­го объ­ек­та при­ня­ла ка­кое-то зна­че­ние, есть от­но­ше­ние чис­ла объ­ек­тов, об­ла­даю­щих этим зна­че­ни­ем ха­рак­те­ри­сти­ки, к об­ще­му чис­лу объ­ек­тов в мно­же­ст­ве, так что, ес­ли об­щее чис­ло объ­ек­тов из­вест­но, за­да­ча на­хо­ж­де­ния ве­ро­ят­но­сти и пе­ре­чис­ли­тель­ная за­да­ча на­хо­ж­де­ния чис­ла объ­ек­тов с за­дан­ным зна­че­ни­ем ха­рак­те­ри­сти­ки эк­ви­ва­лент­ны.

Пер­вые ша­ги В. к. свя­за­ны с раз­ви­ти­ем в сер. 17 в. эле­мен­тар­ной тео­рии ве­ро­ят­но­стей, ко­гда ком­би­на­тор­ные ме­то­ды ис­поль­зо­ва­лись для под­счё­та разл. ве­ро­ят­но­стей в азарт­ных иг­рах. Пер­вые ре­зуль­та­ты ис­сле­до­ва­ний в В. к. с ис­поль­зо­ва­ни­ем совр. ме­то­дов тео­рии ве­ро­ят­но­стей поя­ви­лись в ра­бо­тах В. Л. Гон­ча­ро­ва 1942–44, в ко­то­рых по­лу­че­ны осн. ре­зуль­та­ты о пре­дель­ном по­ве­де­нии слу­чай­ных ве­ли­чин, свя­зан­ных с цик­ло­вой струк­ту­рой слу­чай­ных под­ста­но­вок при воз­рас­та­нии их сте­пе­ней. Слу­чай­ная под­ста­нов­ка сте­пе­ни $n$ – это под­ста­нов­ка, вы­би­рае­мая с рав­ны­ми ве­ро­ят­но­стя­ми из мно­же­ст­ва всех под­ста­но­вок сте­пе­ни $n$. С ис­поль­зо­ва­ни­ем хо­ро­шо раз­ви­тых в тео­рии ве­ро­ят­но­стей ме­то­дов до­ка­за­тель­ст­ва пре­дель­ных тео­рем (ме­то­да про­из­во­дя­щих функ­ций, ме­то­да ха­рак­те­ри­сти­че­ских функ­ций, а так­же ме­то­да мо­мен­тов) Гон­ча­ро­вым бы­ло до­ка­за­но, что чис­ло цик­лов дли­ны $r$ в слу­чай­ной под­ста­нов­ке сте­пе­ни $n$ име­ет в пре­де­ле при $n→∞$ рас­пре­де­ле­ние Пу­ас­со­на с па­ра­мет­ром $1/r$, рас­пре­де­ление об­ще­го чис­ла цик­лов сбли­жа­ет­ся с нор­маль­ным рас­пре­де­ле­ни­ем с па­ра­мет­ра­ми ($\ln n, \ln n $), най­де­но пре­дель­ное рас­пре­де­ле­ние макс. дли­ны цик­ла слу­чай­ной под­ста­нов­ки. Впо­след­ст­вии эти ре­зуль­та­ты во мно­гом слу­жи­ли об­раз­цом для изу­че­ния разл. клас­сов слу­чай­ных ком­би­на­тор­ных объ­ек­тов, в т. ч. слу­чай­ных раз­ме­ще­ний, слу­чай­ных раз­бие­ний це­лых чи­сел на це­ло­чис­лен­ные сла­гае­мые, разл. клас­сов слу­чай­ных гра­фов (слу­чай­ных ото­бра­же­ний, ле­сов, де­ревь­ев), слу­чай­ных мат­риц, сис­тем слу­чай­ных урав­не­ний, слу­чай­ных ав­то­ма­тов, слу­чай­ных ал­го­рит­мов.

При изу­че­нии слу­чай­ных гра­фов венг. ма­те­ма­ти­ка­ми П. Эр­дё­шем и А. Ре­ньи был об­на­ру­жен (1960) не­ожи­дан­ный эф­фект, ко­то­рый по ана­ло­гии с по­доб­ным эф­фек­том в по­ве­де­нии сис­тем час­тиц в ста­ти­стич. фи­зи­ке трак­ту­ет­ся как фа­зо­вый пе­ре­ход. Пусть $𝒢_{n,T}$ – слу­чай­ный граф с $n$ вер­ши­на­ми, ко­то­рый по­лу­ча­ет­ся в ре­зуль­та­те раз­ме­ще­ния $T$ рё­бер, каж­дое из ко­то­рых не­за­ви­си­мо от раз­ме­ще­ния ос­таль­ных рё­бер за­ни­ма­ет лю­бое из $n(n-1)/2$ воз­мож­ных мест с рав­ны­ми ве­ро­ят­но­стя­ми. Пусть $2T/n→λ$ при $n, T→∞$. Ес­ли $λ < 1$, точ­нее, ес­ли $(1–2T/n)^3n→∞$, то граф $𝒢_{n,T}$ с ве­ро­ят­но­стью, стре­мя­щей­ся к еди­ни­це, со­сто­ит из связ­ных ком­по­нент, ко­то­рые яв­ля­ют­ся ли­бо де­ревь­я­ми, ли­бо ком­по­нен­та­ми, со­дер­жа­щи­ми ров­но один цикл. При пе­ре­хо­де па­ра­мет­ром $2T/n$ зна­чения 1, точ­нее, в об­лас­ти, где при $n, T→∞$ па­ра­метр $(1–2T/n)^3$ стре­мит­ся к к.-л. по­сто­ян­ной $c$, по­яв­ля­ет­ся т. н. ги­гант­ская ком­по­нен­та, чис­ло вер­шин в ко­то­рой асим­пто­ти­че­ски нор­маль­но с ма­те­ма­тич. ожи­да­ни­ем $α (c)n$, при этом с убы­ва­ни­ем па­ра­мет­ра $c$ па­ра­метр $α(c)$ воз­рас­та­ет. При $(1–2T/n)^3n→–∞$ граф $𝒢_{n,T} $ с веро­ят­но­стью, стре­мя­щей­ся к еди­ни­це, со­сто­ит из ги­гант­ской ком­по­нен­ты, де­ревь­ев и ком­по­нент с од­ним цик­лом. Та­кое по­ве­де­ние слу­чай­но­го гра­фа при пе­ре­хо­де па­ра­мет­ром $2T/n$ зна­че­ния 1 мож­но ин­тер­пре­ти­ро­вать как фа­зо­вый пе­ре­ход или, дру­ги­ми сло­ва­ми, как на­ли­чие по­ро­го­во­го эф­фек­та в по­ве­де­нии слу­чай­но­го гра­фа. Позд­нее по­ро­го­вый эф­фект был об­на­ру­жен в по­ве­де­нии ещё бо­лее про­стых слу­чай­ных ком­би­на­тор­ных объ­ек­тов та­ких, как слу­чай­ные ле­са из кор­не­вых и не­кор­не­вых де­ревь­ев.

Ве­ро­ят­но­ст­ный под­ход ис­поль­зу­ет­ся и для до­ка­за­тель­ст­ва су­ще­ст­во­ва­ния ком­би­на­тор­ных объ­ек­тов без при­вле­че­ния кон­ст­рук­тив­ных по­строе­ний. Про­стей­ший ва­ри­ант это­го под­хо­да ос­но­ван на том, что ес­ли ма­те­ма­тич. ожи­да­ние це­ло­чис­лен­ной не­от­ри­ца­тель­ной слу­чай­ной ве­ли­чи­ны по­ло­жи­тель­но, то эта слу­чай­ная ве­ли­чи­на не рав­на то­ж­де­ст­вен­но ну­лю. Один из при­ме­ров при­ме­не­ния ве­ро­ят­но­ст­но­го под­хо­да со­сто­ит в сле­дую­щем.

Пусть $𝒢_n(p)$ – слу­чай­ный граф с $n$ вер­ши­на­ми, в ко­то­ром ка­ж­дая па­ра вер­шин не­за­ви­си­мо от ос­таль­ных со­еди­не­на реб­ром с ве­ро­ят­но­стью $p$ (с ве­ро­ят­но­стью $q$ та­ко­го реб­ра нет, $p+q=1$). В гра­фе

$\overline{𝒢_{n}}(p)$, до­пол­ни­тель­ном к гра­фу ${𝒢_{n}(p)}$, па­ра вер­шин со­еди­не­на реб­ром то­гда и толь­ко то­гда, ко­гда та­ко­го реб­ра нет в ${𝒢_{n}(p)}$. Пусть $v_n(p, k)$ и $\overline{v_{n}}(p, k)$ – чис­ла пол­ных под­гра­фов с $k$ вер­ши­на­ми в $𝒢_n(p)$ и $\overline{𝒢_{n}}(p)$ со­от­вет­ст­вен­но. Для ма­те­ма­тич. ожи­да­ний спра­вед­ли­вы ра­вен­ст­ва

$\mathsf{M}v_n(p,k)=C_{n}^{k}p^{k(k-1)/2},$

$\mathsf{M}\overline{v}_n(p,k)=\mathsf{M}v_n(q,k)=C_{n}^{k}q^{k(k-1)/2}.$

Ес­ли число $k > max$ $\{$ $[2$ $\ln n /$ $\ln (1/p)]$$,[ 2 \ln n /$ $ \ln$ $(1/q)$ $]\}$, где  $C_{n}^{k}$ – би­но­ми­аль­ные ко­эф­фи­ци­ен­ты, $[a]$ – це­лая часть чис­ла $a$, то и при $n→∞$. След­ст­ви­ем этих со­от­но­шений яв­ля­ет­ся то, что для ка­ж­до­го фик­си­ро­ван­но­го $p, 0 < p < 1$, и ка­ж­до­го дос­та­точ­но боль­шо­го $n$ су­ще­ст­ву­ет граф $G_n(p)$ c $n$ вер­ши­на­ми, не со­дер­жащий пол­но­го под­гра­фа с бо­лее чем $2\ln n/\ln(1/p)$ вер­ши­на­ми, до­пол­нитель­ный граф $\overline{G}_n(p)$ ко­то­ро­го не со­дер­жит пол­но­го под­гра­фа с бо­лее чем $\ln n/ \ln(1/q)$ вер­ши­на­ми.

 

Зна­чи­тель­ное вни­ма­ние в В. к. уде­ляет­ся ге­не­ра­ции по­сле­до­ва­тель­но­стей слу­чай­ных чи­сел, ге­не­ра­ции слу­чай­ных ком­би­на­тор­ных объ­ек­тов та­ких, как слу­чай­ные под­ста­нов­ки, а так­же ве­ро­ят­ност­но­му ана­ли­зу ал­го­рит­мов и по­строе­нию ве­ро­ят­но­ст­ных ал­го­рит­мов, вклю­чаю­щих в се­бя дат­чи­ки слу­чай­ных чи­сел.

Лит.: Гон­ча­ров В. Л. О рас­пре­де­ле­нии цик­лов в пе­ре­ста­нов­ках // Док­ла­ды АН СССР. 1942. Т. 35. № 9; он же. Из об­лас­ти ком­би­на­то­ри­ки // Из­вес­тия АН СССР. Сер. ма­те­ма­ти­че­ская. 1944. Т. 8. № 1; Сте­па­нов В. Е. Фа­зо­вые пе­ре­ходы в слу­чай­ных гра­фах // Тео­рия ве­ро­ят­но­стей и ее при­ме­не­ния. 1970. Т. 15. Вып. 2; Кол­чин В. Ф., Се­ва­сть­я­нов Б. А., Чис­тя­ков В. П. Слу­чай­ные раз­ме­ще­ния. М., 1976; Сач­ков В. Н. Ве­ро­ят­но­ст­ные ме­то­ды в ком­би­на­тор­ном ана­ли­зе. М., 1978; Пав­лов Ю. Л. Слу­чай­ные ле­са. Пет­ро­за­водск, 1996; Кол­чин В. Ф. Слу­чай­ные гра­фы. 2-е изд. М., 2004.

Вернуться к началу