0000112

Rozdział 14

PROBLEMY PRZYDZIAŁ&W 14.1. Określenia podstawowe

Woźny pod uwagę skończony zbiór X • A^B oraz zbiory 2^A i 2^B. Przydziale* w sensie ogólny* *olemy nazywać dowolno funkcję ^f/, * A— 2° lub f_Q i B—*-2^m. Przydziałem dopuszczalnym nazywany funkcję f_A lub f₀ społniajoco określone warunki (ograniczeni*). Szczególno rolę w zastosowaniach praktycznych odgrywa-JO takio przydziały, dla których wartościami funkcji f_A *o ele-*onty zbioru B, (f : A—B), np. A - zbiór obywoteli, B - zbiór mieszkań. Wśród tych przydziałów wyróżnia się przydzioły wza -jsmnie Jednoznaczne (funkcja f no funkcję odwrotno f"¹)

• f i A— B ;    f"¹ i B -—A

Dożoli no zbiorze dopuezczalnych przydziałów {fjJ określimy funkcjonał £ * {^fi) —to «oiomy mówić o problemie wyboru przydziału optymalnego, eketremallzujocogo wartość funkcjono -łu Problem wyznaczanlo przydziału dopuszczalnego i optymalnego nożna oforaułowoć w Języku teorii grofów i sieci oraz wykorzystać metody grafów i sieci do Jego rozwlozanla.

Ograniczymy się do rozważania tylko przydzlełów_vwzajemnie Jednoznacznych.

Skojarzeniem grafu G ■ <X,U,P> noży -wa*y podgraf częściowy bez pętli i wierzchołków izolowanych d • <xi Ul P‘> o zerowej macierzy przyległoścl gałęzi ( B(^G'J • -0).

Zauważmy, że podzbiór gałęzi U*C U określa Jednoznacznie skojarzenie c'.

No ryo.14.1 Joot przodatowlony przykłodowy grof G oroz jedno z Jogo okojorzoń, okroił łono podzbiorom gałęzi U¹ oznoczo-nych grubymi'liniami. Zbiór X¹ oznaczono podwójnymi kółkomi.

Ryt.14.1

Llcznolcl* akojorzonio nazywany ilość gałęzi uCU¹ tworzęcych okojorzonie. Licznoóć okojarzenia na ryo.14.1 Jaot równa 4. Oznaczmy U(G) zbiór wozyatkich podzbiorów u‘cu tworzących okojarzonia grafu G ■ <X,U,P> .

Utożaeoimy okojorzonie G¹ ■ <,X'. U¹, P’> z podzbiorem u’.

Skojorzonia ■okoymolno U_-ox€ określono jaot nootępujęco

u.._xeU(c) «|{u’€U, u_||Xcu'au_||X t u')| - o

Skojarzenia nejlicznieJozeU^T£U(&:

I U^x | •    |u’|

U'cU(G)

Liczba akojerzenla grafu T(G)

X(C) - |U*|

Liczba akojerzenla grafu z rye.14.1 Joot równo 6. Skojorzonia U^{1 n}®-tym ryaunku joot mokoyrolno ole nie najllcznlajoza. Skoja -rzanle najlicznlejoze togo grofu Jaot przedotowione na ryo.14.2. Graf może alać wiola różnych okojorzeń mokoymolnych i nojllcz-niejozych.

223