Метод сортування покривних дерев
DOI:
https://doi.org/10.35681/1560-9189.2026.28.1.358849Ключові слова:
експертне оцінювання, матриця парних порівнянь, покривне дерево, діаметр графа, код ПрюфераАнотація
Статтю присвячено розробці методу сортування покривних дерев за діаметром. Покривні дерева широко застосовуються в теорії підтримки прийняття рішень, зокрема для отримання найбільш повної інформації з матриць експертних парних порівнянь. Метод дозволяє, за необхідності, без суттєвої втрати інформації знизити трудомісткість комбінаторного перебору базисних множин парних порівнянь під час обчислення відносних ваг альтернатив. Запропонований метод базується на певних когнітивних особливостях процесу експертного оцінювання множини альтернатив і використовує бієктивну відповідність між покривними деревами та кодами Прюфера.
Посилання
Cayley A. A theorem on trees. The Quarterly Journal of Mathematics. 1889. Vol. 23. pp. 376–378. https://doi.org/10.1017/CBO9780511703799.010
Chaiken S., Kleitman D. Matrix Tree Theorems. Journal of Combinatorial Theory, Series A. 1978. Vol. 24, No 3. pp. 377–381. https://doi.org/10.1016/0097-3165(78)90067-5
Bozoki S., Tsyganok V. The (logarithmic) least squares optimality of the arithmetic (geometric) mean of weight vectors calculated from all spanning trees for incomplete additive (multiplicative) pairwise comparison matrices. International Journal of General Systems. 2019. Vol. 48, No 4. pp. 362–381. https://doi.org/10.1080/03081079.2019.1585432
Nikolaieva K., Koybichuk V. Diskretny analiz. Grafy ta yikh zastosuvannya v ekonomitsi. Navchalny posibnyk. Sumy: UABS NBU, 2007.
Totsenko V. Metody ta systemy pidtrymky pryniattya rishen. Kyiv: Naukova dumka, 2002.
Tsyganok V. Kombinatorny algorytm parnykh porivnian’ zi zvorotnum zv’yazkom z ekspertom. Reyestratsia, zberigannya i obrobka danykh. 2000. Vol. 2, No 2. pp. 92–102.
Tsyganok V. Investigation of the aggregation effectiveness of expert estimates obtained by the pairwise comparison method. Mathematical and Computer Modelling. 2010. Vol. 52, No 3–4. pp. 538–544. https://doi.org/10.1016/j.mcm.2010.03.052
Kadenko S., Tsyganok V., Szadoczki Z., Bozoki S. An update on combinatorial method for aggregation of expert judgments in AHP. Production. 2021. Vol. 31. pp. 1–17. https://doi.org/10.1590/0103-6513.20210045
Prufer H. Neuer Beweis eines Satzes uber Permutationen. Archiv der Mathematik und Physik. 1918. Vol. 27. pp. 742–744.
Deo N., Micikevicius P. Prufer-like codes for labeled trees. Congressus Numerantium. 2001. Vol. 151. pp. 65–73.
Gottlieb J., Julstrom B.A., Raidl G.R., Rothlauf F. Prufer Numbers: A Poor Representation of Spanning Trees for Evolutionary Search. GECCO’01: Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation. 2001. pp. 343–350.
Wang X., Wang L., Wu Y. An Optimal Algorithm for Prufer Codes. Journal of Software Engineering and Applications. 2009. Vol. 2. pp. 111–115. https://doi.org/10.4236/jsea.2009.22016
Siraj S., Mikhailov L., Keane J. Enumerating all spanning trees for pairwise comparisons. Computers & Operations Research. 2012. Vol. 39, No 2. pp. 191–199. https://doi.org/10.1016/j.cor.2011.03.010
Siraj S., Mikhailov L., Keane J. Corrigendum to "Enumerating all spanning trees for pairwise comparisons" [Computers & Operations Research, 39(2), 191–199]. Computers & Operations Research. 2012. Vol. 39, No 9. P. 2265. https://doi.org/10.1016/j.cor.2011.11.010
Lundy M., Siraj S., Greco S. The mathematical equivalence of the "spanning tree" and row geometric mean preference vectors and its implications for preference analysis. European Journal of Operational Research. 2017. Vol. 257, No 1. pp. 197–208. https://doi.org/10.1016/j.ejor.2016.07.042
Tsyganok V. Metod obchyslennya vag alternatyv na osnovi rezultativ parnykh porivnyan’, provedenykh grupoyu ekspertiv. Reyestratsia, zberigannya i obrobka danykh. 2008. Vol. 10, No 2. pp. 121–127.
Tsyganok V. Elements of Combinatorial Approach in Determining the Consistency Spectral Coefficient of Experts’ Pairwise Comparisons / Data Recording, Storage & Processing - Vol. 14, No 2, 2012. pp. 98–105. https://doi.org/10.35681/1560-9189.2012.14.2.105056
Tsyganok V., Royik P. Metod vyznachennya ta pidvyshchennya uzgodzhenosti ekspertnykh otsinok pry pidtrymtsi grupovykh rishen’. Systemni doslidzhennya ta informatsiini technologii. 2018. No 3. pp. 110–121. https://doi.org/10.20535/SRIT.2308-8893.2018.3.10
Szadoczki Z., Bozoki S., Tekile H. Filling in pattern designs for incomplete pairwise comparison matrices: (quasi-)regular graphs with minimal diameter. Omega. 2022. Vol. 107. Article 102557. https://doi.org/10.1016/j.omega.2021.102557
Szadoczki Z., Bozoki S., Juhasz P., Kadenko S.V., Tsyganok V. Incomplete pairwise comparison matrices based on graphs with average degree approximately 3. Annals of Operations Research. 2023. Vol. 326. pp. 783–807. https://doi.org/10.1007/s10479-022-04819-9
