Optimizacijske metode

Iskanje največjega prirejanja se torej prevede na iskanje povečujočih poti. Če je graf $G = (V, E)$ dvodelen ($V = X + Y$, $X \cap Y = \emptyset$, $\forall e \in E: (e \cap X \ne \emptyset \land e \cap Y \ne \emptyset)$; ekvivalentno, v $G$ ni lihih ciklov), povečujočo pot poiščemo z madžarsko metodo.

• Naj bo $G = (X + Y, E)$ dvodelen graf in $M$ prirejanje v $G$. Postavimo množico prostih vozlišč v $X$ kot množico $S$ in $T := \emptyset$.
• Ponavljamo:
  • $T := T \cup \{v \in Y \mid u \in S, uv \not\in M \}$
  • $S := S \cup \{u \in X \mid v \in T, uv \in M\}$
• Če je v $T$ v nekem trenutku prosto vozlišče, smo našli povečujočo pot. Postopek ustavimo in povečamo prirejanje (in začnemo od začetka).
• Sicer sta v nekem trenutku nova $S$ in $T$ enaka starima.

Izrek. Če sta nova $S$ in $T$ enaka starima, potem je $M$ največje prirejanje, $C := (X \setminus S) + T$ je najmanjše pokritje, in $|M| = |C| = \mu(G) = \tau(G)$.

Dokaz. Trdimo:

• med $S$ in $Y \setminus T$ ni prostih povezav (sicer bi lahko povečali $T$)
• med $S$ in $Y \setminus T$ ni vezanih povezav (do $S$ vodijo vezane povezave samo iz $T$)
• med $X \setminus S$ in $T$ ni vezanih povezav (sicer bi lahko povečali $S$)

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

  S [label=<<i>S</i>>]
  T [label=<<i>T</i>>]
  XS [label=<<i>X \ S</i>>]
  YT [label=<<i>Y \ T</i>>]

  S -- T [color=red, label=<<i>M<sub>1</sub></i>>]
  S -- T
  XS -- T
  XS -- YT
  XS -- YT [color=red, label=<<i>M<sub>2</sub></i>>]
  S -- YT [style=invis]
}

Množica $C := (X \setminus S) + T$ je torej pokritje. Definirajmo še množico $M_1$ vezanih povezav med $S$ in $T$ ter množico $M_2$ vezanih povezav med $X \setminus S$ in $Y \setminus T$. Potem je $M = M_1 + M_2$ ter velja $|M_1| = |T|$ (sicer je v $T$ prosto vozlišče) in $|M_2| = |X \setminus S|$ (vsa prosta vozlišča iz $X$ so v $S$). Velja torej $$ |M| = |M_1| + |M_2| = |T| + |X \setminus S| = |C|. $$ $M$ je torej največje prirejanje, $C$ pa najmanjše pokritje.

Primer.

digraph G {
  rankdir=RL
  nodesep=0.5
  ranksep=1
  node [label=""]
  edge [arrowhead=none]

  e -> a [style=invis]
  f -> a [color=red]
  e -> b
  g -> b [color=red]
  h -> b
  i -> b
  f -> c
  g -> c [style=invis]
  h -> c [color=red]
  g -> d [color=blue,arrowhead=normal]
  h -> d [color=blue,arrowhead=normal]
  Y -> X [style=invis]

  X [label=<<i>X</i>>,color=none]
  Y [label=<<i>Y</i>>,color=none]
  d [xlabel=<<i>S</i>>]
  g [xlabel=<<i>T</i>>]
  h [xlabel=<<i>T</i>>]
}

digraph G {
  rankdir=RL
  nodesep=0.5
  ranksep=1
  node [label=""]
  edge [arrowhead=none]

  e -> a [style=invis]
  f -> a [color=red]
  e -> b [color=blue,arrowhead=normal]
  g -> b [color=red]
  h -> b [color=blue,arrowhead=normal]
  i -> b [color=blue,arrowhead=normal]
  f -> c [color=blue,arrowhead=normal]
  g -> c [style=invis]
  h -> c [color=red]
  g -> d [arrowhead=normal]
  h -> d [arrowhead=normal]
  Y -> X [style=invis]

  X [label=<<i>X</i>>,color=none]
  Y [label=<<i>Y</i>>,color=none]

  d [xlabel=<<i>S</i>>]
  g [xlabel=<<i>T</i>>]
  h [xlabel=<<i>T</i>>]
  b [xlabel=<<i>S</i>>]
  c [xlabel=<<i>S</i>>]
  e [xlabel=<<i>T</i>>]
  f [xlabel=<<i>T</i>>]
  i [xlabel=<<i>T</i>>]
}

Imamo prosto vozlišče v $T$, torej smo našli povečujočo pot.

digraph G {
  rankdir=RL
  nodesep=0.5
  ranksep=1
  node [label="", fillcolor=red]
  edge [arrowhead=none]

  e -> a [style=invis]
  f -> a [color=red]
  e -> b [color=red]
  g -> b
  h -> b
  i -> b
  f -> c
  g -> c [style=invis]
  h -> c [color=red]
  g -> d [color=red]
  h -> d
  Y -> X [style=invis]

  X [label=<<i>X</i>>,color=none]
  Y [label=<<i>Y</i>>,color=none]
  a [style=filled]
  b [style=filled]
  c [style=filled]
  d [style=filled]
}

Ni več prostih vozlišč v $X$, torej imamo največje prirejanje in najmanjše pokritje $C = X$.

V posebnem (za dvodelne grafe) velja torej Kőnig-Egerváryjev izrek. Za dvodelen graf $G$ velja $\mu(G) = \tau(G)$.

Opomba. Obstaja tudi algoritem za iskanje povečujoče poti v splošnem grafu: Edmondsov algoritem (angl. tudi blossom algorithm). Ta algoritem je "učinkovit", torej polinomski.