0000114

.ryznaczoay wszystkie bezy minimalne grafu G* f( x⁷) . (*₁*x₄)(x₁4x₇)(x₂4x₄)(x₂4x₃)(x₂*x₅)(x₂*x₆) . .(x₃«x₄)(^x44x₀)(x₅4^x6)(x_e«^x7) -

■ (^X2^4X3^X4^X5^X6^,<X4^4X1^X3^X7⁾<^X7^4X1^X6^)(X5^4X6⁾ "

• (*2^X4^4X3^X4^X5^X6 ^{4 X}1^X2^X3^X7 ^{4 X}1^X3^X4^X5^X6^X7^ *

•(^X5^X7 ^{4    4 x}6^X7 ^{4 x}l^x6^ "

" ^X2^X4^X5^X7    *    ^X3^X4^X5^X6^X7    ^4    X1*2^X3^X5^X7    ^{4 X}1^X3*A*£^6^X7    ⁴

^{4 X}2^X4^X6^X7    ^4    x3“XV7    ^4    X1^X2^X3^XC ^4    XlV>*ś^<6^X7 ⁴

^{4 x}i^x2^X4^x6    ^4    xl^x3^X4^x5^X6    ^4    xł^x^*6^X7    ^{4 X}1^X3V*5^X6^X7

Makayoalnc zbiory wewnętrzni* *t*bllno grafu c" *q następujęce (1.3.61. [l.l] . {4.6j , {1.3.5} . (4.5} . {3.5.7} . {2.7} Zatea nę trzy różno najliczniejezo •kojorzenln grafu C

^•{1,3,6). U₂ - {1.3.5}.    - {2.5,7}

przedstawiono no rye.14.5.

O

Zolotq notody przedstawionej w przykładzie 14.i jest wyznaczenie wozyotkich nojliczniejozych okojarzoń (przydziałów). Wprowadzając dodatkowo krytorla nożna wśród nich wybrać skojorzonlo optynolne. Wodę notody joot pracochłonny procoo przokcztałcanlo wyrażonla boolowoklogo do postaci nfa.

Ola dużej llcznoóci zbiorów A 1 O wygodnloj Joet stonować algorytm wyznaczania najllcznioJozogo okojarzonlo [14] oparty na motodzio wyznaczanlo przepływu naksynalnego w sieci skioro-wonoj S ■ < C* {o}, {h}> . Sieć S tworzymy dla grafu G w następujący sposóbt

Krawędzie utU zastępujemy łukanl skierowanymi od zbioru A do zbioru B. Dodajemy dwa wierzchołki s-źródło 1 t-odpływ. źródło s łęczymy łukeal z wierzchołkami x£A. natomiast wierzchołki xCO łęczymy łukami z odpływom t. W ten sposób otrzymu-

0* •	<w; u: p*>.
|A|	dla x ■ s
0	dla x / s.t
lo|	dla x ■ t
i	dla <x,y> i x • i
oo	dla <x,y> i x c A

o(x)

h(x.y)

Ola grafu możliwości przydziału z przykładu 14.1 (rys.14.3), oloć S jest przedstawiona na rys.14.6, wartości h(x.y) przed stawiono w prootokętach.

227