close

Вход

Забыли?

вход по аккаунту

?

Число компонент связности случайного графа.

код для вставкиСкачать
?????????? ? ????????
??? 514.765
?.?. ??????, ?.?. ????????
????? ????????? ????????? ??????????
??????
M.A. Lvova, V.V. Slavsky
The Number of Components
of Connectivity of the Random Graph
????????? ????????? ??????????? ????????
????????? ??? ????????? ?????, ??? ????? ?????? ? ?????? ??????-????? ????????? ??????.
This article focuses on random tolerant binary
relations or random graphs. Specifically, the study
aimed to investigate the Erdo?s- Re?nyi random graph
model.
???????? ?????: ????????? ?????????, ????????? ?????.
1. ??????????? ????, ??? ? ??????? ?? 1 ??????
???????????????.
????? ????? ????????????? ????????? ????????????? ??? ?????, ? ????? ?????? ? ????????
?????????. ????? ??????????? ????????? ????? 1 ????? ???????????????, ?????????? ? ??????????, ????? ???? ????????? ????????????? ???
???????. ??????? ???? ? ??????????? ??????????? ????? ? ??? ??????. ?? t ???????? ????? ????????? tt?2 ????????? ????????. ?? ??????? ???????? ? 42 , ??? ???? ????? ??????? ?????
????? 3 ?????. ????? ?????????? ??????????? ????????? ?????? ????????? 42 и p3 и (1 ? p)3 .
????? ? 4-?? ????????? ? 4-?? ??? ????? ??????? ??? ????? ????????. ??????????? ?????????
??????????????? ????????? ?????????????
? ???????????? ?????? (??????????, ????????,
?????????, ????????, ??????, ????? ? ??.), ? ????? ? ???????????? ?????? (??????????, ?????????, ???????, ???????????, ?????????? ? ??.) ?????
????????? ?????? ????????????? ??? ????????????? ???????? ?? ?? ???????????????. ????????? ????????? ? ???????? ??????? ???????? ??????????? ???????? ????????? ????? ?????????
? ???? ?????????? ????????.
?? ???????? ??????? ???????????? ?????????
? ?? ???????? ????????? ???????? X ???????????? ??????????? ?, ?????????????, ???????, ?? ?
????? ? ???? ????????? ?????????? ????????.
?????????? ??? ??????? ??????, ????? ????????? X ??????? ?? 4 ????????.
??????? 1. ????? ??????????? ????????? ?
????? ????????????? ????????????? ????????, ?.?.
?(xi , xi ) = 1 ? ??? i 6= j
?(xi , xj ) =
1
0
Key words: random relations, random graphs.
C64 и p4 и (1 ? p)2 + C65 и p5 и (1 ? p) + C66 и p6 .
??????????????, ??????????? ????, ??? ? ??????? ?? 1 ?????? ???????????????
? ???????????? p
? ???????????? q = 1 ? p.
P1 = 42 и p3 и (1 ? p)3 + C64 и p4 и (1 ? p)2 +
+C65 и p5 и (1 ? p) + C66 и p6 .
????????? ???????? ?(xi , xj ) ??????????. ????? ??????????? Pk ????, ??? ??????????? ?????????:
????? ? ????? k ??????? ???????????????,
P1 = p3 ?6p3 + 24p2 ? 33p + 16
P2 = (1 ? p)3 p2 (15 ? 11p)
P3 = 6(1 ? p)5 p
P4 = (1 ? p)6
??????????????. ??????? ???????, ?????????? ????????? ???? ? ?????? ??????????? ????
?????? ? ???????? ????? [2].
2. ??????????? ????, ??? ? ?????????? ?? ???
??????.
????? ? 3-?? ??????? ? 2-?? ???????? ????????????, ?? ????? C63 ? 42 .
????? ? 2-?? ??????? ? 2-?? ???????? ????????????. 12 C42 ? ????? ??????, ??? ???? ?????????? ??????? ?? 2-? ??????, ?????? ? ???? ??
????, C41 и 31 ? ????? ??????, ??? ???? ??????????
??????? ?? ????? ???????, ?????? ? ?? ????.
??????????????, ??????????? ????, ??? ? ?????????? ?? ??? ??????, ?????
P2 = C63 ? 42 и p3 и (1 ? p)3 +
1
+ C42 и p2 и (1 ? p)4 + 3C41 p2 (1 ? p)4 .
2
? ?????? ????????? ??? ????????? ?????????? ????????? ???? (?????? ? 08-01-98001), ? ??? ?? ????
Ф??????? ? ??????-?????????????? ????? ?????????????
??????╗ ?? 2009 ? 2013 ????, ???? Ф??????????????? ???????? ??????? ? ?????????╗ (????? ?????? ? ?????????????? ???????????????????? ??????? Ф2012-1.1-12-0001003-014╗.
28
????? ????????? ????????? ?????????? ?????
3. ??????????? ????, ??? ?????????? ?? ???
??????.
P3 = C61 p(1 ? p)5 .
????? ???????, ????? ????????? ???????????
????, ??? ???? ? n ????????? ??????? ?? k ????????? ?????????, ????? ?????? ????????????
????????? ????????? ?? n ????????? ?? k ??????????? V1 , . . . , Vk . ???????? ???? ????????
?????? ????????????? ???????? r1 ? и и и ? rk
? r1 + и и и + rk = n. ??? ??????? ?????? ????? r1 , . . . , rk ?????????? ???????? ?????? ??????????????? ??????????? ?????? ?????
4. ??????????? ????, ??? ? ?????????? ?? ?????? ??????. ??? ???????? ??????, ???? ??? ?????????????? ???????? ????. ?????????????, ??? ??????????? ?????
P4 = (1 ? p)
(4?1)4
2
= (1 ? p)6 .
rk
r2
=
и . . . и Cn?r
Cnr1 и Cn?r
1 ?...?rk?1
1
??????? ????????.
??????? 2. ????? ??????????? ????????? ? ??
????????? X ?? n ????????? ????? ?????????????
????????????? ????????, ?.?. ?(xi , xi ) = 1 ? ???
i 6= j
1 ? ???????????? p
?(xi , xj ) =
0 ? ???????????? q = 1 ? p.
=
n!
=
r1 ! и . . . и rk !
r1 ,...,rk
P (k, n) =
1?r1 ?иии?rk
r1 +иии+rk =n
и (1 ? p)
?(r1 , . . . , rk )
n
r1 ,...,rk
,
?(r1 , . . . , rk )
2 ?иии?r 2
n2 ?r1
k
2
n
.
r1 , . . . , rk
???????, ??? ???? ? ??????????? ?????????????????? r1 ? и и и ? rk ??????????? s ??????????
?????, ?? ??? ???????? ?????????? ???????? ?????? ??????????? ??????, ? ??? s! ??? ??????????????? ???? ? ??? ?? ?????? ??? ?????? ??????
?????????? ?????????, ?.? ????? ??? ?????? ?????????? ???????????? ??????? s. ???? ?????????
?????????? ?????? ????, ?? ?????????? ????????
??????? ???? ?? ???????? ?????
n
????????? ???????? ?(xi , xj ) ??????????. ?????
??????????? P (k, n) ????, ??? ??????????? ????????? ? ????? k ??????? ???????????????, ????????? ? ??????? ???????????? ????????:
? P (1, 1) = 1;
? ??? 2 ? k ? n
X
.
??? ????? ?(r1 , . . . , rk ) = s1 ! и и и st !, ????? s1 , . . . , st
???? ????? ???????? ? ??????????? ?????????????????? r1 ? и и и ? rk , ????????? ?? ??????
????? ????? ?????.
????? ?????????? ??????,??? ?? ??????????
???? ?? ??????? ?????? ???????? ? ???????
??? ??????. ??? ????????????. ????? n(n?1)
2
ri (ri ?1)
?? ????????
. ?????, ???????? n(n?1)
?
2
2
Pk ri (ri ?1)
???
??????,
???????
??
??????
i=1
2
???? ??????? ???????. ??????????? ??? ?????????
P (1, r1 ) и . . . и P (1, rk )и
(1)
??? ????? ?(r1 , . . . , rk ) = s1 ! и и и st !, ????? s1 ,. . . ,st
? ????? ???????? ? ??????????? ?????????????????? r1 ? и и и ? rk , ????????? ?? ?????? ?????
????? ?????
(??????: ?(2, 2, 3, 4, 4, 5) = 2!1!2!1!),
n
n!
=
r1 !иииrk ! ? ???????????? ??????????r1 ,...,rk
??.
? ??? k = 1;
k
k
n(n ? 1) X ri (ri ? 1)
n2 ? n X ri2 ? ri
?
=
?
=
2
2
2
2
i=1
i=1
P (1, n) = 1 ? P (2, n) ? P (3, n) ? и и и ? P (n, n).
??????????????. P (1, 1) = 1 ????????, ???
?? ????? ??????? ????? ????????? ?????? ????
????, ??????? ??????? ?? ????? ?????????? ?????????.
???? ? n ????????? ???????? k ?????????
????????? ????? ? ?????? ?????, ????? ? ???? ?????????? k ??????? ????????? ?????, ??? ?? ?????????? ???? ?? ??????? ?????? ???????? ? ??????? ???????, ?????? ????? ????? ?????? ????? ????????? ????? ????? ?????? ?????. ?????
G = (V, E), |V | = n ? ???? ? n ????????? ? k ???????????? ?????????. ?????????? ??? ?????????? (??????? ????? ???????? ??????????) ?? ??????????? ????? ??????: G1 = (V1 , E1 ), . . . , Gk =
(Vk , Ek ). ????????? ?????????? ?????? i-?? ????????, ??? ri = |Vi |. ???????? ?????? ?????????,
????? r1 ? и и и ? rk ? r1 + и и и + rk = n.
Pk
Pk
? (n ? i=1 ri )
n2 ? i=1 ri2
=
.
2
2
?? ??????????????? ??????????? ???????,
??? ??? 2 ? k ? n
=
n2 ?
Pk
2
i=1 ri
P (k, n) =
=
n
r1 ,...,rk
X
1?r1 ?иии?rk
r1 +иии+rk =n
и (1 ? p)
?(r1 , . . . , rk )
2 ?иии?r 2
n2 ?r1
k
2
P (1, r1 ) и . . . и P (1, rk )и
.
??? ????? ? n ????????? ???????????
1 = P (1, n) + P (2, n) + P (3, n) + . . . + P (n, n).
29
?????????? ? ????????
P (2, 8) = (p ? 1)7 p6 (13068p15 ? 225036p14 +
?? ???? ??????? ?????? ????????? ?? ???????
???????
+1813980p13 ? 9083564p12 + 31615787p11 ?
?81060259p10 + 158254628p9 ? 239732560p8 +
+284345642p7 ? 264338326p6 + 191274720p5 ?
P (1, n) = 1 ? P (2, n) ? P (3, n) ? и и и ? P (n, n).
?105964740p4 + 43595055p3 ? 12608323p2 +
+2300624p ? 200704);
P (3, 8) = ?14(p ? 1)13 p5 (938p10 ? 10822p9 +
??????? ????????.
+56393p8 ? 174947p7 + 358193p6 ?
??????. ??????? ???????????? ???????
??? n = 5.
?506371p5 + 501339p4 ? 343951p3 +
+156929p2 ? 43171p + 5472);
5
P (1, 1)P (1, 4)(1 ? p)4 +
1, 4
5
+
P (1, 2)P (1, 3)(1 ? p)6 ;
2, 3
5
P (2, 5) =
P (3, 5) =
1,1,3
+
1,2,2
2! 5
P (1, 1)P (1, 1)P (1, 3)(1 ? p)7 +
5
1,1,1,2
3!
P (6, 8) = 14(p ? 1)25 p2 (23p ? 27);
P (7, 8) = ?28(p ? 1)27 p;
P (8, 8) = (1 ? p)28 .
P (1, 1)4 P (1, 2)(1 ? p)9 ;
5
1,1,1,1,1
P (5, 5) =
P (5, 8) = ?70(p ? 1)22 p3 28p3 ? 98p2 + 115p ? 46 ;
P (1, 1)P (1, 2)P (1, 2)(1 ? p)8 ;
2!
P (4, 5) =
P (4, 8) = 7(p ? 1)18 p4 967p6 ? 6730p5 + 19605p4 ?
?30680p3 + 27285p2 ? 13134p + 2695 ;
?????????. ????????, ?????, ?????? ???????????? ??????? ??? P (1, n) [1, 2]:
P (1, 1)5 (1 ? p)10 ;
5!
P (1, 5) = 1 ? P (2, 5) ? P (3, 5) ? P (4, 5) ? P (5, 5).
1 ? P (1, n) =
n?1
X
k?1
P (1, k)Cn?1
(1 ? p)k(n?k) .
k=1
? ?????? ?????? ? ??????? ?? [1], ??-?????? ???????? ????? ???????????? ???????, ??-??????
?????????? ????????:
n
? ??????????? n ???????? P (k, n) ??????
???????????. ???????? ????????? ????????????? ?????????? ??? n = 8.
Q(r1 , . . ., rk ) =
7
P (1, 8) = p
?5040p
21
20
+ 120960p
19
? 1386000p +
+10086720p18 ? 52319190p17 + 205732800p16 ?
15
?636845160p
14
+ 1590501640p
r1 ,...,rk
?(r1 , . . . , rk )
О
О P (1, r1 ) и и и P (1, rk )(1 ? p)
2 ?иии?r 2
n2 ?r1
k
2
,
13
? 3258291120p +
??? 1 ? r1 ? и и и ? rk , n = r1 + и и и + rk . ???+ 9345271992p10 ? ??? ???????? ???????????? ??????????? ??????? ? ????? ???????????? ????, ??? ?????????
?9324568001p9 + 7786027816p8 ? 5410382880p7 +
???? ? n ????????? ? ?????? ??????-????? ???+3098951072p6 ? 1441519296p5 + 532354536p4 ?
?? ? ???????? k ????????? ????????? ??????? ??
?150657080p3 + 30802240p2 ? 4068456p + 262144 ; ???????????? r1 ? и и и ? rk .
+5536123600p
12
? 7856193296p
11
????????????????? ??????
1. Gilbert, E.N. Random graphs, Annls Math.
Statist. 30, 1141-1144, 1959.
2. Bela Bollobas. Random Graphs. Cambridge
studies in advanced mathematics, 73. Cambridge
University Press 2001.
30
Документ
Категория
Без категории
Просмотров
3
Размер файла
294 Кб
Теги
компонентов, связность, случайное, граф, числа
1/--страниц
Пожаловаться на содержимое документа