Минимальное вершинное покрытие графа.

[wintttr]

Как найти наименьшее вершинное покрытие графа?
Вроде бы, препод говорил, надо найти наибольшее паросочетание графа, а оно находится алгоритмом Куна, но везде в интернете написано, что он работает только для двудольных графов, а в задании графы не двудольные. (Да и сам этот алгоритм какой-то непонятный)

[sqribner48]

wintttr
А Вы в интернете посмотрите. Там по этой теме много чего написано.

[marie-la]

wintttr
А вы покажите ваш граф, может, там какие-то особенности, позволяющие легко отыскать покрытие

[hitler]

Тут есть https://algorithmica.org/ru/matching

[Sender]

wintttr в сообщении #1510321 писал(а):

надо найти наибольшее паросочетание графа, а оно находится алгоритмом Куна, но везде в интернете написано, что он работает только для двудольных графов, а в задании графы не двудольные

Есть алгоритмы для поиска наибольших паросочетаний в произвольном графе, например, алгоритм Эдмондса. Но нахождение наибольшего паросочетания, вообще говоря, не слишком поможет в поиске минимального вершинного покрытия.