Про планарні квазівипадкові графи Пуассонівського типу

В роботі розглядається задача оцінки зв'язаності планарних квазівипадкових графів.

Gespeichert in:
Bibliographische Detailangaben
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 Ukraine
id 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), ! �! ��! �������