Optimizacijske metode
Optimizacijske metode - vaje 10.4.2020
Prirejanja v dvodelnih grafih
-
dvodelen graf: $G = (V, E)$ neusmerjen graf, $V = A + B$, $uv \in E \Rightarrow u \in A, v \in B$
-
prirejanje: $M \subseteq E$, vsako vozlišče iz $V$ se pojavi kot krajišče največ ene povezave iz $M$
-
pokritje: $C \subseteq V$, vsaka povezava iz $E$ ima vsaj eno krajišče iz $C$
-
$|M| \le |C|$
-
dvodelni grafi: $M^*$ maksimalno prirejanje, $C^*$ minimalno pokritje:
\[|M^*| = |C^*|\]
Naloga 1
Poišči največja prirejanja in najmanjša pokritja v danih dvodelnih grafih.
graph G1 {
rankdir=LR
node [style=filled]
edge [penwidth=2]
a -- f [color=green]
b -- i [color=green]
c -- f
c -- h [color=green]
d -- i
e -- g [color=green]
d [color=red]
i [color=blue]
b [color=red]
a [color=blue]
c [color=blue]
e [color=blue]
}
- Maksimalno prirejanje: $M^* = {af, bi, ch, eg}$
- Minimalno pokritje: $C^* = {a, c, e, i}$
graph G3 {
node [style=filled]
edge [penwidth=2]
000 -- 001
000 -- 010
000 -- 100 [color=green]
001 -- 011 [color=green]
001 -- 101
010 -- 011
010 -- 110 [color=green]
100 -- 101
100 -- 110
011 -- 111
101 -- 111 [color=green]
110 -- 111
000 [color=blue]
011 [color=blue]
101 [color=blue]
110 [color=blue]
}
- Maksimalno prirejanje: $M^* = {{000, 100}, {001, 011}, {010, 110}, {101, 111}}$
- Minimalno pokritje: $C^* = {000, 011, 101, 110}$
graph G3 {
node [style=filled]
edge [penwidth=2]
a -- b [color=green]
a -- c
a -- d
b -- e
d -- f [color=green]
c -- g
e -- h [color=green]
f -- h
f -- i
g -- i [color=green]
e -- j
g -- j
b -- k
i -- k
c -- l [color=green]
h -- l
d -- m
j -- m [color=green]
k -- n [color=green]
l -- n
m -- n
a
f
g [label=g3, color=red]
e [label=e3, color=red]
k [label=k3, color=red]
l [label=l1, color=red]
m
b [label=b4, color=blue]
c [label=c2, color=blue]
d
h [label=h2, color=blue]
i [label=i4, color=blue]
j [label=j4, color=blue]
n [label=n2, color=blue]
}
- Maksimalno prirejanje: $M^* = {ab, df, eh, gi, cl, jm, kn}$
- Minimalno pokritje: $C^* = {a, e, f, g, k, l, m}$
Naloga 2
Gasilsko društvo v Spodnjem Birtniku je organizirano v več odborov. Predsednik odbora za cisterne je Anton, tajnik odbora je Bogdan, blagajnik pa Cene. Odboru za cevi predseduje Cene, blagajnik je David, tajnika pa odbor zaradi racionalizacije nima. V odboru za sirene si Bogdan predsedstvo deli z Davidom, v odboru za utripajoče luči pa z Evgenom. David in Evgen sta hkrati tudi predsednik in namestnik predsednika v odboru za hidrante.
Na redni letni skupščini se najprej izvoli delovno predsedstvo, v katerem mora vsak odbor imeti svojega predstavnika, nihče pa ne sme zastopati dveh odborov. Kdo naj predstavlja kateri odbor?
graph G4 {
node [style=filled]
edge [penwidth=2]
rankdir=LR
A -- cisterne [color=green]
B -- cisterne
C -- cisterne
C -- cevi [color=green]
D -- cevi
B -- sirene
D -- sirene [color=green]
B -- luči [color=green]
E -- luči
D -- hidranti
E -- hidranti [color=green]
D [color=red]
cevi [color=blue]
sirene [color=blue]
hidranti [color=blue]
C [color=red]
B [color=red]
E [color=red]
cisterne [color=blue]
luči [color=blue]
}
Naloga 3
Katere izmed naslednjih plošč se da v celoti pokriti z dominami velikosti 1 × 2?
graph P1 {
rankdir=LR
node [style=filled]
edge [penwidth=2]
a -- b
a -- e
c -- b [color=green]
c -- g
d -- e
f -- b
f -- e [color=green]
f -- g
f -- j
h -- g [color=green]
i -- e
i -- j [color=green]
k -- g
k -- j
l -- j
}
graph P2 {
rankdir=LR
node [style=filled]
edge [penwidth=2]
a -- c [color=green]
b -- c
b -- f [color=green]
e -- d [color=green]
e -- f
e -- i
g -- c
g -- f
g -- h [color=green]
g -- k
j -- f
j -- i [color=green]
j -- k
j -- n
l -- h
l -- k
l -- m [color=green]
o -- k [color=green]
o -- n
p -- n [color=green]
}
graph P3 {
rankdir=LR
node [style=filled]
edge [penwidth=2]
a -- b [color=green]
c -- b
e -- b
e -- d [color=green]
e -- f
c [color=red]
b [color=blue]
a [color=red]
e [color=blue]
}
graph P4 {
rankdir=LR
node [style=filled]
edge [penwidth=2]
a -- b
a -- d [color=green]
c -- b [color=green]
c -- f
e -- b
e -- d
e -- f
e -- j [color=green]
g -- f [color=green]
i -- d
i -- h [color=green]
i -- j
i -- l
k -- f
k -- j
k -- n [color=green]
m -- j
m -- l [color=green]
m -- n
}
Naloga 4
Sledečo dvojno stohastično matriko zapiši kot konveksno kombinacijo permutacijskih matrik:
\[\begin{aligned} \begin{pmatrix} \fbox{0.3} & 0.4 & 0.1 & 0.2 \\ 0.3 & 0.1 & \fbox{0.6} & 0 \\ 0.3 & \fbox{0.4} & 0 & 0.3 \\ 0.1 & 0.1 & 0.3 & \fbox{0.5} \end{pmatrix} &= \\ 0.3 \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} + \begin{pmatrix} 0 & \fbox{0.4} & 0.1 & 0.2 \\ \fbox{0.3} & 0.1 & 0.3 & 0 \\ 0.3 & 0.1 & 0 & \fbox{0.3} \\ 0.1 & 0.1 & \fbox{0.3} & 0.2 \end{pmatrix} &= \\ 0.3 \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} + 0.3 \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0.1 & 0.1 & \fbox{0.2} \\ 0 & 0.1 & \fbox{0.3} & 0 \\ \fbox{0.3} & 0.1 & 0 & 0 \\ 0.1 & \fbox{0.1} & 0 & 0.2 \end{pmatrix} &= \\ 0.3 \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} + 0.3 \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} &+ \\ + 0.1 \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & \fbox{0.1} & 0.1 & 0.1 \\ 0 & 0.1 & \fbox{0.2} & 0 \\ \fbox{0.2} & 0.1 & 0 & 0 \\ 0.1 & 0 & 0 & \fbox{0.2} \end{pmatrix} &= \\ 0.3 \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} + 0.3 \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0.1 & 0.1 & \fbox{0.2} \\ 0 & 0.1 & \fbox{0.3} & 0 \\ \fbox{0.3} & 0.1 & 0 & 0 \\ 0.1 & \fbox{0.1} & 0 & 0.2 \end{pmatrix} &= \\ 0.3 \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} + 0.3 \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} + 0.1 \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} &+ \\ + 0.1 \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0.1 & \fbox{0.1} \\ 0 & 0.1 & \fbox{0.1} & 0 \\ 0.1 & \fbox{0.1} & 0 & 0 \\ \fbox{0.1} & 0 & 0 & 0.1 \end{pmatrix} &= \\ 0.3 \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} + 0.3 \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} + 0.1 \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} &+ \\ + 0.1 \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} + 0.1 \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix} + 0.1 \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} & \end{aligned}\]Naloga 5
Dopolni spodnji kvadrat tako, da bodo v vsaki vrstici in v vsakem stolpcu vsa števila od $1$ do $9$.
| 2 | 4 | 9 | 8 | 7 | 5 | 3 | 1 | 6 |
| 4 | 1 | 6 | 9 | 3 | 2 | 7 | 8 | 5 |
| 9 | 7 | 2 | 1 | 8 | 4 | 5 | 6 | 3 |
| 1 | 2 | 3 | 4 | 5 | 6 | 9 | 7 | 8 |
| 6 | 9 | 1 | 2 | 4 | 3 | 8 | 5 | 7 |
| 7 | 3 | 5 | 6 | 1 | 8 | 4 | 2 | 9 |
| 3 | 6 | 8 | 5 | 9 | 7 | 1 | 4 | 2 |
| 8 | 5 | 4 | 7 | 6 | 9 | 2 | 3 | 1 |
| 5 | 8 | 7 | 3 | 2 | 1 | 6 | 9 | 4 |