Матрицы, ассоциированные с D-дистанционными магическими графами, и их свойства
Рассмотрены матрицы, ассоциированные с D-дистанционными магическими графами. Получены результаты относительно спектральных свойств этих матриц. Доказано, что если два графа G и H одинакового порядка имеют подобные дистанционные матрицы AD₁ и AD₂ соответственно, то граф G является D₁-дистанционным ма...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2019 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/180874 |
| 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: | Матрицы, ассоциированные с D-дистанционными магическими графами, и их свойств / М.Ф. Семенюта, В.А. Шульгин // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 112-120. — Бібліогр.: назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860260239335489536 |
|---|---|
| author | Семенюта, М.Ф. Шульгин, В.А. |
| author_facet | Семенюта, М.Ф. Шульгин, В.А. |
| citation_txt | Матрицы, ассоциированные с D-дистанционными магическими графами, и их свойств / М.Ф. Семенюта, В.А. Шульгин // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 112-120. — Бібліогр.: назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Рассмотрены матрицы, ассоциированные с D-дистанционными магическими графами. Получены результаты относительно спектральных свойств этих матриц. Доказано, что если два графа G и H одинакового порядка имеют подобные дистанционные матрицы AD₁ и AD₂ соответственно, то граф G является D₁-дистанционным магическим тогда и только тогда, когда H будет D₂-дистанционным магическим графом. Графы G и H названы магическими дистанционно-подобными и доказано, что их дистанционные магические постоянные совпадают.
Розглянуто матриці, асоційовані з D-дистанційними магічними графами. Отримано результати щодо спектральних властивостей цих матриць. Доведено, що в тому разі, якщо два графи G і H однакового порядку мають подібні дистанційні матриці AD₁ і AD₂ відповідно, то граф G є D₁-дистанційним магічним тоді й тільки тоді, коли H буде D₂-дистанційним магічним графом. Графи G і H названо магічними дистанційно-подібними і доведено, що їхні дистанційні магічні сталі збігаються
Matrices associated with D-distance magic graphs are considered in the paper. Results regarding the spectral properties of these matrices have been obtained. It has been proved that if two graphs G and H of the same order have similar distance matrices AD₁ and AD₂ respectively, then graph G is D₁-distance magic if and only if H is a D₂-distance magic graph. Graphs G and H are called magic distance-similar and their distance magic constants have been proved to coincide.
|
| first_indexed | 2025-12-07T18:54:29Z |
| format | Article |
| fulltext |
ÓÄÊ 519.1:512.643
Ì.Ô. ÑÅÌÅÍÞÒÀ, Â.À. ØÓËÜÃÈÍ
ÌÀÒÐÈÖÛ, ÀÑÑÎÖÈÈÐÎÂÀÍÍÛÅ Ñ D-ÄÈÑÒÀÍÖÈÎÍÍÛÌÈ
ÌÀÃÈ×ÅÑÊÈÌÈ ÃÐÀÔÀÌÈ, È ÈÕ ÑÂÎÉÑÒÂÀ
Àííîòàöèÿ. Ðàññìîòðåíû ìàòðèöû, àññîöèèðîâàííûå ñ D-äèñòàíöèîííûìè
ìàãè÷åñêèìè ãðàôàìè. Ïîëó÷åíû ðåçóëüòàòû îòíîñèòåëüíî ñïåêòðàëüíûõ
ñâîéñòâ ýòèõ ìàòðèö. Äîêàçàíî, ÷òî åñëè äâà ãðàôà G è H îäèíàêîâîãî ïî-
ðÿäêà èìåþò ïîäîáíûå äèñòàíöèîííûå ìàòðèöû AD1
è AD2
ñîîòâåòñòâåííî,
òî ãðàô G ÿâëÿåòñÿ D1-äèñòàíöèîííûì ìàãè÷åñêèì òîãäà è òîëüêî òîãäà,
êîãäà H áóäåò D2-äèñòàíöèîííûì ìàãè÷åñêèì ãðàôîì. Ãðàôû G è H íàçâà-
íû ìàãè÷åñêèìè äèñòàíöèîííî-ïîäîáíûìè è äîêàçàíî, ÷òî èõ äèñòàíöèîí-
íûå ìàãè÷åñêèå ïîñòîÿííûå ñîâïàäàþò.
Êëþ÷åâûå ñëîâà: D-îêðåñòíîñòü, D-äèñòàíöèîííàÿ ìàãè÷åñêàÿ ðàçìåòêà, D-äèñ-
òàíöèîííàÿ ìàòðèöà, ìàòðèöà ðàçìåòêè, D-äèñòàíöèîííàÿ ìàãè÷åñêàÿ ìàòðèöà.
ÂÂÅÄÅÍÈÅ
Ïåðâûå ïóáëèêàöèè î ðàçìåòêàõ ãðàôîâ ïîÿâèëèñü â ñåðåäèíå 60-õ ãîäîâ ïðî-
øëîãî ñòîëåòèÿ. Ìîòèâàöèåé ê çàðîæäåíèþ ýòîãî íàïðàâëåíèÿ èññëåäîâàíèé
ïîñëóæèë ðÿä ïðè÷èí. Îäíà èç íèõ, ñâÿçàííàÿ ñ ïîèñêîì ìåòîäîâ ðåøåíèÿ ãè-
ïîòåçû Ã. Ðèíãåëÿ î ðàçëîæåíèè ïîëíîãî ãðàôà K n2 1� íà 2 1n� ïîäãðàôîâ,
êàæäûé èç êîòîðûõ èçîìîðôåí äåðåâó ðàçìåðà n , îáóñëîâèëà âîçíèêíîâåíèå
ïîíÿòèÿ ãðàöèîçíîé è åé ïîäîáíîé ðàçìåòîê ãðàôîâ. Ìàãè÷åñêèé è àíòèìà-
ãè÷åñêèé òèïû ðàçìåòîê ïåðâîíà÷àëüíî ââåäåíû êàê èíñòðóìåíò äëÿ èñïîëüçîâà-
íèÿ ìàãè÷åñêèõ êâàäðàòîâ, ìàãè÷åñêèõ ïðÿìîóãîëüíèêîâ, ìàññèâîâ Êîöèãà â òåî-
ðèè ãðàôîâ. Ïîëíûé îáçîð ïóáëèêàöèé, ïîñâÿùåííûõ ðàçìåòêàì ãðàôîâ, ïðåä-
ñòàâëåí Ä. Ãàëëèàíîì â ýëåêòðîííîì æóðíàëå «A dynamic survey of graph
labeling» [1]. Æóðíàë åæåãîäíî ïåðåèçäàåòñÿ è ïîïîëíÿåòñÿ ñâåäåíèÿìè î íîâûõ
ðåçóëüòàòàõ èññëåäîâàíèé. Ýòîò ðàçäåë òåîðèè ãðàôîâ ïðîäîëæàåò èíòåíñèâíî
ðàçâèâàòüñÿ. Ïîïóëÿðíîñòü äàííîé òåìàòèêè îáúÿñíÿåòñÿ øèðîêèì êðóãîì ïðèìå-
íåíèé òåîðèè ðàçìåòîê. Íàïðèìåð, ìîäåëèðîâàíèå ñëîæíûõ ñèñòåì ãðàôàìè
áîëüøîé ðàçìåðíîñòè îòíîñèòñÿ ê àêòóàëüíîé ñîâðåìåííîé ïðîáëåìå. Ñóùåñòâó-
åò ñïîñîá êîäèðîâêè ñòðóêòóðû òàêèõ ãðàôîâ, ñâÿçàííûé ñ íàëè÷èåì èçáûòî÷íîé
èíôîðìàöèè î ëîêàëüíûõ åãî ÷àñòÿõ, â òîì ÷èñëå ñâåäåíèé îá îêðåñòíîñòÿõ âåð-
øèí ïîäãðàôîâ çàäàííîãî ãðàôà. Íåêîòîðûå èç âåðøèííûõ ðàçìåòîê ÿâëÿþòñÿ
ïîëåçíûìè â ýòîé ñèòóàöèè, ñðåäè íèõ — D-äèñòàíöèîííàÿ ìàãè÷åñêàÿ ðàçìåòêà.
 ýòîé ðàáîòå áóäåì ðàññìàòðèâàòü êîíå÷íûå íåîðèåíòèðîâàííûå ãðàôû, íå
ñîäåðæàùèå êðàòíûõ ðåáåð è ïåòåëü. Â îáùåì âèäå îïðåäåëåíèå ðàçìåòêè ãðàôà
ìîæíî ñôîðìóëèðîâàòü òàê: ðàçìåòêà f ãðàôà G V E� ( , ) ïðåäñòàâëÿåò ñîáîé áè-
åêòèâíîå èëè èíúåêòèâíîå îòîáðàæåíèå ìíîæåñòâà ýëåìåíòîâ ãðàôà G íà ìíî-
æåñòâî ÷èñåë (÷àùå íàòóðàëüíûõ èëè öåëûõ), êîòîðîå óäîâëåòâîðÿåò îïðåäåëåí-
íûì óñëîâèÿì. Ýòè óñëîâèÿ çàâèñÿò îò òèïà ðàçìåòêè. Åñëè îíà îòíîñèòñÿ ê
ìàãè÷åñêîìó òèïó, òî äîïîëíèòåëüíî íà V èëè E ââîäèòñÿ âåñîâàÿ ôóíêöèÿ, ïðè-
íèìàþùàÿ îäèíàêîâûå çíà÷åíèÿ äëÿ êàæäîãî ýëåìåíòà ñîîòâåòñòâóþùåãî ìíî-
æåñòâà. Êðîìå òîãî, ðàçìåòêè ðàçäåëÿþò íà âåðøèííûå, ðåáåðíûå, òîòàëüíûå â çà-
âèñèìîñòè îò îáëàñòè îïðåäåëåíèÿ ôóíêöèè f . Äàëåå ðå÷ü ïîéäåò î D-äèñòàíöè-
îííîé ìàãè÷åñêîé ðàçìåòêå, ÿâëÿþùåéñÿ âåðøèííîé ðàçìåòêîé ìàãè÷åñêîãî òèïà.
Îíà ïðåäñòàâëÿåò ñîáîé îáîáùåíèå ïîíÿòèÿ äèñòàíöèîííîé ìàãè÷åñêîé ðàçìåòêè,
èçâåñòíîé òàêæå êàê � ðàçìåòêà è 1-âåðøèííàÿ ìàãè÷åñêàÿ ðàçìåòêà [2–5].  äèñ-
112 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
© Ì.Ô. Ñåìåíþòà, Â.À. Øóëüãèí, 2019
òàíöèîííîì ìàãè÷åñêîì ãðàôå G V E� ( , ) ìåòêàìè âåðøèí ñëóæàò ÷èñëà îò åäè-
íèöû äî | |V , à âåñ âåðøèíû îïðåäåëÿåòñÿ êàê ñóììà ìåòîê ñìåæíûõ åé âåðøèí è
âñå âåðøèíû èìåþò îäèíàêîâûé âåñ. Äëÿ D-äèñòàíöèîííîãî ìàãè÷åñêîãî ãðàôà
ìíîæåñòâî ñìåæíîñòè âåðøèíû ðàñøèðåíî íà åå D-îêðåñòíîñòü, ãäå
D d� { }0 1 2, , , ,� , d G� diam( ) — äèàìåòð ãðàôà G. Âïåðâûå D-äèñòàíöèîííàÿ ìà-
ãè÷åñêàÿ ðàçìåòêà ïðåäëîæåíà â ðàáîòå [6].
Çà÷àñòóþ óäîáíî èìåòü äåëî íå ñ ðàçìå÷åííûì ãðàôîì, à ñ åãî ìàòðè÷íûìè
ïðåäñòàâëåíèÿìè. Ìàòðèöû ðàçìåòêè îïèñàíû â ðàáîòàõ [5–9]. Àâòîðû ðàáî-
òû [6] ïðèìåíèëè ìàòðè÷íûé àíàëèç ïðè ðåøåíèè ïðîáëåìû ñóùåñòâîâàíèÿ
D-äèñòàíöèîííîé ìàãè÷åñêîé ðàçìåòêè ( , )D r -ðåãóëÿðíîãî ãðàôà.  [7] ïîëó÷åíû
íåêîòîðûå ðåçóëüòàòû îòíîñèòåëüíî ñâÿçè ìåæäó çàêðûòîé äèñòàíöèîííîé ìàãè-
÷åñêîé ðàçìåòêîé ãðàôà è åãî ñïåêòðîì.  ýòîé ñòàòüå èññëåäîâàíû ñâîéñòâà
ìàòðèö, àññîöèèðîâàííûõ ñ D-äèñòàíöèîííûìè ìàãè÷åñêèìè ãðàôàìè.
ÏÎÍßÒÈß È ÎÏÐÅÄÅËÅÍÈß
Ìíîæåñòâî âñåõ âåðøèí ãðàôà G V E� ( , ) , ñìåæíûõ ñ íåêîòîðîé âåðøèíîé
� �V , íàçûâàþò (îòêðûòûì) ìíîæåñòâîì ñìåæíîñòè âåðøèíû � è îáîçíà÷àþò
N ( )� . Âåðøèíà � âìåñòå ñ N ( )� îáðàçóþò çàêðûòîå ìíîæåñòâî ñìåæíîñòè �,
êîòîðîå îáîçíà÷èì N [ ]� , ò.å. N N[ ] { } ( )� � �� � .
Ïóñòü çàäàíî ìíîæåñòâî D d� { }0 1 2, , , ,� , ãäå d G� diam( ) . D-îêðåñòíîñòü
âåðøèíû � �V G( ) îáîçíà÷àåòñÿ N D ( )� è ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî âñåõ
âåðøèí u V G� ( ) , íàõîäÿùèõñÿ íà ðàññòîÿíèè d u D( , )� � îò âåðøèíû � , ò.å.
N u V G d u DD ( ) { ( ) : ( , ) }� �� � � . Òàêèì îáðàçîì, N N{ } ( ) ( )1 � �� è N N{ , } ( ) [ ]0 1 � �� .
Ðàññìîòðèì íåêîòîðîå ìíîæåñòâî (èëè, â îáùåì ñëó÷àå, ìóëüòèìíîæåñòâî)
M m m m Rn� �{ , , , }1 2 � , ñîñòîÿùåå èç äåéñòâèòåëüíûõ ÷èñåë, è âåðøèííóþ ðàç-
ìåòêó f V G M: ( ) � äëÿ ãðàôà G V E� ( , ) ïîðÿäêà n, ãäå f — áèåêöèÿ. Ïîä âåñîì
ïîäìíîæåñòâà S V G� ( ) ïðè ðàçìåòêå f ïîíèìàþò ÷èñëî w S f u
u S
( ) ( ),�
�
ãäå
ñóììèðîâàíèå ïðîèçâîäèòñÿ ïî âñåì u S� . Âåñ w( )� (èëè w f ( )� ) âåðøèíû � äëÿ
ðàçìåòêè f îïðåäåëÿåòñÿ êàê ñóììà ìåòîê âåðøèí D-îêðåñòíîñòè âåðøèíû �, òî
åñòü w f u
u N D
( ) ( )
( )
�
�
�
�
, ãäå � �V G( ) .  òàêîì ñëó÷àå w N wD( ( )) ( )� �� .  äàëü-
íåéøåì íàñ áóäåò èíòåðåñîâàòü ìíîæåñòâî M n� { , , ..., }1 2 .
Îïðåäåëåíèå 1 [6]. Ãðàô G ïîðÿäêà n íàçûâàþò D-âåðøèííî-ìàãè÷åñêèì èëè
D-äèñòàíöèîííûì ìàãè÷åñêèì, åñëè ñóùåñòâóåò áèåêöèÿ f V G n: ( ) { , , , }� 1 2 � è
òàêàÿ ïîñòîÿííàÿ k, ÷òî äëÿ êàæäîé âåðøèíû � �V G( ) èìååì w k( )� � . ×èñëî k íàçû-
âàþò D-äèñòàíöèîííîé (èëè äèñòàíöèîííîé) ìàãè÷åñêîé ïîñòîÿííîé ðàçìåòêè f .
Ïðè D � { }1 ðàçìåòêó f ãðàôà G íàçûâàþò äèñòàíöèîííîé ìàãè÷åñêîé èëè
�-ðàçìåòêîé, à ïðè D � { , }0 1 — �
-ðàçìåòêîé. Òàêæå èñïîëüçóþò òåðìèí «l-âåð-
øèííàÿ ìàãè÷åñêàÿ» ðàçìåòêà, åñëè G ÿâëÿåòñÿ D-äèñòàíöèîííûì ìàãè÷åñêèì
ãðàôîì è D l� { }, ãäå 0� �l d.
Îáîçíà÷èì M n ìíîæåñòâî n n� ìàòðèö ñ ýëåìåíòàìè èç ìíîæåñòâà äåéñòâèòåëü-
íûõ ÷èñåë R. Ïóñòü A a Mij n� �( ) .  ñëåäóþùèõ ðàçäåëàõ íà M n áóäåì èñïîëüçîâàòü
ìàêñèìàëüíóþ ñòðî÷íóþ íîðìó, êîòîðàÿ îïðåäåëÿåòñÿ ôîðìóëîé || || max | |A a
i n j
n
ij
� � �
�
1 1
.
Ïîä ñïåêòðîì �( )A ìàòðèöû A ïîíèìàþò ñîâîêóïíîñòü âñåõ åå ñîáñòâåííûõ
çíà÷åíèé � �C, ãäå C — ìíîæåñòâî êîìïëåêñíûõ ÷èñåë. Ñïåêòðàëüíûé ðàäèóñ ìàò-
ðèöû A — ýòî íåîòðèöàòåëüíîå äåéñòâèòåëüíîå ÷èñëî � � � �( ) max{| | : ( )}A A� � .
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 113
Îäíîé èç ìàòðè÷íûõ èíòåðïðåòàöèé ãðàôà G V E� ( , ) ïîðÿäêà n ÿâëÿåòñÿ
ìàòðèöà ñìåæíîñòè âåðøèí A an n ij� � ( ) , ãäå aij �1, åñëè âåðøèíû u ui j, ñìåæ-
íûå â G, èíà÷å aij � 0. Ìàòðèöà ñìåæíîñòè A — ñèììåòðè÷íàÿ, ïîýòîìó åå
ñïåêòð, à ñëåäîâàòåëüíî è ñïåêòð ãðàôà G ñîäåðæèò n äåéñòâèòåëüíûõ ñîáñòâåí-
íûõ çíà÷åíèé � � �1 2� � �� n , ïðèíàäëåæàùèõ îòðåçêó [ , ]�� �1 1 , ãäå ñïåê-
òðàëüíûé ðàäèóñ ìàòðèöû A — íàèáîëüøåå äåéñòâèòåëüíîå ñîáñòâåííîå çíà÷å-
íèå � �1 � ( )A , íàçûâàåìîå èíäåêñîì ãðàôà G [10]. Íàïîìíèì îñíîâíûå ñâîéñòâà
ñïåêòðà � � �1 2, , ,� n ãðàôà G ïîðÿäêà n:
1) � i
i
n
�
�
1
0 ;
2) � �i
i
n
i
i
n
2
1 1� �
� deg( ) , ãäå deg( )� i — ñòåïåíü âåðøèíû � i V G� ( ) ;
3) � �� �1 � , ãäå � �
�
�
�
min ( )
( )i V G
ideg è � �
�
max ( )
( )�
�
i V G
ideg ;
4) � �� ��1 .
ÄÈÑÒÀÍÖÈÎÍÍÀß ÌÀÒÐÈÖÀ ÃÐÀÔÀ È ÅÅ ÑÂÎÉÑÒÂÀ
Îáîçíà÷èì { , , , }u u un1 2 � ìíîæåñòâî âåðøèí ãðàôà G ïîðÿäêà n . Ïóñòü
D d� { }0 1 2, , , ,� , ãäå d G� diam( ) . Ïîä D-äèñòàíöèîííîé (èëè äèñòàíöèîííîé)
ìàòðèöåé ãðàôà G ïîíèìàþò n n� áèíàðíóþ ìàòðèöó A aD ij
D� ( ) ñ ýëåìåíòàìè
aij
D �1 òîãäà è òîëüêî òîãäà, êîãäà d u u Di j( , )� , ãäå u u V Gi j, ( )� , â îñòàëü-
íûõ ñëó÷àÿõ aij
D � 0 .
Íåòðóäíî óáåäèòüñÿ, ÷òî ìàòðèöà AD ñèììåòðè÷íàÿ, ò.å. A AD D
� T , ñóììà åå ýëå-
ìåíòîâ â i-é ñòðîêå ðàâíà ìîùíîñòè ìíîæåñòâà N uD i( ) è a N uij
i
n
j
n
D i
i
n
�� �
�
11 1
| ( )| .
Åñëè D � { }1 , òîãäà A AD � ; åñëè D � { , }0 1 , òîãäà A A ED � � , ãäå A — ìàòðèöà
ñìåæíîñòè ãðàôà G, E — åäèíè÷íàÿ ìàòðèöà.  îáùåì ñëó÷àå äèñòàíöèîííóþ
ìàòðèöó ïðåäñòàâèì â âèäå ñóììû ñïåöèàëüíûõ êâàäðàòíûõ ìàòðèö As ïîðÿäêà
n : A A A A ED d� � � � ��1 1� , åñëè 0�D è A A A AD d� � � � �1 1� , åñëè 0�D, ãäå
A a Ms ij
s
n� �( )( ) è aij
s( ) �1ïðè d u u s Di j( , ) � � �1 , èíà÷å aij
s( ) � 0 , s d� �1 2 1, , ,� .
Îïðåäåëåíèå 2 [6]. Ãðàô G ïîðÿäêà n íàçûâàþò ( , )D r -ðåãóëÿðíûì, åñëè äëÿ
ëþáîé âåðøèíû � i V G� ( ) è êàæäîãî i n�1 2, , ,� âûïîëíÿåòñÿ ðàâåíñòâî
a rij
D
j
n
�
�
1
, êîãäà 0�D è a rij
D
j
n
�
� �
1
1, êîãäà 0�D , ãäå A aD ij
D� ( ) — äèñòàíöèîí-
íàÿ ìàòðèöà ãðàôà G, ò.å. âñå D-îêðåñòíîñòè èìåþò îäèíàêîâóþ ìîùíîñòü.
Ïóñòü çàäàí ãðàô G è áèåêöèÿ f V G n: ( ) { , , , }� 1 2 � . Ðàññìîòðèì ìàòðè÷-
íîå óðàâíåíèå
A X kID � , (1)
ãäå X f u f u f un� ( ( ) ( ) ( ))1 2 �
T — ìàòðèöà ìåòîê, ïðåäñòàâëÿþùàÿ ñîáîé ïåðå-
ñòàíîâêó ÷èñåë 1 2, , ,� n, I � ( )1 1 1�
T , k � const — íàòóðàëüíîå ÷èñëî. Î÷åâèä-
íî, ÷òî f áóäåò D-äèñòàíöèîííîé ìàãè÷åñêîé ðàçìåòêîé ãðàôà G, åñëè ñóùåñòâóåò
ïåðåñòàíîâêà X 0 è ÷èñëî k0 , óäîâëåòâîðÿþùèå óðàâíåíèþ (1).  [5] äîêàçàíà
åäèíñòâåííîñòü ìàãè÷åñêîé ïîñòîÿííîé äëÿ ëþáîãî äèñòàíöèîííîãî ìàãè÷åñêîãî
ãðàôà. Ýòà æå òåõíèêà äîêàçàòåëüñòâà ïðèâîäèò ê àíàëîãè÷íîìó ðåçóëüòàòó äëÿ
D-äèñòàíöèîííîãî ìàãè÷åñêîãî ãðàôà. Ïðåäïîëîæèì, ÷òî ãðàô G äîïóñêàåò äâå
D-äèñòàíöèîííûå ìàãè÷åñêèå ðàçìåòêè f è g ñ ñîîòâåòñòâóþùèìè äèñòàíöèîííû-
ìè ìàãè÷åñêèìè ïîñòîÿííûìè k1 è k2 . Ñîãëàñíî (1) èìååì A X k ID � 1 è
114 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
A Y k ID � 2 , ãäå Y g u g u g un� ( ( ) ( ) ( ))1 2 �
T . Ìàòðèöà Y A XD
T ñîñòîèò èç îä-
íîãî ýëåìåíòà, ïîýòîìó Y A X Y A X X A YD D D
T T T T� �( ) . Èç ýòîãî ñëåäóåò, ÷òî
k Y I k X I1 2
T T� èëè k n k n1 21 2 1 2( ) ( )� � � � � � �� � . Òàêèì îáðàçîì, k k1 2� .
Äîêàçàòåëüñòâî ýòîãî ôàêòà â òåðìèíàõ äðîáíîãî äîìèíèðîâàíèÿ ïðåäñòàâëåíî â [8].
Êàæäîìó ïîìå÷åííîìó ãðàôó G åäèíñòâåííûì îáðàçîì ñòàâèòñÿ â ñîîòâåò-
ñòâèå ìàòðèöà AD . Îäíàêî îáðàòíîå óòâåðæäåíèå íåâåðíî. Äâå äèñòàíöèîííûå
ìàòðèöû AD1
è AD2
ÿâëÿþòñÿ ïîäîáíûìè, åñëè ñóùåñòâóåò ìàòðèöà ïåðåñòàíîâ-
êè P òàêàÿ, ÷òî A P A PD D1 2
1� � .  ýòîì ñëó÷àå áóäåì ãîâîðèòü, ÷òî AD1
è AD2
ïðèíàäëåæàò îäíîìó êëàññó ïîäîáíûõ ìàòðèö. Íåèçîìîðôíûå ãðàôû îäèíàêîâî-
ãî ïîðÿäêà ìîãóò èìåòü ïîäîáíûå äèñòàíöèîííûå ìàòðèöû. Äëÿ íèõ
ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 2. Ïóñòü G è H — ãðàôû ïîðÿäêà n c ïîäîáíûìè äèñòàíöèîííûìè
ìàòðèöàìè AD1
è AD2
ñîîòâåòñòâåííî. Ãðàô G ÿâëÿåòñÿ D1-äèñòàíöèîííûì ìàãè-
÷åñêèì òîãäà è òîëüêî òîãäà, êîãäà H — D2-äèñòàíöèîííûé ìàãè÷åñêèé ãðàô.
Äîêàçàòåëüñòâî. Ïóñòü äàíû äâà ãðàôà G è H ïîðÿäêà n c äèñòàíöèîííûìè
ìàòðèöàìè AD1
è AD2
, ïðèíàäëåæàùèìè îäíîìó è òîìó æå êëàññó ïîäîáíûõ
ìàòðèö. Ïðåîáðàçîâàíèå ïîäîáèÿ áóäåì îñóùåñòâëÿòü ïîñðåäñòâîì ìàòðèöû ïå-
ðåñòàíîâêè P. Ñëåäîâàòåëüíî, A P A PD D1 2
1� � .
Ïðåäïîëîæèì, ÷òî f — D1-äèñòàíöèîííàÿ ìàãè÷åñêàÿ ðàçìåòêà ãðàôà G, ò.å.
ñóùåñòâóåò ïåðåñòàíîâêà X 0 è ÷èñëî k0 , óäîâëåòâîðÿþùèå óðàâíåíèþ (1):
A X k ID1
0
0� . Âîñïîëüçîâàâøèñü ïîäîáèåì ìàòðèö AD1
è AD2
, ïîëó÷èì
P A PX k ID
� �1 0
02
. Óìíîæèì ïîñëåäíåå ðàâåíñòâî ñëåâà íà P, ýòî ïðèâåäåò åãî ê
âèäó A PX k PID2
0
0� , ãäå PI I� , PX X0 0� * è ( )*X 0 T — îäíà èç ïåðåñòàíîâîê
÷èñåë 1 2, , ,� n.  ðåçóëüòàòå èìååì A X k ID2
0
0
* � . Èç ýòîãî ñëåäóåò, ÷òî ñó-
ùåñòâóåò ïåðåñòàíîâêà ( )*X 0 T , êîòîðàÿ çàäàåò D2-äèñòàíöèîííóþ ìàãè÷åñêóþ
ðàçìåòêó ãðàôà H ñ ìàãè÷åñêîé ïîñòîÿííîé k0 . Àíàëîãè÷íûå ðàññóæäåíèÿ ïðè-
âîäÿò ê äîêàçàòåëüñòâó îáðàòíîãî óòâåðæäåíèÿ. Òåîðåìà äîêàçàíà.
Ãðàôû ñ ïîäîáíûìè äèñòàíöèîííûìè ìàòðèöàìè íàçîâåì äèñòàíöèîííî-
ïîäîáíûìè. Î÷åâèäíî, äëÿ äèñòàíöèîííî-ïîäîáíûõ ( , )D r1 1 - è ( , )D r2 2 -ðåãóëÿð-
íûõ ãðàôîâ r r1 2� . Åñëè ãðàôû G è H èìåþò ïîäîáíûå äèñòàíöèîííûå ìàòðèöû
è ÿâëÿþòñÿ D1-, D2-äèñòàíöèîííûìè ìàãè÷åñêèìè, òîãäà èõ íàçîâåì ìàãè÷åñêè-
ìè äèñòàíöèîííî-ïîäîáíûìè.
Ñëåäñòâèå 1. Äëÿ ëþáûõ ìàãè÷åñêèõ äèñòàíöèîííî-ïîäîáíûõ ãðàôîâ èõ
äèñòàíöèîííûå ìàãè÷åñêèå ïîñòîÿííûå ñîâïàäàþò.
Äîêàçàòåëüñòâî. Ðàññìîòðèì äâà D1-, D2-äèñòàíöèîííûõ ìàãè÷åñêèõ ãðàôà G
è H ñîîòâåòñòâåííî. Ïðåäïîëîæèì, ÷òî îíè ÿâëÿþòñÿ äèñòàíöèîííî-ïîäîáíûìè. Èç
äîêàçàòåëüñòâà òåîðåìû 2 ñëåäóåò, ÷òî äëÿ G è H ñóùåñòâóþò D1-, D2-äèñòàíöèîí-
íûå ìàãè÷åñêèå ðàçìåòêè ñ ðàâíûìè äèñòàíöèîííûìè ìàãè÷åñêèìè ïîñòîÿííûìè.
Èç åäèíñòâåííîñòè äèñòàíöèîííîé ìàãè÷åñêîé ïîñòîÿííîé äëÿ êàæäîãî îòäåëüíîãî
ãðàôà âûòåêàåò âåðíîñòü óòâåðæäåíèÿ ñëåäñòâèÿ. Ñëåäñòâèå 1 äîêàçàíî.
Ãðàôû G è H , ïðåäñòàâëåííûå íà ðèñ. 1, èìåþò ðàâíûå ñîîòâåòñòâóþùèå
äèñòàíöèîííûå ìàòðèöû AD1
è AD2
, ãäå D1 1� { }, D2 1 2� { , }:
A AD D1 2
0 1 1 1 1 0
1 0 1 1 0 1
1 1 0 0 1 1
1 1 0 0 1 1
1 0 1 1 0 1
0 1 1 1 1 0
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 115
Íåñëîæíî çàìåòèòü, ÷òî áèåêöèÿ f f u ii: ( ) � , i �1 6, ,� , ïîðîæäàåò D1-äèñòàí-
öèîííóþ ìàãè÷åñêóþ ðàçìåòêó ãðàôà G è D2-äèñòàíöèîííóþ ìàãè÷åñêóþ ðàçìåòêó
ãðàôà H . Äèñòàíöèîííàÿ ìàãè÷åñêàÿ ïîñòîÿííàÿ â êàæäîì èç ýòèõ ñëó÷àåâ ðàâíà 14.
Òàêèì îáðàçîì, G è H ÿâëÿþòñÿ ìàãè÷åñêèìè äèñòàíöèîííî-ïîäîáíûìè ãðàôàìè.
Ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû AD îáîçíà÷èì � � �1 2, , ,� n è íàçîâåì
äèñòàíöèîííûì ñïåêòðîì ãðàôà G. Äèñòàíöèîííûå ñïåêòðû äèñòàíöèîííî-ïî-
äîáíûõ ãðàôîâ ñîâïàäàþò, òàê êàê ïîäîáíûå ìàòðèöû èìåþò îäèíàêîâûå ñîá-
ñòâåííûå çíà÷åíèÿ ñ ó÷åòîì êðàòíîñòè [11]. Êàê óæå îòìå÷àëîñü, D-äèñòàíöèîí-
íàÿ ìàòðèöà ÿâëÿåòñÿ ñèììåòðè÷íîé ñ äåéñòâèòåëüíûìè ýëåìåíòàìè. Ñëåäîâà-
òåëüíî, AD — ýðìèòîâà ìàòðèöà è åå ñïåêòð ñîñòîèò òîëüêî èç äåéñòâèòåëüíûõ
÷èñåë � � �1 2, , ,� n . Èõ ìîæíî óïîðÿäî÷èòü, ïóñòü � � �1 2� � �� n .
Îòìåòèì, ÷òî êàæäàÿ ìàòðèöà AD , åñëè 0�D è A ED � , åñëè 0�D, ãðàôà G
ïîðÿäêà n, ÿâëÿåòñÿ ìàòðèöåé ñìåæíîñòè íåêîòîðîãî ãðàôà ïîðÿäêà n, êîòîðûé áó-
äåì îáîçíà÷àòü GD , è íàçûâàòü D-íàäãðàôîì ãðàôà G. Íåñëîæíî çàìåòèòü, ÷òî
ñïåêòðàëüíûé ðàäèóñ �( )AD ìàòðèöû AD óäîâëåòâîðÿåò íåðàâåíñòâàì
min| ( )| ( ) max| ( )|N u A N uD i D D i� �� , ãäå min è max áåðåòñÿ ïî âñåì i n�1 2, , ,� .
Òåîðåìà 3. Äëÿ êîýôôèöèåíòîâ õàðàêòåðèñòè÷åñêîãî ìíîãî÷ëåíà PAD
( )� �
� � � � �� �
�c c c c cn n n
n n0 1
1
2
2
1� � � ��... äèñòàíöèîííîé ìàòðèöû AD ãðàôà G
ïîðÿäêà n èìåþò ìåñòî òàêèå ñîîòíîøåíèÿ:
1) c0 1� ;
2) c1 0� , åñëè 0�D è c n1 � � , åñëè 0�D ;
3) � �c q2 , åñëè 0�D è c
n n
q2
1
2
�
�
�
( )
, åñëè 0�D, ãäå q — ÷èñëî ðåáåð â
D-íàäãðàôå GD ;
4) � �c t3 2 , åñëè 0�D è c n q n t Cn3
32� � � �( ) , åñëè 0�D, ãäå t — ÷èñëî òðå-
óãîëüíèêîâ â D-íàäãðàôå GD .
Äîêàçàòåëüñòâî. Ïóñòü 0�D, òîãäà D-äèñòàíöèîííàÿ ìàòðèöà AD ãðàôà G
ÿâëÿåòñÿ ìàòðèöåé ñìåæíîñòè âåðøèí D-íàäãðàôà GD . Äëÿ ìàòðèöû ñìåæíîñòè
âåðøèí ñîîòíîøåíèÿ (1)–(4) âåðíû [12].
Ïóñòü 0�D. Äëÿ ìàòðèöû AD ñ ñîáñòâåííûì çíà÷åíèåì � è ñóììàìè
E As D( ) åå ãëàâíûõ ìèíîðîâ ïîðÿäêà s ñïðàâåäëèâî òîæäåñòâî [11]:
P E A E A E AA
n
D
n
D
n
n DD
( ) ( ) ( ) ... ( )� � � �� � � � �� �
1
1
2
2 . (2)
Èç ðàçëîæåíèÿ (2) ñëåäóåò, ÷òî c0 1� .
Òàê êàê äèàãîíàëüíûå ýëåìåíòû ìàòðèöû AD ðàâíû åäèíèöå, òî E A nD1 ( ) � .
Òàêèì îáðàçîì, c n1 � � .
Ïóñòü � — ñîáñòâåííîå çíà÷åíèå ìàòðèöû A, ãäå A A ED� � — ìàòðèöà
ñìåæíîñòè âåðøèí D-íàäãðàôà GD . Õàðàêòåðèñòè÷åñêèå ìíîãî÷ëåíû A è AD
îïðåäåëÿþòñÿ ñîîòâåòñòâóþùèìè âûðàæåíèÿìè det( )�E A� è det( )�E AD� . Òàê
êàê det det( ) (( ) )� �E A E AD� � � � �1 0 , òî � �� �1. Ñëåäîâàòåëüíî,
P E A E A PA D AD
( ) det ( ) det ( ) ( )� � � �� � � � � . (3)
116 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
Ðèñ. 1. Ãðàô G — {1}-äèñòàíöèîííûé ìàãè÷åñêèé, ãðàô H — {1, 2}-äèñòàíöèîííûé ìàãè÷åñêèé
G: u6 u1
u2
u4 u3
u5
u6 u1
u2
u3
u5
u4
H:
Èç (3) ñ ó÷åòîì ñâîéñòâ ìàòðèöû ñìåæíîñòè A âûòåêàåò c E AD2 2� �( )
�
�
�
n n
q
( )1
2
, c E A n q n t CD n3 3
32� � � � � �( ) ( ) , ãäå q — ÷èñëî ðåáåð â GD , t —
÷èñëî òðåóãîëüíèêîâ â GD , Cn
3 — ÷èñëî êîìáèíàöèé èç n ýëåìåíòîâ ïî òðè.
Òåîðåìà äîêàçàíà.
Ñëåäñòâèå 1. Ïóñòü � ñîáñòâåííîå çíà÷åíèå äèñòàíöèîííîé ìàòðèöû AD ãðà-
ôà G, à � — ñîáñòâåííîå çíà÷åíèå ìàòðèöû ñìåæíîñòè âåðøèí A D-íàäãðàôà GD .
Òîãäà P PA AD
( ) ( )� �� , ãäå � �� , åñëè 0�D è � �� �1, åñëè 0�D.
Óòâåðæäåíèå ñëåäñòâèÿ âûòåêàåò èç äîêàçàòåëüñòâà òåîðåìû 3, à åãî ñïðà-
âåäëèâîñòü îñíîâûâàåòñÿ íà ñïðàâåäëèâîñòè ôîðìóëû (3) äëÿ ëþáîãî
D d� { }0 1 2, , , ,� .
Òåîðåìà 4. Åñëè � � �1 2� � �� n — äèñòàíöèîííûé ñïåêòð ãðàôà G ïî-
ðÿäêà n , òîãäà � �( )AD � 1 è � � �
1
2
2
2 2
1
� � � �
�
.. | ( )|n D i
i
n
N u , ãäå u V Gi � ( ) .
Äîêàçàòåëüñòâî. Ïóñòü D d� { }0 1 2, , , ,� è { , , , }u u un1 2 � — ìíîæåñòâî âåð-
øèí ãðàôà G ïîðÿäêà n. Òàê êàê ìàòðèöà A MD n� íåîòðèöàòåëüíàÿ, òî �( )AD —
åå ñîáñòâåííîå çíà÷åíèå [11]. Èñõîäÿ èç óñëîâèÿ äàííîé òåîðåìû, ïîëó÷èì
� �( )AD � 1.
Ñ ó÷åòîì ñèììåòðè÷íîñòè ìàòðèöû AD , êàæäûé bii -ûé ýëåìåíò ìàòðèöû
A b
D ii
2 � ( ) áóäåò ðàâåí a N uij
D
j
n
D i
�
�
1
| ( )| , ò. å. b N uii D i�| ( )| . Òàê êàê bii
i
n
�
1
ÿâëÿ-
åòñÿ ñëåäîì ìàòðèöû A
D
2 , òî | ( )|N uD i
i
n
i
i
n
� �
�
1
2
1
� . Òåîðåìà äîêàçàíà.
Ñëåäñòâèå 1. Äëÿ ( , )D r -ðåãóëÿðíîãî ãðàôà G ïîðÿäêà n èìååì
� � �
1
2
2
2 2� � � �... n nr, åñëè 0�D è � � �
1
2
2
2 2 1� � � � �... ( )n n r , åñëè 0�D.
Äîêàçàòåëüñòâî ñëåäñòâèÿ âûòåêàåò íåïîñðåäñòâåííî èç òåîðåìû 4.
Òåîðåìà 5. Åñëè G — ( , )D r -ðåãóëÿðíûé ãðàô, òîãäà �( )A rD � ïðè 0�D è
�( )A rD � �1 ïðè 0�D.
Äîêàçàòåëüñòâî. Ðàññìîòðèì ( , )D r -ðåãóëÿðíûé ãðàô G. Ïóñòü �( )AD —
ñïåêòðàëüíûé ðàäèóñ ìàòðèöû AD . Êðîìå òîãî, èìååì A MD n� , AD � 0 ,
|| ||A rD
� , êîãäà 0�D è || ||A rD
� �1, êîãäà 0�D. Èçâåñòíî, ÷òî
�( ) || ||A AD D�
[11]. Òàêèì îáðàçîì, �( )A rD � , åñëè 0�D è �( )A rD � �1, åñëè
0�D. Òåîðåìà äîêàçàíà.
Íà ðèñ. 1 ïðåäñòàâëåíû äâà ãðàôà: ({ }, )1 4 -ðåãóëÿðíûé ãðàô G è ({ , }, )1 2 4 -ðå-
ãóëÿðíûé ãðàô H ñ ïàðàìåòðîì r � 4. Íàéäåì ñîáñòâåííûå çíà÷åíèÿ D1 1� { }-,
D2 1 2� { , }-äèñòàíöèîííûõ ìàòðèö A AD D1 2
� ýòèõ ãðàôîâ. Õàðàêòåðèñòè÷åñêèé
ìíîãî÷ëåí A AD D1 2
� èìååò âèä � � �3 22 4( ) ( )� � . Îòñþäà �1 4� � r,
� � �2 3 4 0� � � è � �5 6 2� � � è ñïåêòðàëüíûé ðàäèóñ � � �r 4 äëÿ ìàòðèöû
A AD D1 2
� .
Òåîðåìà 6. Ïóñòü Gi — ñâÿçíûé ( , )D ri -ðåãóëÿðíûé ãðàô, ãäå i s�1 2, , ,� è
D Di
i
s
�
�
1
� . Åñëè G G G Gs� � � �1 2 � è Gi
i
s
�
��
1
� , òîãäà G ÿâëÿåòñÿ ( , )D r -ðåãó-
ëÿðíûì ãðàôîì è êðàòíîñòü ñîáñòâåííîãî çíà÷åíèÿ r ïðè 0�D è r �1 ïðè 0�D
äèñòàíöèîííîé ìàòðèöû AD ðàâíà s .
Äîêàçàòåëüñòâî. Ñíà÷àëà ðàññìîòðèì ñâÿçíûé ( , )D r -ðåãóëÿðíûé ãðàô G
ïîðÿäêà n, ò.å. G G� 1 è D D� 1.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 117
Ïðåäïîëîæèì, ÷òî 0�D è D-äèñòàíöèîííàÿ ìàòðèöà AD ãðàôà G åñòü ìàò-
ðèöà ñìåæíîñòè D-íàäãðàôà GD . Î÷åâèäíî, ÷òî GD — r-ðåãóëÿðíûé ñâÿçíûé
ãðàô. Èçâåñòíî, ÷òî r ïðåäñòàâëÿåò ñîáîé ñîáñòâåííîå çíà÷åíèå êðàòíîñòè îäèí
äëÿ ìàòðèöû ñìåæíîñòè r-ðåãóëÿðíîãî ãðàôà. Òàêèì îáðàçîì, õàðàêòåðèñòè÷åñ-
êèé ìíîãî÷ëåí ìàòðèöû AD ìîæíî ïðåäñòàâèòü â âèäå det( )�E AD� �
� � �( ) ( )� �r Pn 1 , ãäå � — ñîáñòâåííîå çíà÷åíèå AD , Pn�1 ( )� — ìíîãî÷ëåí
ñòåïåíè n�1 .
Ïóñòü 0�D è � � �1 2� � �� n — ñîáñòâåííûå çíà÷åíèÿ AD . Íà îñíîâàíèè
ñëåäñòâèÿ 1 èç òåîðåìû 3 è òåîðåì 4, 5 çàêëþ÷àåì, ÷òî � �i i� �1,
� � �( )A rD � � � � �1 11 1 è � �1 � �r A( ), ãäå � i — ñîáñòâåííûå çíà÷åíèÿ ìàò-
ðèöû ñìåæíîñòè âåðøèí A A ED� � r-ðåãóëÿðíîãî D-íàäãðàôà GD . Ñëåäîâà-
òåëüíî, êðàòíîñòü ñîáñòâåííîãî çíà÷åíèÿ r �1 ðàâíà åäèíèöå.  ýòîì ñëó÷àå õà-
ðàêòåðèñòè÷åñêèé ìíîãî÷ëåí ìàòðèöû AD çàïèøåì òàê:
det( ) ( ( )) ( )� � �E A r PD n� � � � �1 1 .
Ðàññìîòðèì ãðàô G ïîðÿäêà n ñ s êîìïîíåíòàìè ñâÿçíîñòè G G Gs1 2, , , ..� .
Ïóñòü Gi — ( , )D ri -ðåãóëÿðíûé ãðàô è | ( )|V G ti i� , ãäå i s�1 2, , ,� . Äèñòàíöèîí-
íàÿ ìàòðèöà AD ãðàôà G ÿâëÿåòñÿ áëî÷íî-äèàãîíàëüíîé, à ãðàô G — ( , )D r -ðåãó-
ëÿðíûì. Îáîçíà÷èì Aii áëîê, ñîîòâåòñòâóþùèé Di -äèñòàíöèîííîé ìàòðèöå ïîä-
ãðàôà Gi ãðàôà G. Òîãäà A AD ii
i
s
� �
�
1
. Äëÿ ìàòðèöû �E èñïîëüçóåì àíàëîãè÷-
íîå ïðåäñòàâëåíèå � �E Eii
i
s
� �
�
1
, ãäå ìàòðèöû Eii è Aii èìåþò îäèíàêîâûå
ïîðÿäêè. Òîãäà
det det det( ) (� � �E A E A ED ii
i
s
ii
i
s
� � � ��
�
�
�
�
�
�
�
�
� �
� �
1 1
ii ii
i
s
A�
�
�
�
�
�
�
�
�
�
1
) .
Åñëè 0�D, òî íà îñíîâàíèè ñâîéñòâ áëî÷íî-äèàãîíàëüíûõ ìàòðèö è ðåçóëü-
òàòîâ îòíîñèòåëüíî êðàòíîñòè êîðíÿ r �1 ìàòðèöû Aii ïîëó÷èì
det( ) ( ( )) ( ) ( ) ( )� � � � �E A r P P PD
s
t t ts
� � � � � � �1
1 21 1 1� ,
ãäå det( ) ( ) ( ( )) ( )� � � �E A P r Pii ii t ti i
� � � � � �1 1 , Pti
( )� — ìíîãî÷ëåí ñòåïåíè
ti , i s�1 2, , ,� .
Àíàëîãè÷íûé ðåçóëüòàò ïîëó÷àåòñÿ ïðè 0�D. Òåîðåìà äîêàçàíà.
ÑÂÎÉÑÒÂÀ ÄÈÑÒÀÍÖÈÎÍÍÎÉ ÌÀÃÈ×ÅÑÊÎÉ ÌÀÒÐÈÖÛ
Áóäåì ñ÷èòàòü, ÷òî ãðàô G ïîðÿäêà n èìååò âåðøèííóþ ðàçìåòêó f , ãäå
f V G n: ( ) { , , , }� 1 2 � — áèåêöèÿ. Ñîñòàâèì êâàäðàòíóþ ìàòðèöó A aij* ( )*� èç
äèñòàíöèîííîé ìàòðèöû A aD ij
D� ( ) ãðàôà G çàìåíîé êàæäîãî åäèíè÷íîãî ýëå-
ìåíòà aij
D íà ÷èñëî f u j( ) — ìåòêó âåðøèíû u V Gj � ( ). Òàêèì îáðàçîì, A*
îïðåäåëÿåòñÿ òàê:
a
a
f u a
ij
ij
D
j ij
D
* , ,
( ), .
�
�
�
�
�
�
�
0 0
1
åñëè
åñëè
Ìàòðèöó A* íàçûâàþò ìàòðèöåé ðàçìåòêè f [5]. Åñëè f — D-äèñòàíöèîííàÿ
ìàãè÷åñêàÿ ðàçìåòêà, òî A* áóäåì íàçûâàòü D-äèñòàíöèîííîé (èëè äèñòàíöèîí-
íîé) ìàãè÷åñêîé ìàòðèöåé. Àâòîðû ðàáîòû [5] ïðåäëàãàþò âûÿñíèòü, êàêèìè ñâîéñòâàìè
îáëàäàåò ìàòðèöà ðàçìåòêè äëÿ äèñòàíöèîííîãî ìàãè÷åñêîãî ãðàôà. Ïðîâåäåì èññëåäîâà-
118 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
íèå äëÿ áîëåå øèðîêîãî äèàïàçîíà ðàçìåòîê. Ïðèâåäåííûå íèæå òåîðåìû îïèñûâàþò
ñâîéñòâà äèñòàíöèîííûõ ìàãè÷åñêèõ ìàòðèö D-äèñòàíöèîííûõ ìàãè÷åñêèõ ãðàôîâ.
Òåîðåìà 7. Ïóñòü G — D-äèñòàíöèîííûé ìàãè÷åñêèé ãðàô ïîðÿäêà n è
� � �1 2
* * *, , .., n — ñîáñòâåííûå çíà÷åíèÿ äèñòàíöèîííîé ìàãè÷åñêîé ìàòðèöû A*, òîãäà
1) � i
i
n
*
�
�
1
0, åñëè 0�D è � i
i
n n n* ( )
�
�
�
1
1
2
, åñëè 0�D;
2) � i
i
n kn n* ( )2
1
1
2�
�
�
.
Äîêàçàòåëüñòâî. Ïóñòü G — D-äèñòàíöèîííûé ìàãè÷åñêèé ãðàô ïîðÿäêà n
è � � �1 2
* * *, , .., ,n — ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû A*.
1. Ïî îïðåäåëåíèþ ñëåä trA* ìàòðèöû A* ðàâåí ñóììå ýëåìåíòîâ ãëàâíîé äèàãî-
íàëè, ò.å. tr A a a ann* * * *� � � �11 22 � . Òàêæå èçâåñòíî, ÷òî tr A n* * * *� � � �� � �1 2 � [11].
Î÷åâèäíî, � � �1 2 0* * *...� � � �n , åñëè 0�D è � � �1 2
1
2
* * *...
( )
� � � �
�
n
n n
, åñëè
0�D.
2. Ïóñòü { , , , }u u un1 2 � — ìíîæåñòâî âåðøèí ãðàôà G, èìåþùåãî D-äèñòàí-
öèîííóþ ìàãè÷åñêóþ ðàçìåòêó f ñ äèñòàíöèîííîé ìàãè÷åñêîé ïîñòîÿííîé k è
D d� { }0 1 2, , , ,� . Ó÷èòûâàÿ, ÷òî AD — ñèììåòðè÷íàÿ ìàòðèöà, äëÿ ìàòðèöû
A cij* ( )2 � ïîëó÷èì ñëåäóþùèå äèàãîíàëüíûå ýëåìåíòû:
c f u a kf uj
j
n
11 1 1
1
1� �
�
( ) ( )* , c f u a kf uj
j
n
22 2 2
1
2� �
�
( ) ( )* , … ,
c f u a kf unn n n j
j
n
n� �
�
( ) ( )*
1
.
Íàéäåì ñëåä ìàòðèöû A*2: tr A c c c
kn n
nn* ...
( )2
11 22
1
2
� � �
�
. Èçâåñòíî,
÷òî tr A k
i
i
n
k
* *�
�
�
1
[11], ñëåäîâàòåëüíî, � i
i
n kn n* ( )2
1
1
2�
�
�
. Òåîðåìà äîêàçàíà.
Òåîðåìà 8. Åñëè ãðàô G äîïóñêàåò D-äèñòàíöèîííóþ ìàãè÷åñêóþ ðàçìåòêó
ñ ìàãè÷åñêîé ïîñòîÿííîé k, òî ÷èñëî k ÿâëÿåòñÿ ñîáñòâåííûì çíà÷åíèåì äèñòàí-
öèîííîé ìàãè÷åñêîé ìàòðèöû A* è �( *)A k� .
Äîêàçàòåëüñòâî. Ñòðî÷íûå ñóììû äëÿ íåîòðèöàòåëüíîé ìàòðèöû A* ïîñòîÿííûå
è ðàâíû k. Òàêèì îáðàçîì, || *||A k
� , ãäå || *||A
— ìàêñèìàëüíàÿ ñòðî÷íàÿ íîðìà.
Èçâåñòíî, ÷òî �( *) || *||A A�
è �( *)A — ñîáñòâåííîå çíà÷åíèå A* [11]. Ñëåäîâàòåëü-
íî, k ÿâëÿåòñÿ ñîáñòâåííûì çíà÷åíèåì ìàòðèöû A* è �( *)A k� . Òåîðåìà äîêàçàíà.
Çàìåòèì, ÷òî äëÿ D-äèñòàíöèîííîãî ìàãè÷åñêîãî ãðàôà G c ìàòðèöåé ñìåæíîñ-
òè A, äèñòàíöèîííîé ìàòðèöåé AD è äèñòàíöèîííîé ìàãè÷åñêîé ìàòðèöåé A*
âûïîëíÿåòñÿ íåðàâåíñòâî � � � � �� � �( ) ( ) ( *)A A A kD , ãäå �( )A , �( )AD ,
�( *)A — ñïåêòðàëüíûå ðàäèóñû ñîîòâåòñòâóþùèõ ìàòðèö, k — ìàãè÷åñêàÿ ïîñòîÿííàÿ.
ÇÀÊËÞ×ÅÍÈÅ
 äàííîé ðàáîòå ïîëó÷åí ñïîñîá ïîðîæäåíèÿ ðàçëè÷íûõ ìàãè÷åñêèõ äèñòàí-
öèîííî-ïîäîáíûõ ãðàôîâ îäèíàêîâîãî ïîðÿäêà èç çàäàííîãî D-äèñòàíöèîííî-
ãî ìàãè÷åñêîãî ãðàôà òîãî æå ïîðÿäêà. Òàêæå ðàññìîòðåíû âîïðîñû, ñâÿçàí-
íûå ñî ñïåêòðàëüíûìè ñâîéñòâàìè ìàòðèö, èñïîëüçóåìûõ ïðè ìàòðè÷íûõ
ïðåäñòàâëåíèÿõ D-äèñòàíöèîííûõ ìàãè÷åñêèõ ãðàôîâ.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 119
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Gallian J.A. A dynamic survey of graph labeling. The Electronic Journal of Combinatorics. 2017.
DS6: Dec 22. 432 p.
2. Miller M., Rodger C., Simanjuntak R. Distance magic labelings of graphs. Australasian Journal of
Combinatorics. 2003. Vol. 28. P. 305–315.
3. Vilfred V. Sigma labelled graphs and circulant graphs. Ph.D. Thesis, Uniersity of Kerala, India,
March 1994.
4. Beena S. On � and
� labelled graphs. Discrete Mathematics. 2009. Vol. 309. P. 1783–1787.
5. Arumugam S., Froncek D., Kamatchi N. Distance magic graphs — a survey. Journal of the
Indonesian Mathematical Society. Special Edition. 2011. P. 11–26.
6. O’Neal A., Slater P. An introduction to distance D magic graphs. Journal of the Indonesian
Mathematical Society. Special Edition. 2011. P. 89–107.
7. Anholcer M., Cichacz S., Peterin I. Spectra of graphs and closed distance magic labelings. Discrete
Mathematics. 2016. Vol. 339. P. 1915–1923.
8. Arumugam S., Kamatchi N. On the uniqueness of D-vertex magic constant. Discussiones
Mathematicae Graph Theory. 2014. Vol. 34. P. 279–286.
9. Donets G. A. Solution of the safe problem on (0, 1)-matrices. Cybernetics and Systems Analysis.
2002. Vol. 38, N 1. P. 83–88.
10. Öâåòêîâè÷ Ä., Äóá Ì., Çàõñ Õ. Ñïåêòðû ãðàôîâ. Òåîðèÿ è ïðèìåíåíèå. Êèåâ: Íàóê. äóìêà,
1984. 384 ñ.
11. Õîðí Ð., Äæîíñîí ×. Ìàòðè÷íûé àíàëèç. Ìîñêâà: Ìèð, 1989. 655 ñ.
12. Biggs N. Algebraic graph theory. Second edition. New York: Cambridge University Press, 1993.
205 p.
Íàä³éøëà äî ðåäàêö³¿ 03.10.2018
Ì.Ô. Ñåìåíþòà, Â.À. Øóëüã³í
ÌÀÒÐÈÖ², ÀÑÎÖ²ÉÎÂÀͲ Ç D-ÄÈÑÒÀÍÖ²ÉÍÈÌÈ ÌÀò×ÍÈÌÈ ÃÐÀÔÀÌÈ,
ÒÀ ¯ÕͲ ÂËÀÑÒÈÂÎÑÒ²
Àíîòàö³ÿ. Ðîçãëÿíóòî ìàòðèö³, àñîö³éîâàí³ ç D-äèñòàíö³éíèìè ìàã³÷íèìè
ãðàôàìè. Îòðèìàíî ðåçóëüòàòè ùîäî ñïåêòðàëüíèõ âëàñòèâîñòåé öèõ ìàò-
ðèöü. Äîâåäåíî, ùî â òîìó ðàç³, ÿêùî äâà ãðàôè G ³ H îäíàêîâîãî ïîðÿäêó
ìàþòü ïîä³áí³ äèñòàíö³éí³ ìàòðèö³ AD1
³ AD2
â³äïîâ³äíî, òî ãðàô G º
D1-äèñòàíö³éíèì ìàã³÷íèì òîä³ é ò³ëüêè òîä³, êîëè H áóäå D2-äèñòàíö³éíèì
ìàã³÷íèì ãðàôîì. Ãðàôè G ³ H íàçâàíî ìàã³÷íèìè äèñòàíö³éíî-ïîä³áíèìè
³ äîâåäåíî, ùî ¿õí³ äèñòàíö³éí³ ìàã³÷í³ ñòàë³ çá³ãàþòüñÿ.
Êëþ÷îâ³ ñëîâà: D-îê³ë, D-äèñòàíö³éíà ìàã³÷íà ðîçì³òêà, D-äèñòàíö³éíà
ìàòðèöÿ, ìàòðèöÿ ðîçì³òêè, D-äèñòàíö³éíà ìàã³÷íà ìàòðèöÿ.
Ì. Semeniuta, V. Shulhin
MATRICES ASSOCIATED WITH D-DISTANCE MAGIC GRAPHS AND THEIR PROPERTIES
Abstract. Matrices associated with D-distance magic graphs are considered in
the paper. Results regarding the spectral properties of these matrices have been
obtained. It has been proved that if two graphs G and H of the same order have
similar distance matrices AD1
and AD2
respectively, then graph G is D1-distance
magic if and only if H is a D2-distance magic graph. Graphs G and H are
called magic distance-similar and their distance magic constants have been
proved to coincide.
Keywords: D-neighborhood, D-distance magic labeling, D-distance matrix,
matrix of labeling, D-distance magic matrix.
Ñåìåíþòà Ìàðèíà Ôðîëîâíà,
êàíäèäàò ôèç.-ìàò. íàóê, äîöåíò êàôåäðû Ëåòíîé àêàäåìèè Íàöèîíàëüíîãî àâèàöèîííîãî
óíèâåðñèòåòà, Êðîïèâíèöêèé, e-mail: marina_semenyuta@ukr.net.
Øóëüãèí Âàëåðèé Àíàòîëüåâè÷,
êàíäèäàò òåõí. íàóê, äîöåíò êàôåäðû Ëåòíîé àêàäåìèè Íàöèîíàëüíîãî àâèàöèîííîãî
óíèâåðñèòåòà, Êðîïèâíèöêèé, e-mail: vashulgin@ukr.net.
120 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
|
| id | nasplib_isofts_kiev_ua-123456789-180874 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T18:54:29Z |
| publishDate | 2019 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Семенюта, М.Ф. Шульгин, В.А. 2021-10-23T16:45:40Z 2021-10-23T16:45:40Z 2019 Матрицы, ассоциированные с D-дистанционными магическими графами, и их свойств / М.Ф. Семенюта, В.А. Шульгин // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 112-120. — Бібліогр.: назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/180874 519.1:512.643 Рассмотрены матрицы, ассоциированные с D-дистанционными магическими графами. Получены результаты относительно спектральных свойств этих матриц. Доказано, что если два графа G и H одинакового порядка имеют подобные дистанционные матрицы AD₁ и AD₂ соответственно, то граф G является D₁-дистанционным магическим тогда и только тогда, когда H будет D₂-дистанционным магическим графом. Графы G и H названы магическими дистанционно-подобными и доказано, что их дистанционные магические постоянные совпадают. Розглянуто матриці, асоційовані з D-дистанційними магічними графами. Отримано результати щодо спектральних властивостей цих матриць. Доведено, що в тому разі, якщо два графи G і H однакового порядку мають подібні дистанційні матриці AD₁ і AD₂ відповідно, то граф G є D₁-дистанційним магічним тоді й тільки тоді, коли H буде D₂-дистанційним магічним графом. Графи G і H названо магічними дистанційно-подібними і доведено, що їхні дистанційні магічні сталі збігаються Matrices associated with D-distance magic graphs are considered in the paper. Results regarding the spectral properties of these matrices have been obtained. It has been proved that if two graphs G and H of the same order have similar distance matrices AD₁ and AD₂ respectively, then graph G is D₁-distance magic if and only if H is a D₂-distance magic graph. Graphs G and H are called magic distance-similar and their distance magic constants have been proved to coincide. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Матрицы, ассоциированные с D-дистанционными магическими графами, и их свойства Матриці, асоційовані з D-дистанційними магічними графами та їхні властивості Matrices associated with D-distance magic graphs and their properties Article published earlier |
| spellingShingle | Матрицы, ассоциированные с D-дистанционными магическими графами, и их свойства Семенюта, М.Ф. Шульгин, В.А. Системний аналіз |
| title | Матрицы, ассоциированные с D-дистанционными магическими графами, и их свойства |
| title_alt | Матриці, асоційовані з D-дистанційними магічними графами та їхні властивості Matrices associated with D-distance magic graphs and their properties |
| title_full | Матрицы, ассоциированные с D-дистанционными магическими графами, и их свойства |
| title_fullStr | Матрицы, ассоциированные с D-дистанционными магическими графами, и их свойства |
| title_full_unstemmed | Матрицы, ассоциированные с D-дистанционными магическими графами, и их свойства |
| title_short | Матрицы, ассоциированные с D-дистанционными магическими графами, и их свойства |
| title_sort | матрицы, ассоциированные с d-дистанционными магическими графами, и их свойства |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/180874 |
| work_keys_str_mv | AT semenûtamf matricyassociirovannyesddistancionnymimagičeskimigrafamiiihsvoistva AT šulʹginva matricyassociirovannyesddistancionnymimagičeskimigrafamiiihsvoistva AT semenûtamf matricíasocíiovanízddistancíinimimagíčnimigrafamitaíhnívlastivostí AT šulʹginva matricíasocíiovanízddistancíinimimagíčnimigrafamitaíhnívlastivostí AT semenûtamf matricesassociatedwithddistancemagicgraphsandtheirproperties AT šulʹginva matricesassociatedwithddistancemagicgraphsandtheirproperties |