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

Wyszukiwarka

Podobne podstrony:
184 Rozdział 14 Na podstawie schematu zastępczego oraz prawa Ohma i Kirchhoffa można zapisać następu
10720 rozdział 6 (14) 182 Podstawy marketingu śli wprowadzamy na rynek nowy towar, należy wcześniej
w określonym kontekście, biorąc pod uwagę okoliczności zawarcia umowy, a nawet uwzględniając inne um
0000047 2 Rozdział 6 CHROMATYKA GRAF&W 6.1. Pokrycia alnlaalne zbioru podzbloranl wetaleay pod u
0929DRUK00001764 352 ROZDZIAŁ yil, UST. 77 W celu wyznaczenia spólrzędnej q bierzemy pod uwagę trój
21471 Obraz3 (13) » Rozdział 14 ?Legitymizacja nierówności Należy zauważyć, że problematyka legitym
21550 zdj5 Prosty Problem Przydziału 4+5+11 + 14 = 34 F 4 6 3 34+1-4 =
Obraz3 (13) » Rozdział 14 ?Legitymizacja nierówności Należy zauważyć, że problematyka legitymizacji
img113 (8) Zadanie 14. Na podstawie danych zawartych w tabeli określ, które przedsiębiorstwo najszyb
Obraz3 3 Rozdział 14 ?Legitymizacja nierówności Należy zauważyć, że problematyka legitymizacji nier
390 391 (6) Rozdział 14 lBezrobocie14.1. Wprowadzenie Problematyka bezrobocia od dawna przyciąga uwa
262 (14) 262 Podstawy nawigacji morskiej Wartość dryfu określa algebraiczna różnica między KDw i KR:
ZAŁĄCZNIK 2 Strona 14 z 42 podstawie przeprowadzonych analiz określiłam optymalne stężenie gentamycy

więcej podobnych podstron