0000113

o

a

-o

o

a

o

a

o

a

o

Ryt.14.2

Przydział wzajemnie Jednoznaczny możemy okroólić Jako skojarzenie zwykłego grafu dwudzielnego C •    U. P) > które

napiszemy Joko c' • <^«O¹, u', P‘> (patrz ryo.14.3)

A

Rys.14.3

G • <AUB. U, P>

U - {l.2.3,4,5.6.7}

Taki graf dwudzielny będziemy nazywali grafem mol-1 i w o i c i przydziału, a każde Jego ekojerzenie przydziałem dopuazczalnym. Ole zastosowań praktycznych duże znaczcie maję przydziały nojliczniejeze (np. problem przydziału mieszkań b€ B obywotolom o G A, gdy możliwość przydziału mieez-kania z punktu widzenia przepieów jeot reprezentowana krawędzią grafu dwudzielnego, ryo.14.3). Pojawia elę zatem potrzeba metody wyznaczania skojarzeń nojlietnieJozyeh dla grofów dwudzielnych.

14.2. Motody wyznaczanie przydziałów najllcznlojuzych

Ważcy pod uwagę graf moźliwoócl przydziału G ■ <.A'-'0,U,P>. Niech B (C) » [^ij]_mKO *    ° • | U| będzie naclorzę blnnrnę

przyległoócl gołęzl.

Możeny utworzyć graf zwykły, sprzężony G*« <U_#U*!p^,,> , któ-rogo binarna moclorz przyległoócl wierzchołków R(C**) -B(C)

U

^R(Cł) “ [^rij]»*- ^{; r}U " ^b'

Problon wyznaczenia najliczniejszego ekojarzenio grafu G Jest równoważny probleaowi wyznaczenie najliczniejszego zbioru wew -nętrznie etobllnego grafu G*

«(C*) -I(G)

Przykład 14.1

Wyznaczymy przydział najliczniejszy dla grafu możliwoóci przydziału z rys.14.3.

1    2    3 4    5 6    7

B(C)

R(C*)

Craf oprzężony G* Jeat przedstawiony na rys.14.4

225