Predavanje 23.3.
Definicija. Matrika $A = (a_{ij})_{i,j=1}^n \in \mathbb{R}^{n \times n}$ je dvojno stohastična, če velja $a_{ij} \ge 0$ ($1 \le i, j \le n$) ter $\sum_{j=1}^n a_{ij} = 1$ ($1 \le i \le n$) in $\sum_{i=1}^n a_{ij} = 1$ ($1 \le j \le n$).
Primer dvojno stohastične matrike: $$ \begin{bmatrix} 0 & 0.9 & 0.1 \\ 0.4 & 0.1 & 0.5 \\ 0.6 & 0 & 0.4 \end{bmatrix} $$
Definicija. Matrika $P = (p_{ij})_{i,j=1}^n \in \{0, 1\}^{n \times n}$ je permutacijska matrika, če je v vsaki vrstici in v vsakem stolpcu natanko ena enica.
Primeri za $n = 3$: $$ \begin{array}{cccccc} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}, & \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}, & \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}, & \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}, & \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix} \\ 123 & 132 & 213 & 231 & 312 & 321 \end{array} $$ Imamo $n!$ permutacijskih matrik velikosti $n \times n$.
Permutacijske matrike so dvojno stohastične.
Trditev. Naj bo $A \in \mathbb{R}^{n \times n}$ dvojno stohastična matrika. Potem obstaja permutacijska matrika $P \in \{0, 1\}^{n \times n}$, tako da velja $p_{ij} = 1 \Rightarrow a_{ij} > 0$ ($1 \le i, j \le n$).
Dokaz. Naj bo $G = (V, E)$ usmerjen graf z množico vozlišč $V = \{v_i, s_i \mid 1 \le i \le n\}$ in množico povezav $E = \{v_i s_j \mid a_{ij} > 0\}$. Postavimo še $b_{v_i} = -1$, $b_{s_i} = 1$ ($1 \le i \le n$) in $c_{v_i s_j} = 0$ ($v_i s_j \in E$). Dobljeni problem razvoza je dopusten, saj obstaja dopustna rešitev z $x_{v_i s_j} = a_{ij}$ ($v_i s_j \in E$): $$ \begin{aligned} v_i&:& \sum_{v_i s_j \in E} x_{v_i s_j} &= \sum_{j=1}^n a_{ij} = 1 \\ s_j&:& \sum_{v_i s_j \in E} x_{v_i s_j} &= \sum_{i=1}^n a_{ij} = 1 \end{aligned} $$ Ker obstaja dopustna rešitev $x$, obstaja tudi celoštevilska dopustna rešitev $x'$: $$ \begin{aligned} v_i&:& \sum_{v_i s_j \in E} x_{v_i s_j}' &= 1, \\ s_j&:& \sum_{v_i s_j \in E} x_{v_i s_j}' &= 1, \end{aligned} $$ kjer je v zgornjih vsotah natanko eden od $x_{v_i s_j}'$ enak $1$, ostali pa so enaki $0$. Tako lahko dobimo permutacijsko matriko $P$, kjer je $p_{ij} = 1$, če je $x_{v_i s_j}' = 1$, in $p_{ij} = 0$ sicer. Očitno potem velja $p_{ij} = 1 \Rightarrow a_{ij} > 0$ ($1 \le i, j \le n$).
Tako permutacijsko matriko lahko najdemo z dvofazno simpleksno metodo na omrežjih.
V našem primeru:
digraph G {
rankdir=TD
nodesep=0.5
ranksep=1
edge [fontcolor=red]
v1 [label=-1]
v2 [label=-1]
v3 [label=-1]
s1 [label=1]
s2 [label=1]
s3 [label=1]
v1 -> s2 [label=0.9]
v1 -> s3 [label=0.1]
v2 -> s1 [label=0.4]
v2 -> s2 [label=0.1]
v2 -> s3 [label=" 0.5"]
v3 -> s1 [label=" 0.6"]
v3 -> s3 [label=0.4]
}
Definicija. Naj bo $G = (V, E)$ neusmerjen graf. Množici $M \subseteq E$ pravimo prirejanje, če nobeni dve povezavi iz $M$ nimata skupnega krajišča (tj., $\forall e, f \in M: (e \ne f \Rightarrow e \cap f = \emptyset)$). Prirejanje $M$ je popolno prirejanje, če je vsako vozlišče grafa $G$ krajišče povezave iz $M$ (tj., $\forall v \in V \ \exists e \in M: v \in e$).
Kőnigov izrek o plesnih parih. Naj bo $G = (V, E)$ dvodelen regularen graf (tj., lahko zapišemo $V = X + Y$, tako da $\forall xy \in E: (x \in X \land y \in Y)$, ter $\exists r \in \mathbb{N} \ \forall v \in V: \deg(v) = r$). Potem obstaja popolno prirejanje $M \subseteq E$ v grafu $G$.
Opomba. Če imamo $n$ deklet in $n$ fantov ter vsako dekle pozna $r$ fantov in vsak fant pozna $r$ deklet, potem lahko vsako dekle pleše s fantom, ki ga pozna.
graph G {
rankdir=TD
nodesep=0.5
ranksep=1
node [label=""]
d1 -- f1 [color=red]
d1 -- f2 [style=invis]
d1 -- f3
d1 -- f4 [style=invis]
d2 -- f1 [style=invis]
d2 -- f2 [style=invis]
d2 -- f3 [color=red]
d2 -- f4
d3 -- f1
d3 -- f2 [color=red]
d3 -- f3 [style=invis]
d3 -- f4 [style=invis]
d4 -- f1 [style=invis]
d4 -- f2
d1 -- f3 [style=invis]
d4 -- f4 [color=red]
}
Dokaz. Naj bo $X = \{x_1, x_2, \dots x_n\}$ in $Y = \{y_1, y_2, \dots y_n\}$. Definirajmo matriko $A = (a_{ij})_{i,j=1}^n$ z $$ a_{ij} = \begin{cases} {1 \over r} & x_i \sim y_j, \\ 0 & \text{sicer.} \end{cases} $$ Matrika $A$ je dvojno stohastična, saj velja $$ \begin{aligned} \sum_{j=1}^n a_{ij} &= {1 \over r} \cdot r = 1 & (1 \le i \le n) \\ \sum_{i=1}^n a_{ij} &= {1 \over r} \cdot r = 1 & (1 \le j \le n) \end{aligned} $$ Po prejšnji trditvi obstaja permutacijska matrika $P = (p_{ij})_{i,j=1}^n$, tako da $$ p_{ij} = 1 \ \Rightarrow\ a_{ij} > 0 \ \Rightarrow\ a_{ij} = {1 \over r} \ \Rightarrow\ x_i \sim y_j \quad (1 \le i, j \le n) $$ Matrika $P$ določa popolno prirejanje $M$: $$ p_{ij} = 1 \ \Leftrightarrow\ x_i y_j \in M \quad (1 \le i, j \le n) $$