ГРАФОВИЙ МАТРОЇД ТА АНАЛІЗ СПАНУЮЧИХ ДЕРЕВ У ГРАФІ
DOI:
https://doi.org/10.30890/2567-5273.2025-40-02-036Ключові слова:
граф, матроїд, остовне дерево, алгоритм Крускала, графовий матроїд, незалежні множини, комбінаторна оптимізаціяАнотація
У статті досліджено графовий матроїд як формальну структуру для моделювання процесу побудови остовного дерева в неорієнтованому графі. На основі аксіом матроїдної теорії продемонстровано, що множини ребер, які не утворюють циклів, утворюють систему незалеПосилання
Matoya, K., & Oki, T. (2020). Pfaffian pairs and parities: Counting on linear matroid intersection and parity problems. https://arxiv.org/abs/1912.00620
Oxley, J.G. (2006) Matroid Theory. Oxford: Oxford University Press. Available at: Oxford Academic (Accessed: 13 August 2025). https://academic.oup.com/book/34846
Wahlström, M. (2024). Representative set statements for delta-matroids and the Mader pp. 780–810. SIAM. Advance online publication. Available at: https://doi.org/10.1137/1.9781611977912
Koana, T. and Wahlström, M. (2025). Faster Algorithms on Linear Delta-Matroids. In: O. Beyersdorf, M. Pilipczuk, E. Pimentel, and N.K. Thắng, eds. 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics, vol. 327, article no. 62, pp. 62:1–62:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. Available at: https://drops.dagstuhl.de/storage/00lipics/lipics-vol327-stacs2025/LIPIcs.STACS.2025.62/LIPIcs.STACS.2025.62.pdf
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Available at: Internet Archive (Accessed: 13 August 2025). https://archive.org/details/introduction-to-algorithms-third-edition-2009
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2025 Автори
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
