je na 14,8 % . Bipartitivni graf
¶ Bipartitivni graf je graf čiji se čvorovi mogu podeliti na dva disjunktna podskupa tako da u grafu postoje samo grane između čvorova
podskupa tako da u grafu postoje samo grane između čvorova iz različitih podskupova. Na primer, slika niže prikazuje bipartitivni graf sa skupom čvorova koga čine dva disjunktna podskupa 1, 2 i 3, 4, 5, gde svaka grana grafa povezuju č vorove iz
podskupova . bipartitivni graf i u slučaju pozitivnog odgovora konstruisati razlaganje čvorova grafa u disjunktnu uniju. ( Prema primeru 6.22
čvorova grafa u disjunktnu uniju. ( Prema primeru 6.22 iz knjige, postoji tačno jedno ovakvo razlaganje za povezan bipartitivni graf G ) .
jasno je da razlazu graf G ( prema induktivnoj hipotezi ) . bipartitivan , jer razlaganja je jednoznačno .
studenata, uz uslov da niti jedan fakultet neće primiti više od dva studenta . bipartitivnog uparivanja ( zadatak 38 ), ali se ono ne može doslovce prepoznati, jer fakultet može biti u vezi sa viže studenata. Ali se
sa maksimalnim brojem grana. Ovaj zadatak se bavi jednim tipom optimalnog uparivanja . bipartitivni graf u kome V, U su disjunktni skupovi čvorova, E je skup grana koje povezuje neke čvorove iz V sa nekim čvorovima iz U.
skupovi čvorova, E je skup grana koje povezuje neke čvorove iz V sa nekim čvorovima iz U. Bipartitivno uparivanje S jeste optimalno = > u grafu G ne postoje alternirajući putevi za njega .