Preview

Чебышевский сборник

Расширенный поиск

Матрица относительной лесной доступности ориентированного пути и ориентированного цикла

https://doi.org/10.22405/2226-8383-2021-22-2-183-201

Полный текст:

Аннотация

В статье рассмотрены свойства матрицы относительной лесной доступности ориентированного цикла и ориентированного пути.
Во введении представлена история вопроса, дан обзор основных идей и результатов работы.
Во втором разделе собраны основные понятия теории графов, и дано ”графовое“ представление матрицы относительной лесной доступности орграфа Γ: F =
(((𝑓𝑖𝑗))𝑛×𝑛)/𝑓 , 𝑖, 𝑗 = 1 . . . 𝑛, где 𝑓𝑖𝑗 – количество остовных сходящихся корневых лесов орграфа Γ, в которых вершины 𝑖 и 𝑗 принадлежат одному дереву, сходящемуся к 𝑗, а 𝑓 – общее количество остовных cходящихся корневых лесов орграфа Γ.
В третьем разделе рассмотрены вопросы построения и исследования матрицы относительной лесной доступности ориентированного пути 𝑃𝑛, 𝑛 ≥ 2. Рассмотрены примеры построения матрицы относительной лесной доступности ориентированного пути для малых значений 𝑛. Приведены иллюстрации ”графовой“ процедуры построения матрицы F. Доказано, что матрица относительной лесной доступности ориентированного пути 𝑃𝑛, 𝑛 ≥ 2, связана с последовательностью 1, 2, 4, 8, 16, ..., 2𝑛, ... степеней числа 2. Другими словами, элементы 𝑓𝑖𝑗 , формирующие матрицу, представляют собой элементы множества {1, 2, 22, ..., 2𝑛−1}, заполняющие столбцы матрицы: первый столбец состоит из последовательно убывающих чисел 2𝑛−1, ..., 2, 1; второй столбец, начинаясь с 0, содержит на втором месте (пересечение с главной диагональю) число 2𝑛−2, в то время как следующие элементы представляют собой последовательно убывающие числа 2𝑛−3, ..., 2, 1; третий столбец, содержащий нули на двух позициях, расположенных над главной диагональю, содержит на третьем месте (пересечение с главной диагональю) число 2𝑛−2, в то время как следующие элементы представляют собой последовательно убывающие числа 2𝑛−3, ..., 2, и т.д.
Величина 𝑓 равна 2𝑛−1.
В четвертом разделе аналогичные рассуждения проведены для матрицы относительной лесной доступности для ориентированного цикла 𝐶𝑛, 𝑛 ≥ 3.
В заключении подведены итоги работы.

Об авторе

Батуль Мханна
Московский педагогический государственный университет
Россия

аспирант



Список литературы

1. Деза Е.И., Мханна Б. О специальных свойствах некоторых квазиметрик // Чебышевский сборник. 2020. Том 21, выпуск 1. С. 145 – 164.

2. Чеботарев П.Ю., Агаев Р.П. Матричная теорема о лесах и лапласовские матрицы орграфов. – М.: LAP LAMBERT Academic publishing, 2011.

3. Basin S.L. The appearance of Fibonacci numbers and the Q matrix in electrical network theory // Math. Magazine. 1963. Vol. 36. P. 84 – 97.

4. Boesch F. T., Prodinger H. Spanning tree formulas and Chebyshev polynomials // Graphs Combin. 1986. Vol. 2. P. 191 – 200.

5. Chaiken S. A combinatorial proof of the all minors matrix tree theorem // SIAM J. Algebraic Discrete Methods. 1982. Vol. 3. P. 319 – 329.

6. Chebotarev P. Y., Shamis E. V. The matrix-forest theorem and measuring relations in small social groups // Automat. Remote Control. 1997. Vol. 58. P. 1505 – 1514.

7. Chebotarev P. Spanning forests and the golden ratio // Discrete Applied Mathematics. 2008. Vol. 156. P. 813 – 821.

8. Chebotarev P., Deza E. Hitting time quasi-metric and its forest representation // Optimization Letters. 2020. Vol. 14. P. 291 – 307.

9. Chebotarev P., Agaev R. Forest matrices around the Laplacian matrix // Linear Algebra and its Applications. 2002. Vol. 356. P. 253 – 274.

10. Chebotarev P.Y., Shamis E.V. On proximity measures for graph vertices // Automation and Remote Control. 1998. Vol. 59. P. 1443 – 1459.

11. Hilton A. J. W. Spanning trees and Fibonacci and Lucas numbers // Fibonacci Quart. 1974. Vol. 12. P. 259 – 262.

12. Koshy T. Fibonacci and Lucas Numbers // Wiley-Interscience. New York. 2001.

13. Merris R. Doubly stochastic graph matrices // Publikacije Elektrotehnickog Fakulteta Univerzitet U Beogradu. Serija. Matematika. 1997. Vol. 8. P. 64 – 71.

14. Merris R. Doubly stochastic graph matrices II // Linear and Multilinear Algebra. 1998. Vol. 45. P. 275 – 285.

15. Mowery V. O. Fibonacci numbers and Tchebycheff polynomials in ladder networks // IRE Trans. Circuit Theory. 1961. Vol. 8. P. 167 – 168.

16. Myers B. R. Number of spanning trees in a wheel // IEEE Trans. Circuit Theory. 1971. Vol. 18. P. 280 – 282.

17. Zhang X. D. A note on doubly stochastic graph matrices // Linear Algebra Appl. 2005. Vol. 407. P. 196 – 200.

18. Zhang X. D., Wu J. X. Doubly stochastic matrices of trees // Appl. Math. Lett. 2005. Vol. 18. P. 339 – 343.

19. Zhang Y., Yong X., Golin M.J. Chebyshev polynomials and spanning tree formulas for circulant and related graphs // Discrete Math. 2005. Vol. 298. P. 334 – 364.


Для цитирования:


Мханна Б. Матрица относительной лесной доступности ориентированного пути и ориентированного цикла. Чебышевский сборник. 2021;22(2):183-201. https://doi.org/10.22405/2226-8383-2021-22-2-183-201

For citation:


Mhanna B. Matrix of relative forest accessibility of the oriented path and the oriented cycle. Chebyshevskii Sbornik. 2021;22(2):183-201. (In Russ.) https://doi.org/10.22405/2226-8383-2021-22-2-183-201

Просмотров: 9


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)