Prop£¤deutikum Diskrete Mathematik (MA 1503) - Fl£¼sse und ... Prop£¤deutikum Diskrete Mathematik (MA

  • View
    0

  • Download
    0

Embed Size (px)

Text of Prop£¤deutikum Diskrete Mathematik (MA 1503) - Fl£¼sse und ......

  • Propädeutikum Diskrete Mathematik (MA 1503) Flüsse und der Algorithmus von Ford und Fulkerson

    Tina Janne Schmidt

    Technische Universität München

    Wintersemester 2012/2013

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 1

  • Gerichtete Graphen

    Definition gerichteter Graph G = (V,A) ist ein gerichteter Graph, wenn A ⊂ V × V (und nicht E ⊂

    ( V 2

    ) ).

    Definiere N−(x) = {y ∈ V : (y, x) ∈ A} und N+(x) = {y ∈ V : (x, y) ∈ A}.

    In A sind Tupel, deren Elemente eine Reihenfolge haben, enthalten, in E Mengen. D.h. eine Kante eines gerichteten Graphen hat einen Anfangs- und einen Endknoten, z.B. wird die Kante (a, b) durch einen Pfeil von a nach b dargestellt. In gerichteten Graphen ist (a, b) 6= (b, a); in ungerichteten Graphen ist {v, w} = {w, v}. In gerichteten Graphen sind Kanten von einem Knoten zu sich selbst möglich, z.B. (a, a); in ungerichteten Graphen gibt es keine Kanten der Form {v, v}.

    e

    a

    d

    b

    c

    A = {(a, b), (a, e), (b, c), (b, e), (c, c), (c, d), (e, b), (e, d)}

    N+(a) = {b, e}, N−(d) = {e, c}

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 2

  • Netzwerke und Flüsse

    Definition Netzwerk Ein Netzwerk ist ein Tupel N = (V,A, s, t, c), wobei (V,A, c) ein gerichteter Graph mit Kapazitätsfunktion c : A→ R≥0 ist, s ∈ V Quelle und t ∈ V Senke zwei ausgezeichnete Knoten sind.

    Definition Fluss Sei N = (V,A, s, t, c) ein Netzwerk. Eine Abbildung f : A→ R≥0 heißt s, t-Fluss (flow) in N , wenn

    1 Flusserhaltung∑ y∈N−(x)

    f((y, x)) = ∑

    y∈N+(x)

    f((x, y)) ∀ x ∈ V \ {s, t}

    2 Zulässigkeit f((x, y)) ≤ c((x, y)) ∀ (x, y) ∈ A.

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 3

  • Netzwerke und Flüsse

    Definition Netzwerk Ein Netzwerk ist ein Tupel N = (V,A, s, t, c), wobei (V,A, c) ein gerichteter Graph mit Kapazitätsfunktion c : A→ R≥0 ist, s ∈ V Quelle und t ∈ V Senke zwei ausgezeichnete Knoten sind.

    Definition Fluss Sei N = (V,A, s, t, c) ein Netzwerk. Eine Abbildung f : A→ R≥0 heißt s, t-Fluss (flow) in N , wenn

    1 Flusserhaltung∑ y∈N−(x)

    f((y, x)) = ∑

    y∈N+(x)

    f((x, y)) ∀ x ∈ V \ {s, t}

    2 Zulässigkeit f((x, y)) ≤ c((x, y)) ∀ (x, y) ∈ A.

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 3

  • Netzwerke und Flüsse - Beispiel

    gerichteter Graph mit zwei ausgezeichneten Knoten

    Kapazitätsobergrenze c : A→ R≥0

    s, t- Fluss f : A→ R≥0

    s t

    a b

    c d

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

  • Netzwerke und Flüsse - Beispiel

    gerichteter Graph mit zwei ausgezeichneten Knoten

    Kapazitätsobergrenze c : A→ R≥0

    s, t- Fluss f : A→ R≥0

    s t

    a b

    c d

    1

    4

    2

    3

    2

    4

    1

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

  • Netzwerke und Flüsse - Beispiel

    gerichteter Graph mit zwei ausgezeichneten Knoten

    Kapazitätsobergrenze c : A→ R≥0

    s, t- Fluss f : A→ R≥0

    s t

    a b

    c d

    1

    4

    2

    3

    2

    4

    1

    1/

    3/

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

  • Netzwerke und Flüsse - Beispiel

    gerichteter Graph mit zwei ausgezeichneten Knoten

    Kapazitätsobergrenze c : A→ R≥0

    s, t- Fluss f : A→ R≥0

    s t

    a b

    c d

    1

    4

    2

    3

    2

    4

    1

    1/

    3/ 1/

    2/

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

  • Netzwerke und Flüsse - Beispiel

    gerichteter Graph mit zwei ausgezeichneten Knoten

    Kapazitätsobergrenze c : A→ R≥0

    s, t- Fluss f : A→ R≥0

    s t

    a b

    c d

    1

    4

    2

    3

    2

    4

    1

    1/

    3/

    1/

    1/

    2/

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

  • Netzwerke und Flüsse - Beispiel

    gerichteter Graph mit zwei ausgezeichneten Knoten

    Kapazitätsobergrenze c : A→ R≥0

    s, t- Fluss f : A→ R≥0

    s t

    a b

    c d

    1

    4

    2

    3

    2

    4

    1

    1/

    3/

    1/

    1/

    2/

    1/

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

  • Netzwerke und Flüsse - Beispiel

    gerichteter Graph mit zwei ausgezeichneten Knoten

    Kapazitätsobergrenze c : A→ R≥0

    s, t- Fluss f : A→ R≥0

    s t

    a b

    c d

    1

    4

    2

    3

    2

    4

    1

    1/

    3/

    1/

    1/

    2/

    3/

    1/

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

  • Flüsse Vereinbarung: Schreibe f(x, y) statt f((x, y)) und c(x, y) statt c((x, y)).

    Bemerkung: In Zukunft gehen wir davon aus, dass für alle x, y ∈ V gilt

    f(x, y) > 0 ⇒ f(y, x) = 0.

    a b c d

    4

    3

    a b c d

    1

    0

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 5

  • Flüsse Vereinbarung: Schreibe f(x, y) statt f((x, y)) und c(x, y) statt c((x, y)).

    Bemerkung: In Zukunft gehen wir davon aus, dass für alle x, y ∈ V gilt

    f(x, y) > 0 ⇒ f(y, x) = 0.

    a b c d

    4

    3

    a b c d

    1

    0

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 5

  • Flüsse Vereinbarung: Schreibe f(x, y) statt f((x, y)) und c(x, y) statt c((x, y)).

    Bemerkung: In Zukunft gehen wir davon aus, dass für alle x, y ∈ V gilt

    f(x, y) > 0 ⇒ f(y, x) = 0.

    a b c d

    4

    3

    a b c d

    1

    0

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 5

  • Wert eines Flusses

    Definition Wert Der Wert eines Flusses f ist definiert als

    val(f) = ∑

    y∈N+(s)

    f(s, y) − ∑

    y∈N−(s)

    f(y, s).

    Der Fluss f hat maximalen Wert im Netzwerk N , wenn val(f) ≥ val(f ′) für alle Flüsse f ′ in N gilt.

    s t

    a b

    c d

    1

    4

    2

    3

    2

    4

    1

    1/

    3/

    1/

    1/

    2/

    3/

    1/

    val(f) = (3 + 1)− 0 = 4

    Proposition Jedes Netzwerk besitzt einen Fluss maximalen Werts.

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 6

  • Wert eines Flusses

    Definition Wert Der Wert eines Flusses f ist definiert als

    val(f) = ∑

    y∈N+(s)

    f(s, y) − ∑

    y∈N−(s)

    f(y, s).

    Der Fluss f hat maximalen Wert im Netzwerk N , wenn val(f) ≥ val(f ′) für alle Flüsse f ′ in N gilt.

    s t

    a b

    c d

    1

    4

    2

    3

    2

    4

    1

    1/

    3/

    1/

    1/

    2/

    3/

    1/

    val(f) = (3 + 1)− 0 = 4

    Proposition Jedes Netzwerk besitzt einen Fluss maximalen Werts.

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 6

  • Wert eines Flusses

    Definition Wert Der Wert eines Flusses f ist definiert als

    val(f) = ∑

    y∈N+(s)

    f(s, y) − ∑

    y∈N−(s)

    f(y, s).

    Der Fluss f hat maximalen Wert im Netzwerk N , wenn val(f) ≥ val(f ′) für alle Flüsse f ′ in N gilt.

    s t

    a b

    c d

    1

    4

    2

    3

    2

    4

    1

    1/

    3/

    1/

    1/

    2/

    3/

    1/

    val(f) = (3 + 1)− 0 = 4

    Proposition Jedes Netzwerk besitzt einen Fluss maximalen Werts.

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 6

  • Restnetzwerk

    Definition Restnetzwerk Sei N = (V,A, s, t, c) ein Netzwerk und f ein Fluss in N . Wir erweitern zunächst die Kapazitätsfunktion zu c : V × V → R≥0 durch c(x, y) = 0 für alle (x, y) /∈ A. Das Restnetzwerk Nf = (V,Af , s, t, cf ) ist definiert durch Af = {(x, y) : cf (x, y) > 0} und

    cf (x, y) =

     c(x, y)− f(x, y), falls f(x, y) > 0c(x, y) + f(y, x), falls f(y, x) > 0 c(x, y), sonst.

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 7

  • Restnetzwerk - Beispiel

    cf (x, y) =

     c(x, y)− f(x, y), falls f(x, y) > 0c(x, y) + f(y, x), falls f(y, x) > 0 c(x, y), sonst.

    Kapazitätsobergrenze c : A→ R≥0

    s, t- Fluss f : A→ R≥0

    s t

    x

    y

    5

    5

    1

    55

    5

    2

    Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 8

  • Restnetzwerk - Beispiel

    cf (x, y) =

     c(x, y)− f(x, y), falls f(x, y) > 0c(x, y) + f(y, x), falls f(y, x) > 0 c(x, y), sonst.

    Kapazitätsobergrenze c : A→ R≥0

    s, t- Fluss f : A→ R≥0