Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

📚 The CoCalc Library - books, templates and other resources

132930 views
License: OTHER
Tweet
Share
Share
1
\documentclass{article}

2
\usepackage[pdftex,active,tightpage]{preview}

3
\setlength\PreviewBorder{2mm}

4


5
\usepackage[utf8]{inputenc} % this is needed for umlauts

6
\usepackage[ngerman]{babel} % this is needed for umlauts

7
\usepackage[T1]{fontenc}    % this is needed for correct output of umlauts in pdf

8
\usepackage{amssymb,amsmath,amsfonts} % nice math rendering

9
\usepackage{braket} % needed for \Set

10
\usepackage{algorithm,algpseudocode}

11


12
\begin{document}

13
\begin{preview}

14
    Sei $S \subseteq V$ und $c:E\rightarrow\mathbb{R}_0^+$ die

15
    Kantengewichtsfunktion.

16
    Für $v \in V \setminus S$ sei:

17


18
        \begin{align*}

19
            c &:\mathcal{P}(V) \times V \rightarrow \mathbb{R}_0^+\\

20
        c(S,v) &:= \sum_{\substack{\Set{u,v} \in E\\ u \in S}} c(\Set{u,v})

21
        \end{align*}

22


23
    Sei nun $d: \mathcal{P}(V) \rightarrow V$ die Funktion, die den

24
    Knoten liefert, der am stärksten mit $S \in \mathcal{P}(V)$

25
    verbunden ist:

26
        \[d(S) := v \in V \setminus S: c(S, v) = \max(\Set{c(S,v) | v \in V \setminus S})\]

27


28
    \begin{algorithm}[H]

29
        \begin{algorithmic}

30
            \Function{StoerWagner}{Network $N(D, s, t, c)$}

31
                \State Graph $G_0 = D$

32
                \State Knoten $a,b,v$

33
                \State Phasenergebnisse $P$ \Comment{Speichert Schnitt und Gewicht}

34
                \For{($i=1$; $\;i<|V|$; $\;i$++)}

35
                    \State Knotenmenge $S_i \gets \Set{}$

36
                    \State $S_i$.add($S_i \in G_i$) \Comment{Wähle einen beliebigen Startknoten}

37
                    \While{$S_i \neq V_{i-1}$}

38
                        \State $v \gets$ \Call{d}{$S_i$}

39
                        \State $S_i$.add($v$)

40
                    \EndWhile

41


42
                    \State $a \gets v$

43
                    \State $b \gets$ \Call{d}{$\Set{a}$}

44
                    \State $V_i \gets$ \Call{Verschmelzen}{$V_{i-1}$, $a$, $b$}

45
                    \State $E_i \gets$ \Call{Verschmelzen}{$E_{i-1}$, $a$, $b$}

46
                    \State $G_i = (V_i, E_i)$

47
                    \State $P$.add($(a, V \setminus a)$, $c(a, V \setminus a)$)

48
                \EndFor

49


50
                \State \Return $P$.getMinimalCut()

51
            \EndFunction

52


53
            \Function{Verschmelzen}{Knotenmenge $V$, Knoten $a$, Knoten $b$}

54
                \State $V$.remove($a$)

55
                \State $V$.remove($b$)

56
                \State \Comment{TODO: was, wenn a und b schon Mengen sind?}

57
                \State $V$.add($\Set{a, b}$)

58
            \EndFunction

59


60
            \Function{Verschmelzen}{Kantenmenge $E$, Knoten $a$, Knoten $b$}

61
                \State \Comment{TODO: Kantengewichtsfunktion muss auch angepasst werden}

62
                \ForAll{Kante $e:=(x,y) \in E$}

63
                    \If{$x == a \lor x == b$}

64
                        \State $E$.remove($e$)

65
                        \State $E$.add($(\Set{a, b},y)$)

66
                    \ElsIf{$y == a \lor y == b$}

67
                        \State $E$.remove($e$)

68
                        \State $E$.add($(x, \Set{a, b})$)

69
                    \EndIf

70
                \EndFor

71
            \EndFunction

72
        \end{algorithmic}

73
    \caption{Algorithmus von Stoer und Wanger}

74
    \label{alg:seq1}

75
    \end{algorithm}

76
\end{preview}

77
\end{document}

78


79