2WO12: Optimalisering in Netwerken

2WO12: Optimalisering in Netwerken Leo van Iersel Technische Universiteit Eindhoven (TU/E) en Centrum Wiskunde & Informatica (CWI)

27 februari 2014

http://homepages.cwi.nl/~iersel/2WO12/ [email protected]

Leo van Iersel (TUE/CWI)

2WO12: Optimalisering in Netwerken

27 februari 2014

1 / 34

Overzicht

Tot nog toe: grafen, kleuren en routeren graafrepresentaties en complexiteit kortste pad algoritmes Vandaag minimum opspannende bomen Pr¨ ufer reeksen fylogenetische bomen



27 februari 2014

2 / 34

Definitie Een bos is een graaf zonder circuits. Een boom is een samenhangend bos.

Definitie Laat G = (V , E ) een graaf zijn. Een opspannende boom (spanning tree) van G is een boom T = (V , F ) met F ⊆ E . Anders gezegd, een opspannende boom van G is een deelgraaf van G die alle punten van G opspant (verbindt) en geen circuits bevat.



27 februari 2014

3 / 34

Voorbeeld Een opspannende boom van de Petersen graaf (in zwart):



27 februari 2014

4 / 34

Voorbeeld Een andere opspannende boom van de Petersen graaf (in zwart):



27 februari 2014

5 / 34

Probleem Minimum Opspannende Boom (Minimum Spanning Tree) Gegeven: samenhangende graaf G = (V , E ) en lengtefunctie `:E →R Vind: een opspannende boom T = (V , F ) van G met minimale lengte X `(e) e∈F

Elke samenhangende graaf heeft een opspannende boom.



27 februari 2014

6 / 34

Prim-Dijkstra methode voor het vinden van een minimum opspannende boom van een samenhangende graaf G = (V , E ) en lengtefunctie `:E →R

Definitie δ(U) is de verzameling lijnen die precies één eindpunt in U hebben

Algoritme Kies willekeurig punt v1 U1 := {v1 } F1 := ∅ Voor k = 1, 2, . . . , |V | − 1 I I I

Kies een lijn ek ∈ δ(Uk ) met minimale lengte Uk+1 := Uk ∪ ek Fk+1 := Fk ∪ {ek }

Stelling (V , F|V | ) is een minimum opspannende boom van G Leo van Iersel (TUE/CWI)


27 februari 2014

7 / 34

Voorbeeld Vind een minimum opspannende boom in de volgende graaf m.b.v. de Prim-Dijkstra methode:

3 2

6

3 2 5

3

4

5

3

4 1

3

4

5

9 Leo van Iersel (TUE/CWI)

4

7


8

3 6 27 februari 2014

8 / 34

Lemma (1) De volgende uitspraken zijn equivalent voor een graaf G = (V , E ): 1

G is een boom (is samenhangend en bevat geen circuit)

2

G is samenhangend en |E | = |V | − 1

3

G bevat geen circuit en |E | = |V | − 1

4

G bevat een uniek pad tussen elk tweetal punten



27 februari 2014

9 / 34

Lemma (2) Als G = (V , E ) samenhangend is, (V , F ) een opspannende boom van G en e ∈ E \ F dan zijn de volgende twee uitspraken waar: 1

F ∪ {e} bevat een uniek circuit C

2

als f een lijn is van C , dan is F \ {f } ∪ {e} een opspannende boom van G

e f

Voorbeeld: lijn e toevoegen geeft een uniek circuit; lijn f weglaten geeft weer een opspannende boom. Leo van Iersel (TUE/CWI)


27 februari 2014

10 / 34

Definitie (V , F ) is een bos van G = (V , E ) als F ⊆ E en (V , F ) een bos is.

Definitie Een bos (V , F ) van G heet gulzig (greedy) als er een opspannende boom van minimale lengte bestaat die alle lijnen van F bevat. Een opspannende boom die gulzig is heeft dus minimale lengte

Stelling (1.11) Laat (V , F ) een gulzig bos zijn van G = (V , E ) en U een component van (V , F ). Als e een lijn met minimale lengte is over alle lijnen in δ(U), dan is (V , F ∪ {e}) weer een gulzig bos.

Stelling Het algoritme van Prim-Dijkstra vindt een minimum opspannende boom. Leo van Iersel (TUE/CWI)


27 februari 2014

11 / 34

Stelling Het algoritme van Prim-Dijkstra vindt een minimum opspannende boom in tijd O(|V |2 ).

Bewijs Houd voor elk punt v ∈ V \ Uk de lengte f (v ) bij van een kortste lijn {u, v } met u ∈ Uk . Er zijn |V | iteraties. In elke iteratie is er O(|V |) tijd nodig om een punt v ∈ V \ Uk met minimale f (v ) te vinden. In elke iteratie is er O(|V |) tijd nodig om de labels van de buren van dit punt v aan te passen.

Stelling Het algoritme van Prim-Dijkstra ge¨ımplementeerd met Fibonacci Heaps lost het minimum opspannende boom probleem op in tijd O(|E | + |V | log(|V |)). Leo van Iersel (TUE/CWI)


27 februari 2014

12 / 34

Kruskals methode voor het vinden van een minimum opspannende boom van een samenhangende graaf G = (V , E ) met lengtefunctie ` : E → R.

Algoritme F := ∅ Voor k = 1, 2, . . . , |V | − 1 I

I

Kies een lijn ek ∈ E \ F met minimale lengte waarvoor (V , F ∪ {ek }) een bos is F := F ∪ {ek }

Stelling Kruskals algoritme vindt een minimum opspannende boom (V , F ) van G .

Stelling Kruskals algoritme kan ge¨ımplementeerd worden zodat de looptijd O(|E | log(|V |)) is.



27 februari 2014

13 / 34

Voorbeeld Vind een opspannende boom in de volgende graaf m.b.v. Kruskals algoritme:

3 2

6

3 2 5

3

4

5

3

4 1

3

4

5


4

7


8

3 6 27 februari 2014

14 / 34

Bor˚ uvka’s methode voor het vinden van een minimum opspannende boom van een samenhangende graaf G = (V , E ) met lengtefunctie ` : E → R. Neem voor het gemak aan dat alle lijnen verschillende lengtes hebben.

Algoritme F := ∅ while |F | < |V | − 1 I I

laat U1 , . . . , Uk de componenten van (V , F ) zijn voor i = 1, . . . , k F

I

kies een lijn ei ∈ δ(Ui ) van minimum lengte

F := F ∪ {e1 , . . . , ek }

Stelling Bor˚ uvka’s algoritme vindt een minimum opspannende boom (V , F ) van G .

Stelling Bor˚ uvka’s algoritme kan ge¨ımplementeerd worden zodat de looptijd O(|E | log(|V |)) is. Leo van Iersel (TUE/CWI)


27 februari 2014

15 / 34

Voorbeeld Vind een opspannende boom in de volgende graaf m.b.v. Bor˚ uvka’s methode:

27 4

6

13 2

5

11

19

14

12

16

1

10

31

21


17

7


25

3 20 27 februari 2014

16 / 34

Lemma (cut property) Als G = (V , E ) een graaf is, ` : E → R, U ⊂ V en e een lijn met `(e) < `(f )

∀f ∈ δ(U) met f 6= e

dan bevat elke minimum opspannende boom voor G de lijn e.

Lemma (cycle property) Als G = (V , E ) een graaf is, ` : E → R en e een lijn in een circuit C met `(e) > `(f )

∀f in C met f 6= e

dan bevat geen enkele minimum opspannende boom voor G de lijn e.



27 februari 2014

17 / 34

Probleem Minimum Bottleneck Opspannende Boom Gegeven: samenhangende graaf G = (V , E ) en lengtefunctie `:E →R Vind: een opspannende boom T = (V , F ) van G waarvoor max `(e) minimaal is. e∈F

Stelling Elke minimum opspannende boom is een minimum bottleneck opspannende boom.



27 februari 2014

18 / 34

Stelling (Formule van Cayley) Het aantal verschillende bomen met n gelabelde punten is nn−2 .

Alle 22−2 = 1 bomen met 2 punten, alle 33−2 = 3 bomen met 3 punten en alle 44−2 = 16 bomen met 4 punten. Leo van Iersel (TUE/CWI)


27 februari 2014

19 / 34

Definitie Een Pr¨ ufer reeks is een reeks van lengte n − 2 bestaande uit getallen uit {1, . . . , n} Gegeven een gelabelde boom T , kun je als volgt een unieke Pr¨ ufer reeks bepalen: Laat 1, 2, . . . , n de labels van de punten van T zijn. Een blad is een punt met graad één.

Algoritme Vind het blad b met kleinste label; voeg de buur van b toe aan de Pr¨ ufer reeks; verwijder b uit de boom; herhaal de voorgaande stappen totdat er twee punten over zijn.



27 februari 2014

20 / 34

Algoritme Vind het blad b met kleinste label; voeg de buur van b toe aan de Pr¨ ufer reeks; verwijder b uit de boom; herhaal de voorgaande stappen totdat er twee punten over zijn.

Voorbeeld Vind de Pr¨ ufer reeks van de onderstaande boom.

8

1 3 6 Leo van Iersel (TUE/CWI)

4

2 5 7


27 februari 2014

21 / 34

Gegeven een Pr¨ ufer reeks a = (a1 , a2 , . . . , an−2 ), kun je als volgt een unieke gelabelde boom bepalen:

Algoritme L := (1, 2, . . . , n) Creëer punten met labels 1, 2, . . . , n Herhaal de volgende stappen totdat |L| = 2 I

Laat ` het eerste label in L zijn dat niet in a voor komt

I

Laat a1 het eerste element van a zijn

I

Verbind het punt met label ` met het punt met label a1

I

Verwijder ` uit L en a1 uit a

Laat L = {`1 , `2 } Verbind het punt met label `1 met het punt met label `2



27 februari 2014

22 / 34

Stelling Er is een bijectie tussen bomen met puntlabels 1, . . . , n en Pr¨ ufer reeksen van lengte n − 2.

Stelling (Formule van Cayley) Het aantal verschillende bomen met n gelabelde punten is nn−2 .



27 februari 2014

23 / 34

Fylogenetische bomen en splits Definitie Gegeven een verzameling labels X , een fylogenetische boom T op X is een boom zonder punten van graad 2 waarvan de bladeren bijectief zijn gelabelled met de elementen van X .

Definitie A|B is een split over X als {A, B} een partitie van X is, d.w.z. als A ∩ B = ∅ en A ∪ B = X . A|B = B|A

Definitie Laat e een lijn zijn van een fylogenetische boom T op X . Split A|B is de split geassocieerd met e als A en B de labels zijn van de bladeren in de twee componenten die verkregen worden als e uit T verwijderd wordt. Leo van Iersel (TUE/CWI)


27 februari 2014

24 / 34

Notatie: Σ(T ) is de verzameling van alle splits geassocieerd met lijnen van T Voorbeeld:

e a b

d c

Σ(T ) = {ab|cde, abc|de, a|bcde, b|acde, c|abde, d|abce, e|abcd}



27 februari 2014

25 / 34

Stelling (split equivalence) Laat Σ een verzameling splits over X zijn. Dan zijn de volgende twee uitspraken equivalent: 1

er bestaat een fylogenetische boom T op X met Σ = Σ(T )

2

voor elke twee splits A1 |B1 en A2 |B2 in Σ is tenminste één van de volgende vier doorsnedes leeg I

A1 ∩ A2

I

A1 ∩ B2

I

B1 ∩ A2

I

B1 ∩ B2



27 februari 2014

26 / 34

Voorbeeld Voor de onderstaande boom T geldt: Σ(T ) = {ab|cdefg , abfg |cde, abcde|fg , abcfg |de} Plus alle splits die één blad afsplitsen van de rest.

f

a

g b d c Leo van Iersel (TUE/CWI)


e 27 februari 2014

27 / 34

Het vinden van T aan de hand van Σ(T ): Creëer een boom voor de eerste split. Σ(T ) = {ab|cdefg , abfg |cde, abcde|fg , abcfg |de}

a,b c,d,e,f,g



27 februari 2014

28 / 34

Het vinden van T aan de hand van Σ(T ): Voeg de tweede split toe. Σ(T ) = {ab|cdefg , abfg |cde, abcde|fg , abcfg |de}

a,b

f,g c,d,e



27 februari 2014

29 / 34

Het vinden van T aan de hand van Σ(T ): Voeg de derde split toe. Σ(T ) = {ab|cdefg , abfg |cde, abcde|fg , abcfg |de}

f,g

a,b c,d,e



27 februari 2014

30 / 34

Het vinden van T aan de hand van Σ(T ): Voeg de vierde split toe. Σ(T ) = {ab|cdefg , abfg |cde, abcde|fg , abcfg |de}

f,g

a,b

c


d,e


27 februari 2014

31 / 34

Het vinden van T aan de hand van Σ(T ): Voeg alle splits toe die één blad afsplitsen van de rest.

f

a

g b d c



e

27 februari 2014

32 / 34

Fylogenetische bomen met lengtes Definitie Laat T = (V , E ) een fylogenetische boom op X zijn en ` : E → R+ een lengtefunctie. Voor twee bladeren met labels a en b is X dT ,` (a, b) := `(e) e∈P

met P het unieke pad tussen de bladeren met labels a en b in T .

Definitie Een metriek op X is een functie d : X × X → R+ waarvoor geldt: d(x, y ) = 0 ⇔ x = y d(x, y ) = d(y , x) (symmetrie) d(x, y ) ≤ d(x, z) + d(z, y ) (driehoeksongelijkheid) Leo van Iersel (TUE/CWI)


27 februari 2014

33 / 34

Stelling (4-point condition) Laat d : X × X → R+ een metriek op X zijn. Dan zijn de volgende twee uitspraken equivalent: 1

er bestaat een fylogenetische boom T op X met lengtefunctie ` : E → R+ waarvoor d(x, y ) = dT ,` (x, y ) voor alle x, y ∈ X ;

2

voor elke vier A, B, C , D ∈ X geldt: d(A, B) + d(C , D) ≤ max

d(A, C ) + d(B, D) d(A, D) + d(B, C ).

Charles Semple and Mike Steel, Phylogenetics, Oxford University Press, 2003.



27 februari 2014

34 / 34

2WO12: Optimalisering in Netwerken

Recommend Documents