Teoria grafow i sieci - temat nr 7

[ Pobierz całość w formacie PDF ]
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 7:
Przydziały optymalne
1
PROBLEMY PRZYDZIAŁÓW
Skojarzenie grafu G
=
〈
W, U, P
〉
- podgraf częściowy
G
I
=
〈
W
I
, U
I
, P
I
〉
o nieprzyległych gałęziach, bez pętli i
wierzchołków izolowanych (tzn. 2
⋅
s(x) – r(x)
≠∅
dla każdego x).
Skojarzenie maksymalne
- U
I
nie jest podzbiorem właściwym
U
II
wyznaczającym skojarzenie.
Skojarzenie najliczniejsze
– skojarzenie, dla którego
U
jest
największe z możliwych.
Przydział
– skojarzenie grafu Königa (tzn. dwudzielnego grafu
zwykłego).
Skojarzenie pełne (doskonałe)
– każdy wierzchołek z G jest
incydentny przynajmniej z jednym u
∈
U
I
.
TWIERDZENIE (Hall’a)
W grafie dwudzielnym G (tzn. G =
〈
W
1
∪
W
2
,U,P
〉
, W
1
∩
W
2
=
∅
oraz W
1
, W
2
tworzą podgrafy puste w G), w którym |W
1
| = |W
2
|
istnieje skojarzenie pełne
⇔
dla każdego podzbioru wierzchołków
Z
⊂
W
1
istnieje przynajmniej |Z| wierzchołków w W
2
, które są
przyległe do któregoś wierzchołka z Z.
PRZYKŁAD 1 (tzw. problem kojarzenia małżeństw)
Jest
n
chłopców i
m
dziewcząt. Każdy z chłopców ocenia swoimi
własnymi kryteriami każdą z dziewcząt i po takiej weryfikacji
„widzi” ją jako potencjalną kandydatkę na żonę lub nie. Problem
polega na takim „przyporządkowaniu” dziewcząt do chłopców,
aby skojarzyć maksymalną liczbę par.
1
5
Niemożliwe skojarzenie pełne, bo
dla
Z
={1,3} istnieje tylko 1<|
Z
|
wierzchołek w W
2
, który jest
przyległ y do któregoś z
wierzchołków z
Z
.
- - -
- dodatkowa gałąź
spowodowałaby istnienie
skojarzenia pełnego.
2
6
n
3
7
m
4
8
W
1
W
2
I
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 7:
Przydziały optymalne
2
Metody wyznaczania skojarzenia (przydziału) najliczniejszego
Metoda baz minimalnych
– utworzyć G
*
(graf sprzężony grafu
G) oraz wyznaczyć w G
*
wszystkie bazy minimalne
(maksymalne zbiory wewnętrznie stabilne). Każdy
maksymalny podgraf pusty grafu G
*
odpowiada
maksymalnemu skojarzeniu w G.
PRZYKŁAD
Dla grafu G z Przykładu 1 mamy (łącznie z krawędzią przerywaną)
4,8
4,7
Maksymalny podgraf pusty
tworzą wierzchołki:
1,6 3,5 2,7 4,8
Gałęzie w G odpowiadające
wierzchołkom podgrafu
pustego w G
*
tworzą
skojarzenia maksymalne w G
(jest to dodatkowo skojarzenie
pełne).
1,6
3,5
2,8
1,5
2,6
2,7
Metoda maksymalnego przepływu
– zastępujemy graf G
grafem skierowanym G
I
następująco: dodajemy 2 wierzchołki
s
i
t
. Wierzchołek
s
łączymy łukami z elementami zbioru
W
1
,
a
wierzchołki zbioru W
2
z wierzchołkiem
t
. Krawędzie grafu G
zastępujemy łukami skierowanymi od W
1
do W
2
. Na bazie
digrafu G
I
tworzymy sieć S dla przepływów:
S =
〈
G
I
,
{
a
}
,
{
c
}〉
gdzie:

W
1
,
dla
x
=
s

1
,
x
,
y
:
x
=
s
∨
y
=
t


a
()

=
0
,
dla
x
≠
s
,
t
( )
c
x
,
y
=

∞
,
x
,
y
:
x
∈
W
∧
y
∈
W
−
W
,
dla
x
=
t
1
2
2
x
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 7:
Przydziały optymalne
75
PRZYKŁAD
Sieć S dla grafu G z Przykładu 1
przedstawiona jest poniżej.
1
∞
5
W sieci S znajdujemy
przepływ maksymalny.
Krawędzie odpowiadające
łukom, które będą miały
przepływ równy 1 tworzą
skojarzenie maksymalne w
G.
1
∞
1
1
2
∞
6
1
∞
S
1
1
∞
1
t
3
7
∞
∞
1
∞
4
8
Poprzednie dwie metody są mało efektywne.
Metoda
wyznaczania
zbioru
niezależnych
oczek
dopuszczalnych
1
5
5678
2
6
_
_
_
1
2
3
4
1
1
3
7
W
1
1
1
4
8
W
2
graf Königa
≡
siatka z oczkami dopuszczalnymi
-
zbiór niezależnych oczek dopuszczalnych –
zbiór oczek,
z których żadne dwa nie występują w tym samym wierszu ani
kolumnie (bo każde dwie gałęzie skojarzenia muszą być
nieprzyległe).
-
Przydział
≡
zbiór niezależnych oczek dopuszczalnych
oznaczonych
1
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 7:
Przydziały optymalne
76
Algorytm wyznaczania najliczniejszego zbioru
niezależnych oczek dopuszczalnych
1.
Wyznaczamy
dowolny
zbiór
niezależnych
oczek
dopuszczalnych – cechujemy je jedynkami.
2.
Cechujemy wszystkie wiersze bez 1 (np. „-„). Wybieramy
kolejno ocechowane wiersze i ich numerami cechujemy
nieocechowane
kolumny
odpowiadające
oczkom
dopuszczalnym.
3.
Wybieramy ocechowaną kolumnę i wiersz, w którym znajduje
się 1, cechujemy numerem kolumny. Postępowanie powtarzamy
dla ocechowanych kolumn cechując nieocechowane wiersze.
4.
Postępowanie powtarzamy kolejno dla wierszy i kolumn, aż do
ocechowania kolumny nie zawierającej 1.
Jeżeli takiej kolumny nie można ocechować, to KONIEC.
W ocechowanej kolumnie bez 1 umieszczamy 1 w wierszu
wskazanym przez cechę tej kolumny. Z wiersza, w którym
umieściliśmy 1 – usuwamy 1 z kolumny wskazanej przez cechę
tego wiersza. W rozpatrywanej kolumnie umieszczamy 1 w
wierszu wskazanym przez cechę kolumny itd., aż dojdziemy do
wiersza ocechowanego „-„. Kasujemy cechy i przechodzimy do
pkt. 2.
Problem przydziału optymalnego
Dla danej sieci S =
〈
G,
∅
,
{
k
}〉
, gdzie G - graf Königa,
k
: U
→
R
wyznaczyć
U
*
∈
U
tak, aby
∑
()
∑
( )
k
u
=
ekstr
k
u
U
'
∈
U
u
∈
*
u
∈
'
gdzie U – zbiór skojarzeń najliczniejszych grafu G
U
U
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 7:
Przydziały optymalne
77
Algorytm wyznaczania optymalnego przydziału (dla min)
Dane:
macierz
k


, gdzie:
{}
ij
rxr
r max m,n ,
=
mW nW
=
I
,
=
II
;
( )
{}

k
u
,
v
,
dla
u
∈
W
I
,
v
∈
W
II
k
=
i
j
i
j
ij

0
,
dla
i
>
m
∨
j
>
n
1.
Od elementów k
ij
każdego wiersza odejmujemy element
minimalny w tym wierszu.
Od nowych elementów każdej kolumny odejmujemy element
minimalny w tej kolumnie.
Oczka zawierające element „0” są oczkami dopuszczalnymi.
2.
Wyznaczamy najliczniejszy zbiór oczek dopuszczalnych,
niezależnych. Czy liczność tego zbioru = r ?
TAK
-
KONIEC
NIE
–wyznaczamy dwa podzbiory wszystkich oczek (na
podstawie ostatniego cechowania):
A – zbiór oczek odpowiadających ocechowanym wierszom
i nieocechowanym kolumnom;
B – zbiór oczek odpowiadających nieocechowanym
wierszom i ocechowanym kolumnom.
3.
Ze zbioru A wybieramy oczko, któremu odpowiada minimalny
element ostatnio przekształconej macierzy. Do wszystkich
elementów odpowiadających oczkom ze zbioru B dodajemy ten
element minimalny, a od wszystkich elementów
odpowiadających elementom (oczkom) zbioru A odejmujemy
ten element. Oczka z „0” są oczkami dopuszczalnymi.
Przejdź do pkt. 2.
Algorytm dla max :
k
I
ij
= −
k
ij

:
[ Pobierz całość w formacie PDF ]