2WO12: Optimalisering in Netwerken Leo van Iersel Technische Universiteit Eindhoven (TUE) en Centrum Wiskunde & Informatica (CWI)
3 en 6 februari 2014
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
1 / 47
Inhoud vak:
Modelleren van praktijkproblemen m.b.v. grafen Effici¨ente algoritmes voor graafproblemen Bewijzen van stellingen over grafen Analyse van algoritmes Classificeren van problemen als “moeilijke” en “makkelijke” problemen
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
2 / 47
Opzet vak:
8 lectures verdeeld over 16 hoorcolleges 8 instructies zelfstudie (opgaven) twee dictaten en twee “hand-outs” op website: http://homepages.cwi.nl/~iersel/2WO12/
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
3 / 47
Dictaten en “hand-outs”
Lecture 1-3: Grafen: kleuren en routeren (gkr.pdf) Lecture 4: Graafrepresentaties en complexiteit (compl.pdf) Lectures 5-7: A course in combinatorial optimization (co.pdf) Lecture 8: NP-completeness (np.pdf) http://homepages.cwi.nl/~iersel/2WO12/
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
4 / 47
Definitie Een graaf (graph) is een paar G = (V , E ) waarin V en E eindige verzamelingen zijn en elk element van E een verzameling van twee elementen van V is. V is een verzameling punten (vertices) E is een verzameling lijnen (edges) of kanten elke lijn verbindt twee punten grafen worden ook wel netwerken genoemd
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
5 / 47
Voorbeeld De onderstaande graaf G = (V , E ) heeft: V = {a, b, c, d, e} E = {{a, b}, {a, c}, {b, c}, {b, d}, {c, d}, {d, e}}
a c
b d e Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
6 / 47
Waarschuwing: we kunnen dezelfde graaf op vele manieren tekenen, bijvoorbeeld:
a c =
b d e Leo van Iersel (TUE/CWI)
b d
2WO12: Optimalisering in Netwerken
c e
a
3 en 6 februari 2014
7 / 47
Terminologie Als e = {u, v } ∈ E , dan zeggen we:
u
u en v zijn verbonden (adjacent)
e
u is een buur (neighbour) van v (en v is een buur van u) u en v zijn eindpunten (endpoints) van e
v
u en e zijn incident (en v en e zijn incident)
Definitie De graad (degree) van een punt v in een graaf G is het aantal buren dat v heeft in G . Notatie: d(v )
Definitie Een graaf G is k-regulier als elk punt van G graad k heeft Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
8 / 47
Voorbeeld In de onderstaande graaf heeft a graad twee, b, c en d hebben graad drie en e heeft graad ´e´en.
a c
b d e Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
9 / 47
Voorbeeld Voorbeelden van reguliere grafen:
2-regulier (circuit)
Leo van Iersel (TUE/CWI)
3-regulier (kubus)
2WO12: Optimalisering in Netwerken
3-regulier (Petersen graaf)
3 en 6 februari 2014
10 / 47
Lemma (Handshaking Lemma) Voor elke graaf G = (V , E ) is de som van de graden even, namelijk: X d(v ) = 2|E | v ∈V
Voorbeeld
A
B
C
D
A, B, C , D: personen Lijnen: handdrukken d(A): aantal handen dat persoon A schudt
Gevolg Elke graaf heeft een even aantal punten van oneven graad. (Opgave 1.16)
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
11 / 47
Definitie Een volledige graaf (complete graph) heeft een lijn tussen elk paar punten. Kn is de volledige graaf op n punten
Opgave (1.22) Hoeveel lijnen heeft K5 ?
Opgave (1.23) Hoeveel lijnen heeft Kn ?
Opgave (1.24) G is een graaf op n punten. Bewijs: G is volledig dan en slechts dan als G (n − 1)-regulier is. Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
12 / 47
Definitie Een graaf G = (V , E ) heet bipartiet (bipartite) als V = V1 ∪ V2 (met V1 ∩ V2 = ∅) en E ⊆ {{v1 , v2 } | v1 ∈ V1 , v2 ∈ V2 } G is een volledig bipartiete graaf als E = {{v1 , v2 } | v1 ∈ V1 , v2 ∈ V2 } Kn,m is de volledig bipartiete graaf met |V1 | = n en |V2 | = m.
Vraag Hoeveel lijnen heeft Kn,m ?
Vraag Voor welke n en m is Kn,m regulier? Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
13 / 47
Definitie ¯ = (V , E¯ ) Het complement van een graaf G = (V , E ) is de graaf G ¯ met {u, v } ∈ E voor alle u, v ∈ V met {u, v } ∈ /E
a
b
a
b
c
d
c
d
G
G
Vraag Wat is het complement van K3,4 ?
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
14 / 47
Definitie Twee grafen G = (V , E ) en G 0 = (V 0 , E 0 ) zijn isomorf (isomorphic) als er een bijectie f : V → V 0 bestaat zodanig dat voor alle u, v ∈ V : (u, v ) ∈ E ⇐⇒ (f (u), f (v )) ∈ E 0 .
Definitie ¯ isomorf zijn. Een graaf G is zelf-complementair als G en G
Voorbeeld Een circuit van lengte 5 is zelf-complementair.
b
a
b
a
c e
e d G
Leo van Iersel (TUE/CWI)
c
a
c d d G
e b G
2WO12: Optimalisering in Netwerken
f (a) = a f (b) = c f (c) = e f (d) = b f (e) = d 3 en 6 februari 2014
15 / 47
Definitie De lijngraaf van een graaf G = (V , E ) is de graaf H = (V 0 , E 0 ) met een punt ve ∈ V 0 voor elke lijn e ∈ E en een lijn {ve1 , ve2 } ∈ E 0 voor elke twee lijnen e1 , e2 ∈ E die incident zijn, d.w.z. met e1 ∩ e2 6= ∅
Vraag Hoe ziet de lijngraaf van K2,2 er uit? En de lijngraaf van K1,7 ?
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
16 / 47
Definitie Een wandeling (walk) in een graaf G = (V , E ) is een rij punten (v0 , v1 , . . . , vk ) zodanig dat vi−1 en vi verbonden zijn voor i = 1, . . . , k. De lengte van de wandeling is k.
Definitie Een pad (path) is een wandeling waarvan alle punten verschillend zijn.
Definitie Een graaf is samenhangend (connected) als tussen elk tweetal punten een pad bestaat.
Stelling (Opgave 1.48) Voor elke samenhangende graaf G = (V , E ) geldt |E | ≥ |V | − 1 Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
17 / 47
Stelling (Opgave 1.51) Voor elke onsamenhangende graaf G = (V , E ) geldt 1 |E | ≤ (|V | − 1)(|V | − 2) 2
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
18 / 47
Definitie G 0 = (V 0 , E 0 ) is een deelgraaf (subgraph) van graaf G = (V , E ) als G 0 een graaf is en V 0 ⊆ V en E 0 ⊆ E .
Voorbeeld In de onderstaande figuur is G 0 een deelgraaf van G .
a
a
b
c
d
c
e
e
f
f G0
G Leo van Iersel (TUE/CWI)
d
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
19 / 47
Definitie Een (samenhangende) component G 0 van een graaf G is een “maximale” samenhangende deelgraaf, d.w.z. G 0 is een samenhangende deelgraaf van G en er is geen samenhangende deelgraaf G 00 van G waarvoor geldt dat G 0 een deelgraaf is van G 00 en G 0 6= G 00 . Dus: G samenhangend ⇐⇒ G heeft precies ´e´en component.
Voorbeeld Hoeveel componenten heeft de onderstaande graaf?
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
20 / 47
Stelling (Opgave 1.59-1.61) Als (V1 , E1 ), . . . , (Vk , Ek ) de componenten van G zijn dan vormt {V1 , . . . , Vk } een partitie van V en {E1 , . . . , Ek } een partitie van E
Opgave (1.64) Bewijs dat een graaf G = (V , E ) tenminste |V | − |E | componenten heeft.
Opgave (1.65) Bewijs dat als een graaf precies twee punten van oneven graad heeft, dan loopt er een pad tussen deze twee punten.
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
21 / 47
Bergbeklimmersprobleem
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
22 / 47
Bergbeklimmersprobleem
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
23 / 47
Bergbeklimmersprobleem
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
24 / 47
Andere soorten grafen
Gerichte grafen (directed graphs) hebben pijlen i.p.v. lijnen. Multigrafen kunnen meerdere lijnen hebben tussen dezelfde twee punten. Grafen met lussen (loops). Een lus is een lijn (of pijl) die een punt met zichzelf verbindt. Gerichte multigrafen “Gewone” grafen worden soms ook simpele grafen genoemd.
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
25 / 47
Definitie Een wandeling (v0 , v1 , . . . , vk ) in een graaf heet gesloten als v0 = vk .
Definitie Een circuit (cycle) is een gesloten wandeling (v0 , v1 , . . . , vk ) waarvoor v1 , . . . , vk verschillend zijn en k ≥ 3.
Voorbeeld In de onderstaande graaf is (a, b, d, c, e, g , f , d, c, a) een gesloten wandeling, maar geen circuit. De gesloten wandeling (a, b, d, c, a) is wel een circuit.
a
b
c
d
e
f g
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
26 / 47
Definitie Een bos is een graaf zonder circuits. Een boom is een samenhangend bos.
boom Stelling (Opaven 1.75,1.77,1.79) Als G een graaf op n punten is dan zijn de volgende uitspraken equivalent 1
G is een boom
2
G heeft n − 1 lijnen en is samenhangend
3
G heeft n − 1 lijnen en bevat geen circuits
4
tussen elk tweetal punten van G loopt precies ´e´en pad
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
27 / 47
Bruggen van K¨oningsberg
Kun je elke brug precies ´e´en keer oversteken en bij je beginpunt uitkomen?
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
28 / 47
Definitie Een Euler tour in een graaf G is een gesloten wandeling die elke lijn precies ´e´en keer doorloopt. Als er een Euler tour bestaat voor G , dan heet G een Euler graaf.
Definitie Een Hamilton circuit in een graaf G is een circuit dat elke punt van G doorloopt. Als er een Hamilton circuit bestaat voor G , dan heet G een Hamilton graaf.
Vraag Is K4 een Hamilton graaf? En een Euler graaf?
Vraag Is K2,4 een Hamilton graaf? En een Euler graaf?
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
29 / 47
Definitie Een Euler tour in een graaf G is een gesloten wandeling die elke lijn precies ´e´en keer doorloopt. Als er een Euler tour bestaat voor G , dan heet G een Euler graaf.
Stelling (Euler) Laat G een graaf zijn zonder punten van graad 0. Dan geldt: G is een Euler graaf ⇐⇒ G is samenhangend en alle graden in G zijn even.
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
30 / 47
Vraag Heeft de onderstaande graaf een Euler tour?
a d
e
b f
k
g
c h
l
i
j
m
Opgave Vind een Euler tour. Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
31 / 47
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
32 / 47
Chinese Postbodeprobleem Probleem Geven een graaf G = (V , E ) met een lengtefunctie ` : E → R+ , vind een zo kort mogelijke gesloten wandeling die elke lijn minstens ´e´en keer doorloopt.
Observatie Als G een Euler graaf is dan is elke Euler tour een optimale oplossing van het Chinese Postbodeprobleem.
2 4
3 4 Leo van Iersel (TUE/CWI)
6 4 5
3 3
4 2WO12: Optimalisering in Netwerken
4
3
5 3 en 6 februari 2014
33 / 47
Chinese Postbodeprobleem Laat T de punten van G zijn met oneven graad. Dan is |T | even.
Definitie Een T -join is een verzameling paden die de punten van T paarsgewijs met elkaar verbindt.
Lemma In een T -join van minimale totale lengte zijn de paden lijn-disjunct. Oplossen van een Chinees Postbodeprobleem: vind een T -join van minimale totale lengte; verdubbel elke lijn in de T -join; vind een Euler tour.
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
34 / 47
Opgave Los het Chinese Postbodeprobleem op in de onderstaande graaf.
2 5
3
4 Leo van Iersel (TUE/CWI)
6 7
4
4 2WO12: Optimalisering in Netwerken
4
2
4 3 en 6 februari 2014
35 / 47
Definitie Een Hamilton circuit in een graaf G is een circuit dat elke punt van G doorloopt. Als er een Hamilton circuit bestaat voor G , dan heet G een Hamilton graaf.
Stelling (Dirac) Als G een graaf is op n ≥ 3 punten waarin alle graden tenminste dan is G een Hamilton-graaf.
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
n 2
zijn,
3 en 6 februari 2014
36 / 47
Fylogenetische bomen Een blad is een punt van een boom met graad ´e´en.
Definitie Gegeven een verzameling X , een fylogenetische boom B op X is een boom zonder punten van graad 2 en met een bijectie tussen de bladeren van B en de elementen van X . X kan bijvoorbeeld een verzameling biologische soorten voorstellen Een fylogenetische boom op X geeft dan aan hoe deze soorten aan elkaar verwand zijn
kat rat
tijger
muis Leo van Iersel (TUE/CWI)
mens
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
37 / 47
Fylogenetische bomen
Of X kan een verzameling talen voorstellen Een fylogenetische boom op X geeft dan weer hoe deze talen aan elkaar verwand zijn
Nederlands Frans
Duits
Italiaans
Leo van Iersel (TUE/CWI)
Engels
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
38 / 47
Fylogenetische boom voor talen
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
39 / 47
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
40 / 47
Een fylogenetische boom waarvan alle punten graad 1 of 3 hebben heet binair. Stel B is een binaire fylogenetische boom op X en |X | = n.
Vraag Hoeveel punten heeft B, als functie van n (voor n ≥ 2)?
Vraag Hoeveel lijnen heeft B, als functie van n (voor n ≥ 2)?
Stelling Voor |X | = n ≥ 3, zijn er 1 · 3 · 5 · · · (2n − 7) · (2n − 5) verschillende binaire fylogenetische bomen op X . Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
41 / 47
De Bruijn rijen Definitie Een De Bruijn rij van orde n voor een alfabet A is een cyclische ordering van de letters van A zodanig dat elk mogelijke woord van lengte n bestaande uit letters van A precies ´e´en keer voorkomt.
Voorbeeld A = {0, 1} en n = 2 Woorden van lengte n: 00, 01, 10 en 11 De Bruijn rij: (0, 0, 1, 1)
Voorbeeld A = {0, 1} en n = 3 Woorden van lengte n: 000, 001, 010, 011, 100, 101, 110 en 111 De Bruijn rij: (0, 0, 0, 1, 0, 1, 1, 1) Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
42 / 47
Definitie De De Bruijn graaf van dimensie n voor een alfabet A is de gerichte graaf met: een punt voor elk woord van lengte n bestaande uit letters van A vanuit het punt voor woord w1 is er een pijl naar elk punt voor een woord w2 dat verkregen kan worden door de eerste letter van w1 weg te laten en ´e´en letter aan het eind toe te voegen (deze letter is het label van de pijl).
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
43 / 47
De Bruijn graaf Voorbeeld voor A = {0, 1}, n = 3: 0 000
0
1
1
100
001 0
0 010 0
1 1
110
0 101
1 1 011
0 0
1 111 1
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
44 / 47
Een Hamilton circuit in een De Bruijn graaf van dimensie n geeft een De Bruijn rij van orde n. Een Euler tour in een De Bruijn graaf van dimensie n geeft een De Bruijn rij van orde n + 1. Je krijgt de De Bruijn rij door de labels van de pijlen in het circuit achter elkaar te zetten.
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
45 / 47
Toepassing in de moleculaire biologie Bacteri¨en hebben cyclisch DNA, bijvoorbeeld: ATGGCGTGCAATGGCGT... Machines die DNA aflezen (sequencing) produceren fragmenten, bijvoorbeeld: ATGGCGT-----------GGCGTGC-----------CGTGCAA-----------TGCAATG-----------CAATGGC-----------ATGGCGT Hoe kunnen we de hele DNA sequentie afleiden uit de fragmenten?
Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
46 / 47
Splits de fragmenten in stukjes van lengte 3 Maar een De Bruijn graaf met een pijl voor elk zo’n stukje Vind een Euler tour in de graaf T
AT
G
AA
TG G
A CA
G
A
C
GG C
GC
GT T
CG
G
Zet de labels van de pijlen in de Euler tour achter elkaar: ATGGCGTGCA Leo van Iersel (TUE/CWI)
2WO12: Optimalisering in Netwerken
3 en 6 februari 2014
47 / 47