0000119

Oczko no przecięciu trzeciego wiersze i trzecieJ■kolumny zostało "pokryte podwójnie". Eler.ont minieolny wśród niopokrytych oczek Jest równy i. Po odjęciu tej wortoóci od oczek niepokrytych i dodoniu do pokrytych podwójnie, otrzymujemy tablicę przedot owionę no rye.14.i2o. Nowo oczko dopuezczolne przedsta-wia tablica no rys.14.i2b (porównaj z ryt.13.9).

Rye.14.12

Stortujęc od ostatniego przydziału wyznaczamy znów nojllcznlej-ezy zbiór nowych niezaleinych oczek dopuozczalnych (ryt.14.13). Ilość ich Jeet równa r - 3. Oznacza to koniec realizacji pro -cedury. Koozt wyznaczonego przydziału wyliczamy z pierwotnej tablicy (rye.14.9). Oest on równy 6 (porównaj z przykładem 13.1).

m	I	1
	1
1		H

Rys.14.13

14.3.2. Przydział najliczniejszy o największym zyaku Przyjmujemy, tek Jak w punkcie 14.3

F(U* ) -ZZ k(u) ueu'

Noloży wyznaczyć toki U°€ U , żo

Mu⁰) • «•* f(u')

Funkcjo k i U -*5i no w ty« wypadku lntorpretację zyoku Jodnoo kowego, wynikającego przy określonym przydziale.

Przydział nojliczniejozy o mokeymolnym zyoku możno wyznaczyć zo pomocę algorytmu omówionego w poprzednim punkcio. W tym celu należy Jedynie zmionlć znak funkcji k no przeciwny.

14.4. Najliczniejoze przydziały, miniooKOwo .

3ako funkcję celu F przyjmuje elę funkcję neatępujęcę

F(U * ) - mox k(u)

ueU'

Należy wyznaczyć U°. taki żo

•

F(U°) - min F(U* )

U’€U

Wartości k(u) eę w tym wypadku Interpretowane Jako koozty wy -nikajęce z przyjęcia krawędzi u do przydziału najllczniejozego

Ryo.14.14

237