slama.dev

Diskrétní a spojitá optimalizace

poznámky poznamky Icon · 10. 1. 2022 · 🇨🇿 · dostupné v PDF · [upravit]

Úvodní informace

Tato stránka obsahuje moje poznámky z přednášky Martina Loebla a Milana Hladíka z akademického roku 2021/2022 (MFF UK). Pokud by byla někde chyba/nejasnost, nebo byste rádi něco přidali, tak stránku můžete upravit pull requestem (případně mi dejte vědět na mail).

Diskrétní optimalizace

Matroidy

Definice (matroid): je dvojice (X,S)(X, \mathcal{S}), kde XX je konečná množina, S2X\mathcal{S} \subseteq 2^X splňující

  1. S\emptyset \in \mathcal{S}
  2. dědičnost: (AS)AA    AS(\forall A \in \mathcal{S}) A' \subseteq A \implies A' \in \mathcal{S}
  3. výměnný axiom: (U,VS) U>V    (uUV)V{u}S(\forall U, V \in \mathcal{S})\ |U| > |V| \implies (\exists u \in U \setminus V) V \cup \left\{u\right\} \in \mathcal{S}
    • (3):(3'): AX    A \subseteq X \implies všechny maximální (\subseteq) podmnožiny AA v S\mathcal{S} mají stejnou velikost

Poznámka: Při definici matroidu je dobré si predstavit graf. XX je tu množina hran a S\mathcal{S} všechny acyklické podgrafy. Pak podmínka dědičnosti říká, že acyklické podgrafy jsou rovněž acyklické a axiom 33' to, že maximální kostry (co do inkluze) mají stejnou velikost.

Lemma (stejná definice): Axiomy (1,2,3)(1, 2, 3) a (1,2,3)(1, 2, 3') definují stejný objekt.

Důkaz: (3)    (3)(3) \implies (3') sporem:

Důkaz: (3)    (3)(3') \implies (3) sporem:

Příklad:

  1. vektorový matroid:
    • nechť MM je matice nad tělesem F\mathbb{F} s řádky CC
    • VM=(C,S)\mathcal{V}_M = (C, \mathcal{S}), kde
      • AS    ACA \in \mathcal{S} \iff A \subseteq C je lineárně nezávislá v F\mathbb{F}
      • 3’ vyplývá přímo ze Steinitzovy věty o výměně, zbytek přímo z definice
  2. grafový matroid:
    • mějme graf G=(V,E)G = (V, E)
    • MG=(E,S)\mathcal{M}_G = (E, \mathcal{S}), kde
      • AS    AEA \in \mathcal{S} \iff A \subseteq E a AA je acyklická
      • (1):(1): S\emptyset \in \mathcal{S}
      • (2):(2): podmnožina acyklické je rovněž acyklická
      • (3):(3): počítání přes to, kolik hran je v komponentách souvislosti
  3. Fanova rovina:
    • za XX uvážíme body Fanovy roviny a za báze trojprvkové množiny bodů neležící na jedné přímce (v rámci Fanovy roviny – kružnice uprostřed je také přímka)

Grafy a matroidy

Definice (sudá podmnožina hran): podmnožina hran EEE' \subseteq E je sudá, právě když H=(V,E)H = (V, E') má pouze sudé stupně.

Definice (matice incidence) grafu G=(V,E)G = (V, E) je matice IGF2V×EI_G \in \mathbb{F}_2^{|V| \times |E|} t.ž. (IG)v,e={1ve0jinak\left(I_G\right)_{v,e}=\begin{cases} 1 & v \in e \\ 0 & \text{jinak} \end{cases}

Definice (jádro matice incidence): pro matici incidence IGI_G definujeme jádro jako KerF2IG={xF2EIGx=0}\mathrm{Ker}_{\mathbb{F}_2} I_G = \left\{\mathbf{x} \in \mathbb{F}_2^{|E|} \mid I_G \mathbf{x} = \mathbf{0}\right\}

Definice (charakteristický vektor): mějme nosnou množinu XX a podmnožinu AXA \subseteq X. Charakteristický vektor AA je χA{0,1}X\chi_A \in \left\{0, 1\right\}^{|X|} t.ž. (χA)k={1kA0k∉A\left(\chi_A\right)_{k} = \begin{cases} 1 & k \in A \\ 0 & k \not\in A \end{cases}

(👀): řádek matice incidence IGI_G indexovaný vrcholem ww je roven χN(w)okolıˊ\chi_{\underbrace{|N(w)|}_{\text{okolí}}}

(👀) (prostor cyklů): jádro matice můžeme ekvivalentně vyjádřit jako KerF2IG={xF2Ex=χE pro E sudou}\mathrm{Ker}_{\mathbb{F}_2} I_G = \left\{x \in \mathbb{F}_2^{|E|} \mid x = \chi_{E'}\ \text{pro}\ E'\ \text{sudou}\right\} Tuto množinu rovněž nazýváme prostor cyklů.

Řádové funkce

V řeči grafů chceme pro libovolnou množinu hran (prvků podmnožin) vrátit největší acyklický podgraf (prvek matroidu).

Definice (řádová funkce): mějme systém podmnožin (X,S),S2X(X, \mathcal{S}), \mathcal{S} \subseteq 2^{X} a AXA \subseteq X. Pak řádovou funkci r:2XNr: 2^{X} \mapsto \mathbb{N} definujeme jako velikost maximální podmnožiny patřící do S\mathcal{S}:

r(A)=max{XX2AXS}r(A) = \max \left\{|X| \mid X \in 2^A \land X \in \mathcal{S}\right\}

Věta (řádová funkce matroidu): funkce r:2XNr : 2^X \mapsto \mathbb{N} je řádová funkce nějakého matroidu nad XX právě tehdy, když platí:

Důkaz (\Rightarrow): ukážeme přímo:

Pokud B=B~|B| = |\tilde{B}|, pak platí R3\mathrm{R3}

Důkaz (\Leftarrow): z XX konstruujeme matroid s řádovou funkcí rr. Matroid definujme jako M=(X,S)t.zˇ.AS    A=r(A)\mathcal{M} = \left(X, \mathcal{S}\right)\quad\text{t.ž.}\quad A \in \mathcal{S} \iff |A| = r(A)

Ukážeme, že (X,S)\left(X, \mathcal{S}\right) je matroid:

  1. S\emptyset \in \mathcal{S} (triviálně)
  2. pro spor předpokládejme, že dědičnost neplatí
    • existuje tedy AS,AAA \in \mathcal{S}, A' \subseteq A ale A>r(A)|A'| > r(A') (menší nemůže být z definice řádové funkce, jelikož je pro množinu definována jako velikost nějaké její podmnožiny) r(A)r(A)+AAR2<A+AA=A    A∉S\begin{aligned} r(A) &\le r(A') + |A \setminus A'| & \quad \text{R2} \\ &< |A'| + |A \setminus A'| \\ &= |A| \implies A \not\in \mathcal{S} & ↯ \end{aligned}
  3. pro spor předpokládejme, že U,VS\exists U, V \in \mathcal{S} t.ž. U>V|U| > |V| ale xUV:V{x}∉S\forall x \in U \setminus V: V \cup \left\{x\right\} \not\in \mathcal{S}
    • přes R3\mathrm{R3} získáváme (x,yUV)(\forall x, y \in U \setminus V): r(V)=r(V{x})=r(V{y})r(V{x,y})R3r(V(UV))=r(UV)r(U)=U\begin{aligned} r(V) &= r(V \cup \left\{x\right\}) = r(V \cup \left\{y\right\}) \\ &\Rightarrow r(V \cup \left\{x, y\right\}) & \quad \mathrm{R3}\\ &\Rightarrow r(V \cup (U \setminus V)) = r(U \cup V) \ge r(U) = |U| & ↯ \end{aligned}

Poznámka (alternativní znění důkazu 2): díky R2 víme, že odebráním prvku z AA se může r(A)r(A) buď o 1 snížit, nebo zůstat stejný. Zůstat stejný být však nemůže (z definice řádové funkce), musí se tedy o 11 snížit a v tom případě je rovněž v S\mathcal{S}.

Věta (řádová funkce a submodularita): r:2XNr : 2^X \mapsto \mathbb{N} je řádová funkce matroidu     \iff

Důkaz (\Rightarrow R1’ a R2’):

Důkaz (\Rightarrow R3’):

Máme r(Y)+r(Z)=AY+AZdefinice=AYAZ+AYAZinkluze/exkluzer(YZ)+AYAZAAYAZ\begin{aligned} r(Y) + r(Z) &= |A_Y| + |A_Z| & \quad \text{definice} \\ &= |A_Y \cap A_Z| + |A_Y \cup A_Z| & \quad \text{inkluze/exkluze} \\ &\ge r(Y \cap Z) + |A_Y \cup A_Z| & \quad A \subseteq A_Y \cap A_Z \end{aligned} K důkazu tvrzení zbývá ukázat, že AYAZr(YZ)|A_Y \cup A_Z| \ge r(Y \cup Z).

(👀): AYA_Y nemůže být rozšířené víče než AZYA_Z \setminus Y prvky na nezávislou množinu v YZY \cup Z

Nyní můžeme dokončit důkaz: r(YZ)AY+AZYAYAZ\begin{aligned} r(Y \cup Z) &\le |A_Y| + |A_Z \setminus Y| \\ & \le |A_Y \cup A_Z| \end{aligned}

Důkaz (matroid \Leftarrow R1’, R2’, R3’): ukážeme R1,R2,R3\mathrm{R1, R2, R3}

(👀): matroidy jsou systémy podmnožiny, kde řádová funkce je monotonní a submodulární.

„Jak cením přidání xx, když mám TT.“

Definice (marginální hodnota): Mějme množinu XX a funkce f:2XNf: 2^X \mapsto \mathbb{N} . Pak xX\forall x \in X definujeme Δfx:2XZ\Delta f_x : 2^X \mapsto \mathbb{Z}: TX    Δfx(T)=f(T{x})f(T)T \subseteq X \implies \Delta f_x (T) = f(T \cup \left\{x\right\}) - f(T)

Věta (marginální hodnota a submodularita): f:2XNf: 2^X \mapsto \mathbb{N} je submodulární     xX:Δfx\iff \forall x \in X: \Delta f_x je nerostoucí

Důkaz: Je-li ff nerostoucí, pak U,y,z\forall U, y, z platí f(U{y,z})f(U{y})Δfz(U{y})f(U{z})f(U)Δfz(U)\underbrace{f(U \cup \left\{y, z\right\}) - f(U \cup \left\{y\right\})}_{\Delta f_z(U \cup \left\{y\right\})} \le \underbrace{f(U \cup \left\{z\right\}) - f(U)}_{\Delta f_z(U)}

Tedy ff je nerostoucí     UX\iff \forall U \subseteq X a y,zXUy, z \in X \setminus U platí f(U{y}A)+f(U{z}B)f(U{y,z}AB)+f(UAB)f(\underbrace{U \cup \left\{y\right\}}_{A}) + f(\underbrace{U \cup \left\{z\right\}}_{B}) \ge f(\underbrace{U \cup \left\{y, z\right\}}_{A \cup B}) + f(\underbrace{U}_{A \cap B}) \qquad *

To je skoro submodularita!

Důkaz (\Rightarrow): platí přímo z definice submodularity (prostě tam dosadíme)

Důkaz (\Leftarrow): dokazujeme     * \implies submodularita. Chceme f(Y)+f(Z)f(YZ)+f(YZ)f(Y) + f(Z) \ge f(Y \cup Z) + f(Y \cap Z)

TODO: ošklivej důkaz

Hladový algoritmus

Definice (úloha kombinatorické optimalizace): je dán možinový systém (X,S)(X, \mathcal{S}) a váhová funkce w:XQw : X \mapsto \mathbb{Q}. Úloha kombinatorické optimalizace je najít ASA \in \mathcal{S} t.ž. w(A)=vAw(v)=wTχAw(A) = \sum_{v \in A} w(v) = w^T \chi_A je maximální (χA\chi_A je charakteristický vektor AA, který je 11 pro vAv \in A a 00 jindy).

Příklad:

  1. maximální párování v GG
  2. minimální Hamiltonovská kružnice
  3. minimální hranový řez

Algoritmus (hladový): nechť že w1wnw_1 \ge \ldots \ge w_n a m=max{iXwi0}m = \max \left\{i \in X \mid w_i \ge 0\right\}; pak:

  1. nastav J=J = \emptyset
  2. pro i={1,,n}i = \left\{1, \ldots, n\right\}
    • je-li J{i}SJ \cup \left\{i\right\} \in \mathcal{S}, pak ii přidej do JJ
  3. vrať JJ

(👀): algoritmus je polynomiální (pro rozumné předpoklady na reprezentaci matroidu).

(👀): pro výše uvedené příklady nemusí algoritmus vrátit optimální řešení.

Věta (hladový algoritmus na matroidech): nechť (X,S)(X, \mathcal{S}) je dědičný množinový systém a S\emptyset \in \mathcal{S}. Pak hladový algoritmus vyřeší správně úlohu kombinatorické optimalizace pro každou funkci w    (X,S)w \iff (X, \mathcal{S}) je matroid.

Důkaz (\Rightarrow): obměnou: nechť (X,S)(X, \mathcal{S}) není matroid     \implies HA nefunguje. Zkonstruujeme w:XQw : X \mapsto \mathbb{Q}, na které algoritmus selže.

Jelikož (X,S)(X, \mathcal{S}) není matroid, tak neplatí 3,33, 3' a tedy U,VS,U>V\exists U, V \in \mathcal{S}, |U| > |V| a U,VU, V jsou max. nezávislé množiny. Pak definujeme ww následně (pro b,aQ,b>a>0b, a \in \mathbb{Q}, b > a > 0):

V takovém případě hladový algoritmus najde UU, ikdyž VV je větší.

Důkaz (\Leftarrow): nejprve dokážeme pomocné lemma.

Lemma: mějme w1wnw_1 \ge \ldots \ge w_n, mnm \le n maximální t.ž. wm>0w_m > 0, množiny Ti{0,1}iT_i \subseteq \left\{0, 1\right\}^i a zz' je charakteristický vektor výsledku HA (rozumíme tím, že je to 0/10/1 vektor podle toho, které prvky HA vybral s tím, že jsou setřízené podle ww). Pak i\forall i platí z(Ti)=iTizi=r(Ti)z'(T_i) = \sum_{i \in T_i} z'_i = r(T_i)

Důkaz: Ukážeme, že HA najde v každém kroku největší nezávislou množinu z uvažovaných prvků.

Pro spor nechť i\exists i t.ž. z(Ti)<r(Ti)z'(T_i) < r(T_i). Vezměme nejmenší takové ii:

Platí, že z(Ti1)=r(Ti1)z'(T_{i - 1}) = r(T_{i - 1}) (jelikož ii je nejmenší protipříklad). Pokud HA další prvek přidá, tak je vše v pořádku a z(Ti)=r(Ti)z'(T_{i}) = r(T_{i}) platí. Jinak to znamená, že z(Ti)z'(T_{i}) je co do inkluze maximální množina v TiT_i, což je spor s 33'.

Nyní k původnímu důkazu: označíme zz^* charakteristický vektor optima. Pak

wTz=wizi=wi(z(Ti)z(Ti1))T0=,=(wiwi+1)0z(Ti)+wm>0z(Tm)(wiwi+1)r(Ti)i+wmr(Tm)=(wiwi+1)z(Ti)i+wmz(Tm)lemma vyˊsˇe=wTz\begin{aligned} w^T z^* &= \sum w_i \cdot z^*_i \\ &= \sum w_i (z^*(T_i) - z^*(T_{i - 1})) & \qquad T_0 = \emptyset, * \\ &= \sum \underbrace{(w_i - w_{i + 1})}_{\ge 0} z^* (T_i) + \underbrace{w_m}_{> 0} z^*(T_m) & ** \\ &\le \sum (w_i - w_{i + 1}) r (T_i)_i + w_m r(T_m) \\ &= \sum (w_i - w_{i + 1}) z' (T_i)_i + w_m z'(T_m) & \text{lemma výše} \\ &= w^T z' \\ \end{aligned}

* rovnost zi=zi(Ti)zi(Ti1)z_i^* = z_i^*(T_i) - z_i^*(T_{i - 1}) platí, protože zi(Ti)z_i^*(T_i) se zvýší právě tehdy, když charakteristický vektor získá novou 11 (konkrétně tu na pozici ziz_i^*).

** tohle vypadá magicky, ale dává to smysl – z(Ti)z^*(T_i) v jednom cyklu smyčky přičítáme a ve druhém odčítáme, tak jsme to jen posunuli do wiwi+1w_i - w_{i + 1}, navíc také započteme poslední část součtu, na který se nedostane. Navíc právě v tomhle kroku používáme předpoklad setřízenosti.

Jelikož navíc triviálně wTzwTzw^T z* \ge w^T z' (je to optimum), tak věta platí.

Důsledek (grafy): poštvání HA na grafový matroid vrátí maximální (minimální pro w-w) kostru. Poštvání na duál vrátí maximální množinu hran, kterou když odstraníme tak graf zůstane souvislý.

Důsledek (lineární programy): nechť (X,S)(X, \mathcal{S}) je matroid a wQXw \in \mathbb{Q}^X. Pak HA vyřeší následující lineární program maxiXwizi\max \sum_{i \in X} w_i z_i za podmínek z(A)r(A),z0z(A) \le r(A), z \ge 0 pro AX\forall A \subseteq X

Operace na matroidech

Součet – pro matroidy M1=(X1,S1),M2=(X2,S2),X1X2=\mathcal{M_1} = (X_1, \mathcal{S}_1), \mathcal{M_2} = (X_2, \mathcal{S}_2), X_1 \cap X_2 = \emptyset M1+M2=(X=X1X2,{AXAX1S1AX2S2})\mathcal{M}_1 + \mathcal{M}_2 = (X = X_1 \cup X_2, \left\{A \in X \mid A \cap X_1 \in \mathcal{S}_1 \land A \cap X_2 \in \mathcal{S}_2\right\})

Příklad (součet a kontrakce v grafovém matroidu):

Sjednocení – zobecnění součtu. Definice je stejná, ale nepředpokládáme různé X1,X2X_1, X_2.

Věta (sjednocení matroidů je matroid)): sjednocení matroidů je matroid s řádovou funkcí r(U)=minTU{UT+r1(TX1)++rk(TXk)}r(U) = \min_{T \subseteq U} \left\{|U - T| + r_1(T \cap X_1) + \ldots + r_k(T \cap X_k)\right\}

Důkaz (náznak): matroidy zdisjunktníme (Xi=Xi×{i}X'_i = X_i \times \left\{i\right\}), sečteme a pak zobrazíme.

Mazání hran v grafu.

Mazání – pro matroid M=(X,S)\mathcal{M} = (X, \mathcal{S}) a YXY \subseteq X: MY=(XY,{AYAS})\mathcal{M} - Y = (X - Y, \left\{A - Y \mid A \in \mathcal{S}\right\}) je opět matroid.

Podobné jako mazání, ale chová se dost jinak (viz kontrakce/mazání hran v grafu). Např. na mostech grafu se ale chová stejně.

Kontrakce – nechť M=(X,S)\mathcal{M} = (X, \mathcal{S}) je matroid, AXA \subseteq X a JSJ \in \mathcal{S} je max. nezávislá množina v AA. Pak MA=(XA,{ZXZJS})\mathcal{M} \setminus A = \left(X - A, \left\{Z \subseteq X \mid Z \cup J \in \mathcal{S} \right\}\right)

Věta (kontrakce matroidu je matroid): nechť M=(X,S)\mathcal{M} = (X, \mathcal{S}) je matroid a AXA \subseteq X. Pak MA\mathcal{M} \setminus A je matroid s řádovou funkcí r(Z)=r(ZA)r(A)r'(Z) = r(Z \cup A) - r(A)

Důkaz: nechť JJ je max. nz. mn v AA (viz definice kontrakce); ověříme axiomy

  1. S    J=JS\emptyset \in \mathcal{S} \iff \emptyset \cup J = J \in \mathcal{S}, platí
  2. mějme YSY \in \mathcal{S}' a YYY' \subseteq Y. Z definice víme YS    YJSY \in \mathcal{S}' \implies Y \cup J \in \mathcal{S}. Díky tomu, že YJYJSY' \cup J \subseteq Y \cup J \in \mathcal{S}, tak rovněž YJSY' \cup J \in \mathcal{S} (definice matroidu) a tedy YSY' \in \mathcal{S}'
  3. nechť ZXAZ \subseteq X \setminus A, BZB \subseteq Z je max. nez. mn. v MA\mathcal{M} \setminus A a JJ max. nez. mn. v AA

BJB \cup J je max. nezávislá podmnožina ZAZ \cup A v M\mathcal{M} a tedy B+J=r(ZA)B=r(ZA)Jr(Z)=r(ZA)r(A)urcˇenyˊ jednoznacˇneˇ\begin{aligned} |B| + |J| &= r(Z \cup A) \\ |B| &= r(Z \cup A) - |J| \\ r'(Z) &= \underbrace{r(Z \cup A) - r(A)}_{\text{určený jednoznačně}} \end{aligned}

Partition matroid – nechť X1,,XnX_1, \ldots, X_n jsou disjunktní množiny a Si={AXiA1}\mathcal{S}_i = \left\{A \subseteq X_i \mid |A| \le 1\right\}. Pak i(Xi,Si)\sum_{i} (X_i, \mathcal{S}_i) je partiční matroid.

Věta (Edmondsova MiniMaxová o průniku matroidů): nechť M1=(X,S1)\mathcal{M}_1 = \left(X, \mathcal{S}_1\right) a M2=(X1,S2)\mathcal{M_2} = \left(X_{1}, \mathcal{S_2}\right) jsou matroidy. Pak max{YYS1S2}=minAXr1(A)+r2(XA)\max \left\{|Y| \mid Y \in \mathcal{S_1} \cap \mathcal{S}_2\right\} = \min_{A \subseteq X} r_1(A) + r_2(X \setminus A)

Důkaz (\le): Nechť JS1S2J \in \mathcal{S}_1 \cap \mathcal{S}_2. Pak AX\forall A \subseteq X JAS1    JAr1(A)J(XA)S2    J(XA)r2(XA)\begin{aligned} J \cap A &\in \mathcal{S}_1 \implies |J \cap A| \le r_1(A) \\ J \cap (X \setminus A) &\in \mathcal{S}_2 \implies |J \cap (X \setminus A)| \le r_2(X \setminus A) \end{aligned} A tedy J=JA+J(XA)r1(A)+r2(XA)|J| = |J \cap A| + |J \cap (X \setminus A) | \le r_1(A) + r_2(X \setminus A)

Důkaz (\ge): TODO, tenhle důkaz je naprosto brutální

Důsledek (obraz matroidu je matroid): mějme matroid M=(X,S)\mathcal{M}' = (X', \mathcal{S}') a funkci f:X    Xf: X' \implies X. Definujme S={f[I]IS}\mathcal{S} = \left\{f[I] \mid I \in \mathcal{S}'\right\} Potom (X,S)(X, \mathcal{S}) je také matroid a navíc pro UTU \subseteq T platí r(U)=minTU{UT+r(f1(T))}r(U) = \min_{T \subseteq U} \left\{|U - T| + r'(f^{-1} (T))\right\}

Poznámka: tvrzení by platilo triviálně, pokud by se jednalo o prostou funkci (tedy pouze přejmenování prvků matriodu). Zajímavé je to, že některé prvky se mohou zobrazit na jiné a nezávislé množiny se tak zmenší, ale matroidnost se zachová.

Dualita matroidu

Duální matroid grafového matroidu je matroid množin hran, které když odebereme tak graf zůstane spojitý.

Definice (duální matroid): nechť M=(X,S)\mathcal{M} = \left(X, \mathcal{S}\right) je matroid. Definujeme duální matroid jako M=(X,S)\mathcal{M}^* = (X, \mathcal{S}^*) t.ž. BB^* je báze M    (XB)\mathcal{M}^* \iff (X - B^*) je báze M\mathcal{M} (s tím, že S\mathcal{S}^* jsou všechny podmnožiny bází).

(👀): nechť M\mathcal{M} je matroid, M\mathcal{M}^* jeho duál a AXA \subseteq X. Pak r(X)=r(XA)      ASr(X) = r(X \setminus A) \ \iff \ A \in \mathcal{S}^*

Důkaz: AA můžeme rozšířit na bázi BB^* duálu, přičemž bude stále platit r(XB)=r(X)r(X - B^*) = r(X), protože XBX - B^* je báze M\mathcal{M}. Tohle můžeme dělat ikdyž jsme další větu ještě nedokázali, jelikož pro M\mathcal{M}^* platí axiomy 1 a 2 matroidu, jelikož jsme ho definovali jako báze.

Věta (duální matroid je matroid): nechť M\mathcal{M} je matroid. Pak M\mathcal{M}^* je také matroid a navíc platí r(A)=Ar(X)+r(XA)r^*(A) = |A| - r(X) + r(X - A)

Důkaz: stačí dokázat 33' (pro dané AA mají všechny nezávislé množiny stejnou velikost), jelikož 11 a 22 platí triviálně z toho, že jsme definovali pouze báze. Uvažme libovolné AA a následující obrázek

Nechť BB je báze M\mathcal{M} t.ž. ZBZ \subseteq B a BXJB \subseteq X - J (existuje, protože r(X)=r(XJ)r(X) = r(X - J))

Jestli existuje x(AJ)Bx \in (A - J) - B, pak r(X(J{x}))=r(X)r(X - (J \cup \left\{x\right\})) = r(X) a J{x}SJ \cup \left\{x\right\} \in \mathcal{S}^* a JJ není maximální, díky čemuž J=ABJ = A - B. Rovněž platí Z=BAZ = B - A (jinak můžeme rozšířit, což je spor) a tedy r(A)=J=AB=ABA=AB(BZ)=AB+Z=Ar(X)+r(XA)\begin{aligned} r^*(A) = |J| &= |A - B| \\ &= |A| - |B \cap A| \\ &= |A| - |B \cap (B - Z)| \\ &= |A| - |B| + |Z| \\ &= |A| - r(X) + r(X - A) \end{aligned}

Poznámka: Matroid může být duální sám sobě (v tom smyslu, že M1\mathcal{M}_1 a M2\mathcal{M}_2 jsou izomorfní).

Definice (Cobáze, conezávislost): nechť M\mathcal{M} je matroid a M\mathcal{M}^* jeho duální matroid. Pak YXY \subseteq X je

V grafu jsou to kružnice.

Definice (kružnice): nechť M\mathcal{M} je matroid. Pak YXY \subseteq X je kružnice, je-li minimální (\subseteq) závislá množina.

Věta: YXY \subseteq X je cokružnice (kružnice v duálu)     Y\iff Y je min (\subseteq) protínající každou bázi.

Důkaz (\Rightarrow): sporem nechť YXY \subseteq X je cokružnice ale B\exists B báze M\mathcal{M} t.ž. YB=Y \cap B = \emptyset. Pak YXBY \subseteq X - B ale z definice je XBX - B báze M\mathcal{M}^*, což je spor se závislostí YY v M\mathcal{M^*}. Navíc kružnice je do inkluze minimální, takže minimalitu splňujeme taky.

Důkaz (\Leftarrow): opět sporem nechť YY je minimální množina (do inkluze) protínající každou bázi, ale není cokružnice. Rozebereme případy toho, co může být (chceme, aby byla minimálně nezávislá):

Důsledek: nechť GG graf souvislý. Pak cokružnice MG\mathcal{M}_G jsou přesně minimální hranové řezy.

Perfektní párování

Poznámka: o tomto tématu jsem vytvořil YouTube video, které algoritmus shrnuje.

Definice (párování): nechť G=(V,E)G = (V, E) graf. Pak MEM \subseteq E je párovaní     eeM\iff \forall e \neq e' \in M platí ee=e \cap e' = \emptyset.

Definice (největší párování) pokud M|M| je maximální.

(👀): je rozdíl mezi maximálním párováním (počítá se do inkluze) a největším (počítá se do velikosti), jelikož si hrany můžeme hladově vybrat špatně (viz lichá cesta).

Definice (perfektní párování): pokud M=V/2|M| = |V| / 2

Definice (pokrytí): vrchol je MM-pokrytý, pokud je v nějaké hraně z párování.

Definice (defekt) def(M)\mathrm{def}(M) je počet MM-nepokrytých vrcholů

Definice (alternující cesta): podgraf, který je cesta

Věta: graf G=(V,E)G = (V, E), MM párování. Pak MM je největší     \iff GG nemá zlepšující cestu.

Důkaz:

(👀): G=(V,E),AVG = (V, E), A \subseteq V. Pak v libovolném párování MM musí být liché komponenty GAG - A pokryté pouze z AA (i v nejlepším zpárování v nich zbyde alespoň jeden volný vrchol) a tedy def(M)lc(GA)A\mathrm{def}(M) \ge \mathrm{lc}(G - A) - |A| Kde lc\mathrm{lc} značí počet lichých komponent grafu.

(👀): G=(V,E)G = (V, E). Pak maxpaˊrovaˊnıˊ MM=minpaˊrovaˊnıˊ M12(Vdef(M))minAV12(Vlc(GA)+A)\max_{\text{párování}\ M} |M| = \min_{\text{párování}\ M} \frac{1}{2} \left(|V| - \mathrm{def}(M)\right) \le \min_{A \subseteq V} \frac{1}{2} \left(|V| - \mathrm{lc}(G - A) + |A|\right) kde první nerovnost plyne z úvahy, že největší párování minimalizuje defekt a druhá z dosazení pozorování výše.

Věta (Tutte-Berge): Pro výše uvedené pozorování platí rovnost.

Důkaz: stačí najít párování MM t.ž. platí rovnost.

Najdeme algoritmem (Edmonds), který najde maximální párování

  1. MM perfektní     \implies je maximální a věta platí (A=A = \emptyset)
  2. MMMM-nepokrytý vrchol rr: budujeme alternující strom TT tím, že sřídavě přidáváme hrany:
    • BB-vrcholy: vrcholy v sudé vzdálenosti od rr
    • AA-vrcholy: vrcholy v liché vzdálenosti od rr
    • zastavíme se, když:
      • existuje w∉T,{v,w}Ew \not\in T, \{v, w\} \in E a ww je nepokrytý – pak jsme našli alternující cestu
      • neexistuje ww
        • pokud je graf bipartitní, tak nemáme žádné BBB-B hrany a všechny zbývající hrany z BB-vrcholů vedou do AA-vrcholů – poté když uvážíme GAG - A, tak liché komponenty vedou pouze do AA vrcholů ale BB je o jedna více (máme rr), tedy B=A+1|B| = |A| + 1 a GG nemá perfektní párování a našli jsme defektní vrchol

Pro bipartitní grafy můžeme algoritmus výše opakovat (opakovaně stavíme stromy z vrcholů, které nejsou v párování), najít všechny defektní vrcholy a věta výše platí (máme množinu defektních vrcholů a párování splňující rovnost).

Pro nebipartitní grafy může existovat hrana mezi BBB-B vrcholy (lichá kružnice).

(👀): nechť CC lichá kružnice v GG, GG' vznikne kontrakcí CC do jednoho (pseudo)vrcholu a MM' je párování v GG'. Potom existuje párování MM v GG, že počet MM'-nepokrytých vrcholů je stejný jako počet MM-nepokrytých.

Podgrafy GG reprezentované pseudovycholy mají lichý počet vrcholů (chceme opět dostat MM a AA, abychom větu dokázali). To platí, protože pseudovrcholy vznikly kontrakcí liché kružnice na vrchol a tedy přišly o sudý počet vrcholů.

Postup pro BBB-B hrany je tedy ten, že zkontrahujeme CC, vyřešíme párování a odkontrahujeme.

AA může být i prázdné (eliminuje grafy s lichým počtem vrcholů).

Důsledek (Tutte): GG má perfektní párování právě tehdy, když AV:lc(GA)A\forall A \subseteq V: \mathrm{lc}(G - A) \le |A|

Důkaz: vychází přímo z Tutte-Berge dosazením M=V/2|M| = |V|/2 (jedná se o perfektní párování).

Věta (Edmonds-Gallai dekompozice): GG graf, G=(V,E)G = (V, E), BVB \subseteq V vrcholů nepokrytých nějakým maximálním párovaním. Nechť AVBA \subseteq V - B sousedé vrcholů z BB, C=V(BA)C = V - \left(B \cup A\right). Pak

  1. každá komponenta G(AC)G - \left(A \cup C\right) je kritická (vK:K{v}\forall v \in K: K - \left\{v\right\} má perfektní párování)
    • GG kritický     \iff GG lze zkonstruovat z liché kružnice lepením lichých uší
  2. každé maximální párování MM splňuje:
    • eM,eA    eA=1e \in M, e \cap A \neq \emptyset \implies |e \cap A| = 1 a ee vede do BB
      • tohle nezamezuje, že by dvě hrany z AA nevedly do jedné z BB
    • do každé komponenty BB vede 1\le 1 hrana MM

Důkaz: Uvažme poslední alternující les v Edmondsově algoritmu.

Každá hrana s koncem v AA vede do BB (s tím, že vrcholy v BB jsou (pseudo)vrcholy vzniklé operací kontrakce. Defekt def(M)\mathrm{def}(M) je počet komponent v tomto lese.

Nepokryté vrcholy žádným maximálním párováním:

Takové vrcholy tedy mohou být pouze v BB, čímž jsme dokázali (1).

Část (2) rovněž plyne z Edmondsova algoritmu.

Generující funkce magic

Nechť G=(V,E)G = (V, E) rovinný, w:EQw : E \mapsto \mathbb{Q} váhová funkce

  1. maximální perfektní párování – najdi MM perfektní párování t.ž. w(E)w(E) je maximální
    • polynomiální (pro všechny grafy)
  2. maximální hranový řez – najdi EE' hranový řez t.ž. w(E)w(E') je maximální
    • obecně je NP-těžný, pro grafy na 2D plochách polynomiální

Definice (determinant): nechť AA je reálná matice. Pak determinant je Det(A)=π(1)sign(π)i=1nAi,π(i)transverzaˊla\mathrm{Det}(A) = \sum_{\pi} (-1)^{\mathrm{sign}(\pi)} \overbrace{\prod_{i = 1}^{n} A_{i, \pi(i)}}^{\text{transverzála}}

Definice (permanent): nechť AA je reálná matice. Pak permanent je Per(A)=πi=1nAi,π(i)\mathrm{Per}(A) = \sum_{\pi} \prod_{i=1}^{n} A_{i, \pi(i)}

Příklad: G=(V1,V2,E)G = (V_1, V_2, E) bipartitní graf, AV1×V2A^{|V_1| \times |V_2|} 0/10/1 matice podle toho, jaké obsahuje hrany. Pak Per(A)\mathrm{Per}(A) je počet perfektních párování GG.

P(G,x,w)=P perf. paˊr.xw(P)\mathcal{P}(G, x, w) = \sum_{P\ \text{perf. pár.}} x^{w(P)} E(G,x,w)=E sudaˊxw(E)\mathcal{E}(G, x, w) = \sum_{E'\ \text{sudá}} x^{w(E')} φ(G,x,w)=C hranovyˊ rˇezxw(C)\varphi(G, x, w) = \sum_{C\ \text{hranový řez}} x^{w(C)}

Věta: GG rovinný. Pak φ(G)E(G)P(GΔ)\varphi(G) \equiv \mathcal{E}(G^*) \equiv \mathcal{P}(G_\Delta^*) kde symbolem \equiv rozumíme vzhledem k vypočítatelnosti a GΔG_\Delta následující operaci:

Rovněž předpokládáme w(e)Z,w(e)V(G)cw(e) \in \mathbb{Z}, |w(e)| \le |V(G)|^{c} pro cc konstantu.

Věta (Kasteleyn): Když GG rovinný, pak P(G,x,w)\mathcal{P}(G, x, w) lze spočítat v polynomiálním čase.

Důsledek:

Důkaz (naznačení): pro DD orientaci GG, M0M_0 fixní perfektní párování definujeme „determinantní verzi“ P\mathcal{P} následně: P(G,D,M0,x,w)=P perf. paˊr.sign(D,M0,P)xw(P)\mathcal{P(G, D, M_0, x, w)} = \sum_{P\ \text{perf. pár.}} \mathrm{sign}(D, M_0, P) x^{w(P)} kde sign(D,M0,P)=(1)# D-sudyˊch cyklu˚ M0 Δ P\mathrm{sign}(D, M_0, P) = (-1)^{\#\ \text{$D$-sudých cyklů $M_0\ \Delta\ P$}}

Postup důkazu:

Připomenutí: pro další plochy je to trochu komplikovanější, ale jde to dělat podobně.

Pošťáci a cestující

Definice: G=(V,E)G = (V, E) graf silniční sítě, l:EQ+l : E \mapsto \mathbb{Q}^+ váhová funkce:

Problém (čínského pošťáka):

  1. G=(V,E)G = (V, E)všechny stupně sudé      \implies řešení je uzavřený eulerovský tah
    • (👀): když H=(W,F)H = (W, F) má všechny stupně sudé a FF \neq \emptyset je neprázdná, pak FF má cyklus; odstraněním cyklu má opět všechny stupně sudé; opakováním dostaneme disjunktní sjednocení cyklů, což jde do eulerovského tahu udělat trivialně
  2. nechť T={vdegG(v) lichyˊ}T = \left\{v \mid \mathrm{deg}_G(v)\ \text{lichý}\right\}

(👀): T|T| je sudé (součet stupňů je sudý)

Je to taková množina vrcholů a hran, na kterou když se omezíme, tak všechny stupně vrcholů v TT jsou liché a ostatní jsou sudé.

Definice (T-join): EEE' \subseteq E je TT-join (pro množinu vrcholů TT), pokud GT=(V,E)G_T = (V, E') platí (vV)(degGT(v) lichyˊ    vT)\left(\forall v \in V\right) \left(\mathrm{deg}_{G_T} (v)\ \text{lichý} \iff v \in T\right)

Věta: nechť EEE' \subseteq E je množina hran min. trasy čínského pošťáka, které se projdou více než jednou. Pak se projdou právě 22-krát a EE' je min. TT-join (kde TT je výše definovaná množina).

Důkaz: (👀): nechť GG' vznikne z GG dodáním násobných hran, násobnost je podle počtu procházení minimální trasou PP. Potom GG' má všechny stupně sudé.

Z pozorování plyne (1), jelikož FF spolu s původními hranami dává 22 průchody.

Navíc jelikož E(G)=E(G)FE(G') = E(G) \cup F je TT-join, jelikož přesné splňuje definici (stupně budou liché v GG', protože musí být sudé po přidaní do GG). Navíc E(G)FE(G) \cup \overline{F} rozhodně nebude lepší než minimální cesta čínského pošťáka a tedy naše FF.

Algoritmus (čínský pošťák):

  1. najdi minimální TT-join
    • použij konstrukci (modifikovanou) Fischera z minulé přednášky (GGΔG \mapsto G_\Delta), o čemž víme, že je polynomiální
    • (alternativně) uvažme pomocný graf H=(T,(T2))H = \left(T, \binom{T}{2}\right) a váha w:(T2)Q+w : \binom{T}{2} \mapsto \mathbb{Q}^+, kde w({u,v})=w(\left\{u, v\right\}) = délka nejkratší cesty mezi u,vu, v v GG
      • nechť MM je min. perfektní párování v HH
      • nechť F=eMPeF = \bigcup_{e \in M} P_e, kde PeP_e je nejkratší cesta v GG spojující vrcholy ee
  2. přidej zbylé hrany
  3. profit?

Problém (obchodního cestujícího): předpokládáme

Algoritmus (Christofidesova heuristika): viz moje poznámky z aproximačních algoritmů

Spojitá optimalizace

pěkná skripta.

Zkouška

Na obou částech jsem si vytáhl okruh, o kterém jsem napsal co vím a pak jsem to se zkoušejícím probíral.

Diskrétní část

Zkušební okruhy:

  1. Matroidy: základní definice, příklady.
  2. Řádová funkce a submodularita.
  3. Kontrakce, dualita.
  4. Hladový algoritmus.
  5. Průnik matroidů, obraz, sjednocení.
  6. Edmondsův algoritmus na maximální párování, Tuttova věta.
  7. Problém Obchodního cestujícího a Čínského pošťáka.

Spojitá část

Odkazy

Poděkování