Раскраски

Докажите утверждение о бесполезных вершинах.

Задачи

 

7.1. Найдите наибольшее паросочетание и наименьшее реберное покрытие для графов ,

, .

 

7.2. Сколько наибольших паросочетаний имеется в графе 1) ; 2) ; 3) ; 4) ;

5); 6) ?

 

7.3. Является ли показанное на рисунке паросочетание наибольшим?

 

 

7.4. Сколько имеется максимальных (не имеющих продолжения) чередующихся путей

относительно показанного на рисунке паросочетания, начинающихся в вершине а?

Есть ли среди них увеличивающий путь? Есть ли вообще для данного паросочетания

увеличивающий путь?

 

7.5. Проверьте, являются ли данные паросочетания наибольшими. Найдите в этих графах

наименьшие реберные покрытия и наибольшие независимые множества.