Помогите разобраться с этой леммой. Она говорит, что паросочитание в графе является максимальным тогда и только тогда, когда не существует пополняющего пути(пути, в котором грани поочередно то содержаться в паросочитании, то нет, и при этом первая и последняя вершина графа не содержаться в паросочетании).
А как же, например, граф
, у которого, скажем, 6 вершин(1,2,3,4,5,6), 2 компоненты. 1 компонента будет сосостоять из пути {12, 23, 34}, а вторая - {56}. И, если сделаем паросочетание {12, 34} для него не существует пополняющего пути, но при этом он не является максимальным, к нему можно добавить грань и получить {12,34,56}. При этом нигде условия о связаности графа я не увидел.
16.01.2015, 20:05 
ом