ITT0030 Diskreetne matemaatika II - eksamikonspekt
tipp. Täielik kooskõla on alati ka maksimumkooskõla.
Oletades, et graafis G leidub kooskõla M:
M-vahelduv on selline ahel P, kus servade järjestusse kuuluvad servad on kordamööda
,,kooskõla M" / ,,tavalise servade hulga E" elemendid.
M-laienev on selline ahel P,kus servade järjestuse esimene ning viimane tipp ei ole
kooskõlalised e. nad ei sisaldu kooskõla M koosseisus (mõne kooskõla M serva otstipuna).
Berge'i teoreem:
,,Kooskõla ME(G) on maksimumkooskõla vaid parajasti siis, kui graafis G ei leidu M-
laienevat ahelat".
(Berge'i teoreem on tegelikult triviaalne- kui ette kujutada näiteks 3-tipulist M-laienevat
ahelat kus kooskõlla on valitud keskmine serv, võiksime selle asemel kooskõlla valida hoopis
mõlemad ahela äärmised servad, saavutades niiviisi ühe võrra suurema kooskõla määra).
annaabi.ee 
