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

В роботі розглядається задача оцінки зв'язаності планарних квазівипадкових графів. В работе рассматривается задача оценки связности планарных квазислучайных графов. In this paper we study the problem of estimating the connectivity of planar
 quasi-random graphs....

Full description

Saved in:
Bibliographic Details
Published in:Моделювання та інформаційні технології
Date:2010
Main Author: Глухов, О.Д.
Format: Article
Language:Ukrainian
Published: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2010
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/21965
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Про планарні квазівипадкові графи Пуассонівського типу / О.Д. Глухов // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 58. — С. 11-14. — Бібліогр.: 2 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1860018554458341376
author Глухов, О.Д.
author_facet Глухов, О.Д.
citation_txt Про планарні квазівипадкові графи Пуассонівського типу / О.Д. Глухов // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 58. — С. 11-14. — Бібліогр.: 2 назв. — укр.
collection DSpace DC
container_title Моделювання та інформаційні технології
description В роботі розглядається задача оцінки зв'язаності планарних квазівипадкових графів. В работе рассматривается задача оценки связности планарных квазислучайных графов. In this paper we study the problem of estimating the connectivity of planar
 quasi-random graphs.
first_indexed 2025-12-07T16:46:21Z
format Article
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), ! �! ��! �������
id nasplib_isofts_kiev_ua-123456789-21965
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn XXXX-0068
language Ukrainian
last_indexed 2025-12-07T16:46:21Z
publishDate 2010
publisher Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
record_format dspace
spelling Глухов, О.Д.
2011-06-20T10:28:31Z
2011-06-20T10:28:31Z
2010
Про планарні квазівипадкові графи Пуассонівського типу / О.Д. Глухов // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 58. — С. 11-14. — Бібліогр.: 2 назв. — укр.
XXXX-0068
https://nasplib.isofts.kiev.ua/handle/123456789/21965
681.142 + 519.4
В роботі розглядається задача оцінки зв'язаності планарних квазівипадкових графів.
В работе рассматривается задача оценки связности планарных квазислучайных графов.
In this paper we study the problem of estimating the connectivity of planar&#xd; quasi-random graphs.
uk
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
Моделювання та інформаційні технології
Про планарні квазівипадкові графи Пуассонівського типу
Article
published earlier
spellingShingle Про планарні квазівипадкові графи Пуассонівського типу
Глухов, О.Д.
title Про планарні квазівипадкові графи Пуассонівського типу
title_full Про планарні квазівипадкові графи Пуассонівського типу
title_fullStr Про планарні квазівипадкові графи Пуассонівського типу
title_full_unstemmed Про планарні квазівипадкові графи Пуассонівського типу
title_short Про планарні квазівипадкові графи Пуассонівського типу
title_sort про планарні квазівипадкові графи пуассонівського типу
url https://nasplib.isofts.kiev.ua/handle/123456789/21965
work_keys_str_mv AT gluhovod proplanarníkvazívipadkovígrafipuassonívsʹkogotipu