Predavanje 12.4.

Spomnimo se: povečujoča pot sestoji iz premih povezav, ki niso nasičene, in obratnih povezav, ki niso prazne.

Kako najdemo povečujočo pot? Začnemo s $C = \{s\}$, nato pa ponavljamo za vsak $v \in C$: ali obstaja $w \not \in C$, da velja $x_{vw} < d_{vw}$ ali $x_{wv} > 0$ - če obstaja, dodamo $w$ v $C$.

  • Če v nekem koraku dobimo $t \in C$, smo našli povečujočo pot od $s$ do $t$, tako da lahko povečamo pretok.
  • Če v nekem koraku tak $w$ ne obstaja, povečujoče poti ni - našli smo maksimalni pretok $x$ in minimalni prerez $C$.

Običajno problem pretoka rešujemo na pridruženem grafu:

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1

  u1 [label=u]
  v1 [label=v]
  x1 [style=invis]
  x2 [style=invis]
  u2 [label=u]
  v2 [label=v]

  u1 -> v1 [taillabel=<d<sub>uv</sub>>]
  v1 -> x1 [style=invis]
  x1 -> x2
  x2 -> u2 [style=invis]
  u2 -> v2 [taillabel=<d<sub>uv</sub> - x<sub>uv</sub>>, headlabel=<x<sub>uv</sub>>, arrowhead=none]
}

Primer.

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]

  SFO [xlabel=s]
  JFK [xlabel=t]

  SFO -> DEN [headlabel=" 0  ", taillabel=5]
  SFO -> IAH [headlabel=" 0  ", taillabel=6, color=red]
  DEN -> ATL [headlabel="0      ", taillabel=2]
  DEN -> ORD [headlabel=0, taillabel=5]
  IAH -> ATL [headlabel=0, taillabel=<<font color="red">5</font>>, color=red]
  ATL -> JFK [headlabel=0, taillabel=7, color=red]
  ORD -> JFK [headlabel=0, taillabel=4]
}

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]

  SFO [xlabel=s]
  JFK [xlabel=t]

  SFO -> DEN [headlabel="0  ", taillabel=5, color=red]
  SFO -> IAH [headlabel="5  ", taillabel=1]
  DEN -> ATL [headlabel="0      ", taillabel=2]
  DEN -> ORD [headlabel=0, taillabel=5, color=red]
  IAH -> ATL [headlabel=5, taillabel=0, style=bold]
  ATL -> JFK [headlabel=5, taillabel=2]
  ORD -> JFK [headlabel=0, taillabel=<<font color="red">4</font>>, color=red]
}

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]

  SFO [xlabel=s]
  JFK [xlabel=t]

  SFO -> DEN [headlabel=" 4  ", taillabel=<<font color="red">1</font>>, color=red]
  SFO -> IAH [headlabel=" 5  ", taillabel=1]
  DEN -> ATL [headlabel="0      ", taillabel=2, color=red]
  DEN -> ORD [headlabel=4, taillabel=1]
  IAH -> ATL [headlabel=5, taillabel=0, style=bold]
  ATL -> JFK [headlabel=5, taillabel=2, color=red]
  ORD -> JFK [headlabel=4, taillabel=0, style=bold]
}

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]

  SFO [xlabel=s, style=filled]
  IAH [style=filled]
  JFK [xlabel=t]

  SFO -> DEN [headlabel=" 5  ", taillabel=0, style=bold, color=blue]
  SFO -> IAH [headlabel=" 5  ", taillabel=1]
  DEN -> ATL [headlabel="1      ", taillabel=1]
  DEN -> ORD [headlabel=4, taillabel=1]
  IAH -> ATL [headlabel=5, taillabel=0, style=bold, color=blue]
  ATL -> JFK [headlabel=6, taillabel=1]
  ORD -> JFK [headlabel=4, taillabel=0, style=bold]
}
  • Prostornina pretoka: $F = 5 + 5 = 6 + 4 = 10$
  • Kapaciteta prereza: $K = 5 + 5 = 10$

Optimalna rešitev:

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]

  SFO [xlabel=s, style=filled]
  IAH [style=filled]
  JFK [xlabel=t]

  SFO -> DEN [label=5, style=bold, color=blue]
  SFO -> IAH [label=5]
  DEN -> ATL [label=1]
  DEN -> ORD [label=4]
  IAH -> ATL [label=5, style=bold, color=blue]
  ATL -> JFK [label=6]
  ORD -> JFK [label=4, style=bold]
}

Opomba. Ali se Ford-Fulkersonov algoritem vedno ustavi? NE. Obstajajo primeri, kjer lahko (če "nerodno" izbiramo povečujoče poti) v neskončno ponavljamo postopek (če so nekatere pretočnosti iracionalne), pri čemer prostornina pretoka konvergira proti številu, ki je manjše od prostornine maksimalnega pretoka. Da zagotovimo, da se algoritem ustavi, v vsakem koraku izberemo najkrajšo povečujočo pot (Edmonds-Karpov algoritem).

Opomba. Disjunktne povečujoče poti (po povezavah) lahko obravnavamo hkrati, npr.

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]

  SFO [xlabel=s]
  JFK [xlabel=t]

  SFO -> DEN [headlabel=" 0  ", taillabel=5, color=green]
  SFO -> IAH [headlabel=" 0  ", taillabel=6, color=red]
  DEN -> ATL [headlabel="0      ", taillabel=2]
  DEN -> ORD [headlabel=0, taillabel=5, color=green]
  IAH -> ATL [headlabel=0, taillabel=<<font color="red">5</font>>, color=red]
  ATL -> JFK [headlabel=0, taillabel=7, color=red]
  ORD -> JFK [headlabel=0, taillabel=<<font color="green">4</font>>, color=green]
}

Prirejanja in pokritja

Definicija. Naj bo $G = (V, E)$ neusmerjen graf. Množici $M \subseteq E$ pravimo prirejanje (angl. matching), č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$).

Primeri.

  • Prirejanje:

    graph G {
rankdir=LR
nodesep=0.5
ranksep=1
node [label=""]

a -- b [color=red]
a -- c
b -- c [constraint=false]
b -- d
c -- e [style=invis]
d -- e [color=red,constraint=false]
d -- f
e -- f
}

  • Ni prirejanje:

    graph G {
rankdir=LR
nodesep=0.5
ranksep=1
node [label=""]

a -- b [color=red]
a -- c
b -- c [constraint=false]
b -- d
c -- e [style=invis]
d -- e [color=red,constraint=false]
d -- f [color=red]
e -- f
}

  • Popolno prirejanje:

    graph G {
rankdir=LR
nodesep=0.5
ranksep=1
node [label=""]

a -- b
a -- c [color=red]
b -- c [constraint=false]
b -- d [color=red]
c -- e [style=invis]
d -- e [constraint=false]
d -- f
e -- f [color=red]
}

Trditev. Če ima $G = (V, E)$ popolno prirejanje, je $|V|$ soda.

Definicija. Naj bo $G = (V, E)$ neusmerjen graf. Množici $C \subseteq V$ pravimo pokritje (angl. vertex cover), če ima vsaka povezava iz $E$ krajišče v $C$ (tj., $\forall e \in E: e \cap C \ne \emptyset$).

Primeri.

  • Pokritje:

    graph G {
rankdir=LR
nodesep=0.5
ranksep=1
node [label="", style=filled, fillcolor=red]

a [style=empty]

a -- b
a -- c
b -- c [constraint=false]
b -- d
c -- e [style=invis]
d -- e [constraint=false]
d -- f
e -- f
}

  • Ni pokritje:

    graph G {
rankdir=LR
nodesep=0.5
ranksep=1
node [label="", fillcolor=red]

a [style=filled]
b [style=filled]
e [style=filled]

a -- b
a -- c
b -- c [constraint=false]
b -- d
c -- e [style=invis]
d -- e [constraint=false]
d -- f
e -- f
}

  • (Najmanjše) pokritje:

    graph G {
rankdir=LR
nodesep=0.5
ranksep=1
node [label="", style=filled, fillcolor=red]

a [style=empty]
e [style=empty]

a -- b
a -- c
b -- c [constraint=false]
b -- d
c -- e [style=invis]
d -- e [constraint=false]
d -- f
e -- f
}

Iščemo čim večje prirejanje in čim manjše pokritje.

  • $\mu(G)$ ... velikost največjega prirejanja v $G$
  • $\tau(G)$ ... velikost najmanjšega pokritja v $G$

Primera.

  • $G_1 = (V_1, E_1)$, $|V_1| = 6$:

    graph G1 {
rankdir=LR
nodesep=0.5
ranksep=1
node [label=""]

a -- d
b -- d [color=red]
c -- d
d -- e
d -- f

d [style=filled, fillcolor=red]
}
    • $\mu(G_1) = 1$
    • $\tau(G_1) = 1$

  • $G_2$:

    graph G2 {
rankdir=LR
nodesep=0.5
ranksep=1
node [label="", style=filled, fillcolor=red]

a [style=empty]
e [style=empty]

a -- b
a -- c [color=red]
b -- c [constraint=false]
b -- d [color=red]
c -- e [style=invis]
d -- e [constraint=false]
d -- f
e -- f [color=red]
}
    • $\mu(G_2) = 3$
    • $\tau(G_2) = 4$

Trditev. Naj bo $M$ prirejanje in $C$ pokritje v grafu $G$. Potem velja $|M| \le |C|$.

Posledica. Če velja $|M| = |C|$, potem je $M$ največje prirejanje in $C$ najmanjše pokritje v $G$.

Posledica. Za vsak graf $G$ velja $\mu(G) \le \tau(G)$.

Opomba. Lahko se zgodi, da velja $\mu(G) < \tau(G)$. Za dvodelne grafe velja $\mu(G) = \tau(G)$ (dokaz kasneje).

Dokaz. Ker ima vsaka povezava iz $M$ vsaj eno krajišče v $C$, obstaja preslikava $f : M \to C$, za katero velja $\forall e \in M: f(e) \in e \cap C$. Ker je vsako vozlišče iz $C$ krajišče največ ene povezave iz $M$, je preslikava $f$ injektivna, od koder sledi $|M| \le |C|$.

Definicija. Naj bo $M$ prirejanje v grafu $G = (V, E)$. Rečemo, da je

  • vozlišče $v \in V$
    • prosto, če $\lnot \exists e \in M: v \in e$, in
    • vezano, če $\exists e \in M: v \in e$;
  • povezava $e \in E$
    • prosta, če $e \not\in M$, in
    • vezana, če $e \in M$; ter
  • pot v $G$
    • izmenična (alternirajoča), če se v njej izmenjujejo proste in vezane povezave, in
    • povečujoča, če je izmenična ter se začne in konča s prostim vozliščem.

Če na povečujoči poti zamenjamo proste in vezane povezave, se prirejanje poveča:

graph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]

  a -- b
  b -- c [color=red]
  c -- d
  d -- e [color=red]
  e -- f
}

graph H {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]

  a -- b [color=red]
  b -- c
  c -- d [color=red]
  d -- e
  e -- f [color=red]
}

Definicija. Simetrična vsota množic $A$ in $B$ je $$ A \oplus B := (A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A) . $$

Trditev. Če je $M$ prirejanje v $G$ in $P$ povečujoča pot z množico povezav $E(P)$, je $M' = M \oplus E(P)$ prirejanje v $G$ in $|M'| = |M| + 1$.

Trditev (Berge). Naj bo $M$ prirejanje v grafu $G$. Potem je $M$ največje prirejanje v $G$ natanko tedaj, ko zanj ne obstaja povečujoča pot.

Dokaz. Dokazujemo enakovredno izjavo: $M$ ni največje prirejanje v $G = (V, E)$ natanko tedaj, ko zanj obstaja povečujoča pot.

  • $(\Longleftarrow)$ Sledi iz prejšnje trditve.

  • $(\Longrightarrow)$ Denimo, da $M$ ni največje prirejanje v $G$. Potem obstaja prirejanje $M'$ v $G$, za katerega velja $|M'| > |M|$. Potem je $H = (V, M \oplus M')$ graf z maksimalno stopnjo $\Delta_H \le 2$ - njegove povezane komponente so poti in sodi cikli.

    graph H {
rankdir=LR
nodesep=0.5
ranksep=1
node [label=""]

a -- b [label=<<i>M</i>>]
a -- c [label=<<i>M'</i>>]
b -- d [label=<<i>M'</i>>]
c -- e [label=<<i>M</i>>]
d -- f [label=<<i>M</i>>]
e -- f [label=<<i>M'</i>>]
g -- h [label=<<i>M</i>>]
h -- i [label=<<i>M'</i>>]
j -- k [label=<<i>M</i>>]
k -- l [label=<<i>M'</i>>]
l -- m [label=<<i>M</i>>]
n -- o [label=<<i>M'</i>>]
o -- p [label=<<i>M</i>>]
p -- q [label=<<i>M'</i>>]
}

    Ker je $|M'| > |M|$, obstaja v $H$ pot $P$, katere prva in zadnja povezava sta v $M'$. Trdimo, da je $P$ povečujoča pot za $M$:

    • je alternirajoča, saj $E(P) \cap M' \subseteq M \oplus M'$ in zato $E(P) \cap M' \cap M = \emptyset$;
    • začne in konča se s prostim vozliščem: denimo, da je $u$ krajišče poti $P$ in ni prosto za $M$ - potem obstaja povezava $uv \in M \setminus (M \oplus M') = M \cap M'$, kar je v protislovju s predpostavko, da je $M'$ prirejanje.

Zadnja sprememba: torek, 12 april 2022, 14:25 PM