ОБ ОДНОМ АЛГОРИТМЕ ПЕРЕЧИСЛЕНИЯ ПАРОСОЧЕТАНИЙ В ПРОИЗВОЛЬНОМ ГРАФЕ (2022)
Выпуск:
№ 9 (2022)
Предлагается алгоритм построения всех наибольших паросочетаний в произвольном связном графе, основанный на предварительном представлении графа специальной матрицей с последующей процедурой комбинаторного построения паросочетаний. Алгоритм использует способ кодирования элементов графа с помощью простых чисел. Тем самым, реализуется идея цифровизации графа. Такой подход позволяет работать с графом как с числовым объектом, не теряя взаимно однозначного соответствия с его геометрической структурой. Изложенный материал может быть использован как при решении конкретных задач теории графов, так и в учебном процессе.