Optimizacijske metode - vaje 10.4.2020

--- tags: vaje, om, prirejanja, dvodelni grafi hackmd: https://hackmd.io/RMrkvGvgSgOvADkKEWz7-g plugins: mathjax, viz.js --- # 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. ```graphviz 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\}$ ---- ```graphviz 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\}$ ---- ```graphviz 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? ---- ```graphviz 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? ![](https://raw.githubusercontent.com/jaanos/optimizacijske-metode/master/zapiski/2020/2020-04-10/plosce.png) ---- ```graphviz 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 } ``` ---- ```graphviz 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] } ``` ---- ```graphviz 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] } ``` ---- ```graphviz 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 |

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.