@article{Бенедиктович В. И.2021-10-06,
author = { Бенедиктович В. И.},
title = {Собственные значения, трассируемость и совершенное паросочетание графа},
year = {2021},
doi = {10.29235/1561-2430-2021-57-3-274-285},
publisher = {NP «NEICON»},
abstract = {Хорошо известно, что задача распознавания существования в графе совершенного паросочетания, как и задачи распознавания его гамильтоновости и трассируемости, является NP-полной. Совсем недавно были получены нижние оценки на размер и спектральный радиус графа, гарантирующие существование в нем совершенного паросочетания. Мы улучшаем эти оценки, во-первых, благодаря использованию имеющихся оценок на размер графа для существования в нем гамильтоновой цепи, во-вторых, благодаря нахождению новых нижних оценок на спектральный радиус графа, являющихся достаточными для наличия свойства трассируемости. Также приводится алгоритм распознавания существования в графе совершенного паросочетания, использующий понятие (κ,τ)-регулярного множества, который становится полиномиальным в классе графов с фиксированным цикломатическим числом.},
URL = {https://www.academjournals.by/publication/12780},
eprint = {https://www.academjournals.by/files/12746},
journal = {Известия Национальной академии наук Беларуси. Серия физико-математических наук},
}