Про планарні квазівипадкові графи Пуассонівського типу
В роботі розглядається задача оцінки зв'язаності планарних квазівипадкових графів.
Gespeichert in:
Datum: | 2010 |
---|---|
1. Verfasser: | |
Format: | Artikel |
Sprache: | Ukrainian |
Veröffentlicht: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2010
|
Schriftenreihe: | Моделювання та інформаційні технології |
Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/21965 |
Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
Zitieren: | Про планарні квазівипадкові графи Пуассонівського типу / О.Д. Глухов // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 58. — С. 11-14. — Бібліогр.: 2 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraineid |
irk-123456789-21965 |
---|---|
record_format |
dspace |
spelling |
irk-123456789-219652011-06-21T12:05:46Z Про планарні квазівипадкові графи Пуассонівського типу Глухов, О.Д. В роботі розглядається задача оцінки зв'язаності планарних квазівипадкових графів. В работе рассматривается задача оценки связности планарных квазислучайных графов. In this paper we study the problem of estimating the connectivity of planar quasi-random graphs. 2010 Article Про планарні квазівипадкові графи Пуассонівського типу / О.Д. Глухов // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 58. — С. 11-14. — Бібліогр.: 2 назв. — укр. XXXX-0068 http://dspace.nbuv.gov.ua/handle/123456789/21965 681.142 + 519.4 uk Моделювання та інформаційні технології Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
collection |
DSpace DC |
language |
Ukrainian |
description |
В роботі розглядається задача оцінки зв'язаності планарних квазівипадкових графів. |
format |
Article |
author |
Глухов, О.Д. |
spellingShingle |
Глухов, О.Д. Про планарні квазівипадкові графи Пуассонівського типу Моделювання та інформаційні технології |
author_facet |
Глухов, О.Д. |
author_sort |
Глухов, О.Д. |
title |
Про планарні квазівипадкові графи Пуассонівського типу |
title_short |
Про планарні квазівипадкові графи Пуассонівського типу |
title_full |
Про планарні квазівипадкові графи Пуассонівського типу |
title_fullStr |
Про планарні квазівипадкові графи Пуассонівського типу |
title_full_unstemmed |
Про планарні квазівипадкові графи Пуассонівського типу |
title_sort |
про планарні квазівипадкові графи пуассонівського типу |
publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
publishDate |
2010 |
url |
http://dspace.nbuv.gov.ua/handle/123456789/21965 |
citation_txt |
Про планарні квазівипадкові графи Пуассонівського типу / О.Д. Глухов // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 58. — С. 11-14. — Бібліогр.: 2 назв. — укр. |
series |
Моделювання та інформаційні технології |
work_keys_str_mv |
AT gluhovod proplanarníkvazívipadkovígrafipuassonívsʹkogotipu |
first_indexed |
2025-07-02T21:59:41Z |
last_indexed |
2025-07-02T21:59:41Z |
_version_ |
1836574134270689280 |
fulltext |
11 © �.�. �����
���
� ��������
����� �� ��� � ������������� ���������� ������, � �����
,
��� � �������� ���
�� �� 10,8 %); ��������! , %� � � ��� .
1. ��������� .
. "
�
���
���
���� # $�
��
��
�����: ����� 3. –
&.:'�
��!,1975. – 120 �.
2. ������
.�.,
������� �.�. (���
� �
��
�#� $�
��
��������#� ���
*. –+�
:
"
�����,1974.– 352 �.
3. ������� �.�., ������� �.�. &
���#
�
��! ���
�
����#� �
� �
��* �
�
��
������ ��! '-&. – +�
: /���� � �����, 1978. – 292 �.
4. ��������� �.�., �����!��� .�. 6�
� ����� �� ���
�����
��! ���
�
� �
���<���! ���� . – &.:/����,1981. – 720 �.
5. "���#�� �.�., ������� �.�. 6���
� ��������* ����
�# ���
*���� � ����
�! �
�����!��#�� ��������� // >�. ����. �
. ?@&A ��. �. B. @��� � /C/ D�
����. –
+.:2010. – -#�.55. – 6.3–11.
6. ���!��� �. �. &
���# � ����
���# ����
�� �������- � $�
��
�������
����
���
*: ����… ���. �
�. ����: 05.09.05. – 6��G
�����, 1987. – 369 �.
��$�%&��� 11.10.2010�.
D�+ 681.142 + 519.4
�.�. �����
��� ��������
���
���
�
� �����
��������
�� ��� ����
-
�����
����!��I���! ������ ������ � ’!������ �����
���
� ��� ������ �� �
�G� .
-
����
������
� �
��! ������ ��
��� � !������ �����
�#�
� ��������*�#� �
�G� .
In this paper we study the problem of estimating the connectivity of planar
quasi-random graphs.
+ ��� ������ �� �
�G�� (��� ������ �- ������ �� �
�G��) �� ���� �
� ���*���� �
�G� G � �������� 0G
��� � �������� 1G
�
,
0 1| | , | | ,G n G m� � ���� �I���! �
�G ( )G p � ������ �� ��������
�
1( ( ))U G p� , �
( )Prob u U p� � , !�<� 1u G� , ( ) 0Prob u U� � , !�<� 1u G .
"��
����!������! � ��� ������ � �
�G� �������� ������ ����, ��! !���
�����I���! ��� �: 1 /p m
� � , �
- �
!�� ���������. "��� �
�G� ����
�
�� ������ [1] ��! ���
�� ���! ����
���� ����
�, ��
����
� !���
���
����� ����� �������� ������ ���
��
� � ������� � ’!��� . - ����*
�����
����!��I���! ������ ������ *�� �
����� P � ’!������ �
�G� ( )G p �
12
������, ���� �
�G G I �����
��� 3-� ’!���� �
�G��.
D ������, ���� G - 3-� ’!���* �
�G, ��! *�� �
����� P ��
�
��� �
������ [1]:
3
1
m
k
k
k
P q�
�
�
� ,
�
1q p� � , ( )k k G� �� - ����� ����������� (�� ����
���)
�
��� k-
��
��� �
�G� G.
/������� � � �
�� ����� ������ ������ ( )k G� ��! �����
���� 3-
� ’!����� �
�G� G.
/
��* G - � ’!����� �
�G, 0,A B G� , 0 \A G A� ; ������ ���
��
���������: [ ]G A - ��
���
��* ����
�G �
�G� G �� �������
��� A,
1( , ) {( , ) : , , ( , ) }E A B a b a A b B a b G� � � � , ( , ) ( , )A B E A B� � , ( ) ( , )A A A� �� .
6������� ��
�
�� ���� �
������ �
��.
���� 1. L�<� M - �����
�� �������, |M|=m, 1{ }k
jA - �����
���
*�� � ��
�
������ ���������, <� ���� ����!I ��� �:
( ) ( ) ( )i j j i i jA A A A A A� � � � � �� , �
� i'j �� k (2m-1.
��������. >������I�� �������� �� ����� m. ��! m=1 �
��
��! �
��
��
���
. /
��* ��! ���� p, p<m �
�� �
�� � �
��* 1{ }s
jB - ���
*�� �
������������ �� ����
��� �������� �� M ��������� �� ��������
���
*�� � ������ 1{ }k
jA . L�<� s=1 �� ��I�� �
� �����
11 2 1 1 2( 1) 1 2 2k B m m
� �
� � � � � .
L�<� s)2, �� �� �
���<
��!� �������� ��I�� �������� �
� �����:
1 1
1 (2 1) 1 2 1 2 2 2 1
s s
i i
i i
k B B s m m
� �
� �
� �
� � � �� � .
"���� ����� �
�� ��
�
��.
���� 2. L�<� G - �����
��* 3-� ’!���* �
�G, �� *3(G) < 2n ( (4/3)m.
��������. >�� ����� ��������, <� ���
� ����������*
��
�� U
� ’!����� �
�G� G I ���
����
�, ����� ��! �
!���� 0A G� ( , )E A A U� .
"��� ������� 3-
��
��� U �
�G� G ����� ��� � ���� ������� I����
������� 0A G� , ( )A U� � , �
| | / 2A n
( � ������, ���� | | / 2A n� , ���
��� � ��� ������������ ,A A �� �����*). ���� ���
��
�
��, <� �������
1{ }k
jA ����� ��������� 0G , <� 0
iA G� , / 2, ( ) 3A n A�
� , ���� ����!I
��� �� �
�� 1 � ���� ����� ����� ���������, � ���
� ����� 3-
��
��� �
�����
2n-1.
@
�������� �
����
��
, <� ������� 1{ }k
jA �
���� ����!I ��� ��
�
�� 1 � ���
������� ���� ���������� 0,A B G� , <�
13
/ 2, / 2, ( ) ( ) 3A n B n A B� �
� � , ( ) ( ) ( )i j j i i jA A A A A A� � � � � � � .
@�������� �������� �������:
0
1 2 3 4, \ , \ , \ ( )M A B M A B M B A M G A B� � � � � � .
��
����, <� 1 2 3, ,M M M� � � � � � ; �����
��, <� ����� �
4M � � . ��*���, !�<� � 4M � � , �� ���� � ����
� ����� A B n� � ,
� ����,
��� ����, �
� ����� / 2, / 2A n B n
, ���� ���, <�
i jA A� �� . "���� ���������: ( , ), , 1, 2,3, 4.ij ji i jm m M M i j�� � �
>� ��� �� �
�� ��I�� �������� ��� �����
��!:
13 23 14 24( ) 3A m m m m� � � � � � ,
12 23 14 34( ) 3B m m m m� � � � � � ,
12 13 14 23 24 342 2 6m m m m m m� � � � � �
12 23 24 3m m m� � � , 13 23 34 3m m m� � � ,
12 14 13 3m m m� � � , 14 24 34 3m m m� � � .
> ��� ��� �����
�� ��
��� ���� �I, <� 23 14 0m m� � . "���� �����,
��
���I�� �������� ��� �����
��!:
13 24 3m m� � ,
12 34 3m m� � ,
12 13 3m m� � ,
12 24 3m m� � ,
13 34 3m m� � ,
24 34 3m m� � .
> ��� ��� �����
�� ���� �I, <� 12 13 24 34 1,5m m m m� � � � , <�
��
���� �
����� �.
���
,
��� ���� �
�� 1, ��I��, <� *3(G) < 2n ( (4/3)m.
���� 3. L�<� G - �
����* ( �
� �
�
�� � �
�����
�
) �����
��* 3-
� ’!���* �
�G, �� �
� k )4 ��I ����
�������� �
� �����:
*k(G) ( / 21 (2 )
2
km
k
.
��������. ��*���, �
��* G* - �
�G, �������* �� �
�G� G. "��� ��!
����� zk(G*) ����� �� ���� k �
�G� G*, �
�� �
� �����
zk(G*) ( (1/2k)tr(Ak) =(1/2k)
1
n
k
i
i
�
�
� , �
� – ���
��! ����������, � 1{ }n
i� –
��
��
�
�G� G* [2]. -
��� � �� �
� ����� B��
��: 2 2
1 1
( ) ( )
n n
k k
i k
i i
� �
� �
� � , �
k ) 2, ��
���I�� �
������� ������ ��! ����� zk(G*) , � ���
� ��! ����� *k(G).
>� ��������� ����� � �� �
� ����� ��
��� �������
�
��
��!.
14 © N.-.&�
�����
���
�������. L�<� G(p) – � ��� ������ �* �
�G �������� ������ ���� ��
���� � 3-� ’!����� �����
���� �
�G� G, �� ��! *�� �
����� P *��� � ’!������
�
�� �������� ������:
P ) 1 7 $m72, �
$ –�
!�� �����.
��������. ��! ��
�
��! �
�
�� ���
����I���� �
� �����
1 7 P
3
m
k
k
k
q�
�
� � ����
�� �� � ��� ������ ��! *k(G), !�� ����� �
��
�
���� 1 �� 2. &�I�� �
� �����:
3 / 2
2 / 2
3 4
4 1 21
3 2
k km m
k k
k
k k
P q m m
k
� � �
� �
�
� �� � .
��������
– �����, ���
�� �����, <� ��I ����
�
� ����� 28m
� �
���� �
�� �
� ����� 1 / 2k ku u�
, �
/ 2
/ 22k k
k
ku m
k
�� , � ������� 4
4
2
m
k
k
u u
�
�� .
��������� ��
���I�� �������� �
� �����:
3 2 4
2 2 24 21
3 4
P m m cm
� � �� � � � ,
� !��� ���� �I �
��
��! �
�
��.
1. 8�%9��
.�., ���$�:�� ;.
. 6�
����
�� �
��
�� �������� ����
���� ����
�
�
� ������ �� ���� ��. -&��
�� ���! �� ��G�
����*�� �
��������. >��
���
����� �� �
��� ?@&A /C/D, ��. 27, +�� , 2004, �. 91-95.
2. >�������? �., �%@ �., C�9$ D. 6�
��
# �
�G� . "
�
�! � �
��
�
��
.-+�
:
/���� � �����, 1984. -384 �.
��$�%&��� 4.10.2010�.
D�+. 621.38; 536.5
N.-.&�
�����
���
�
�������
�������������-���!���!���"#
����!��#
In IMS most expedient is outwardly-internal adaptation, the example of which
are structural methods of increase of exactness, and, in less degree, inwardly-internal
adaptation. For STD the use of all four types of adaptation is possible.
/�����* ���� �* �
� ������
������ G����
���� �
��
���
������#� �G
�� �
��
�
���* �
!�
�������, ���# �
�#� �
���
��#��
�
��
��#�� ������!�� - Problem area (PRAR), ! �!
��! �������
|