Uitwerkingen Tentamen Optimalisering in Netwerken (2WO12

Uitwerkingen Tentamen Optimalisering in Netwerken (2WO12)
Donderdag 10 april 2014, 14.00 - 17.00
Het tentamen bestaat uit 7 opgaven verspreid over 3 pagina’s. In totaal zijn er tussen de −20
en 100 punten te verdienen. Je cijfer wordt verkregen door het totaal aantal behaalde punten
door 9.99 te delen en af te ronden naar het dichtstbijzijnde getal in {1, 2, . . . , 10}. Je mag bij dit
tentamen alleen schrijfgerei gebruiken. Aantekeningen, boeken, dictaten, grafische rekenmachines, computers, telefoons e.d. mogen niet gebruikt worden. Je mag zowel in het Nederlands als
in het Engels antwoorden. Succes!
Opgave 1 (30 punten). Gegeven is de onderstaande graaf G = (V, E) met de aangegeven gewichten van de lijnen.
a
1
3
b
3
4
e
4
f
3
1
g
h
3
d
2
2
3
5
c
(a) Vind een opspannende boom in G van minimaal gewicht. Gebruik hiervoor het algoritme
van Prim-Dijkstra, begin met U1 = {a} en geef aan in welke volgorde je lijnen aan de
opspannende boom toevoegt (negeer hierbij de diktes van de lijnen in de figuur). [10 punten]
Oplossing. Voeg lijnen bijvoorbeeld toe in deze volgorde: {a, b}, {b, c}, {c, d}, {d, h}, {e, h},
{h, g}, {f, g}.
(b) De vette lijnen {{a, d}, {e, f }, {c, g}} vormen een matching van G die maximaal gewicht
heeft over alle matchings die uit drie lijnen bestaan. Vind een matching die maximaal gewicht heeft over alle matchings die uit vier lijnen bestaan. Gebruik hiervoor de Hongaarse
methode, geef aan over welk pad je de matching aanpast en waarom. [10 punten]
Oplossing. Kleur de punten van G met twee kleuren en construeer een gerichte hulpgraaf D door elke lijn in de matching van rood naar blauw te richten en elke lijn niet in
1
de matching van blauw naar rood. De lijnen in de matching houden positieve lengte en de
lijnen die niet in de matching zitten krijgen negatieve lengte. Dit leidt tot de onderstaande
hulpgraaf.
a
-1
-3
b
-3
4
e
4
f
-3
-1
g
h
-2
-3
d
-2
5
c
-3
De enige punten die niet door de matching overdekt worden zijn h en b. Een kortste gerichte
pad in D van h naar b is (h, d, a, e, f, b) met lengte -1. De nieuwe matching is het symmetrisch verschil tussen de oude matching en de lijnen op dit pad. Dit geeft de matching:
{{c, g}, {d, h}, {a, e}, {b, f }} met gewicht 14.
(c) Door een lijn {d, f } aan G toe te voegen krijgen we de graaf H. Is H planair? Geef aan
waarom wel/niet? [10 punten]
Oplossing. Graaf H is niet planair aangezien H een onderverdeling van K3,3 bevat. Zie
de figuur hieronder.
a
b
e
h
f
g
d
c
Opgave 2 (10 punten). Beschouw nu de onderstaande gerichte graaf D = (V, A) met de aangegeven lengtefunctie ` : A → R+ . Vind een kortste pad van s naar t in D met betrekking tot de
lengtefunctie `. Gebruik hiervoor het algoritme van Dijkstra en geef elke stap van het algoritme
duidelijk aan.
2
s
2
b
2
e
10
9
6
c
4
1
1
1
3
d
1
t
2
4
3
8
a
f
Oplossing.
• U = V, f (s) = 0 en f (v) = ∞
∀v ∈ V \ {s}
• f (b) = 2, f (c) = 6, f (d) = 9, f (a) = 10, verwijder s uit U
• f (e) = 4, verwijder b uit U
• f (c) = 5, verwijder e uit U
• f (d) = 8, f (t) = 13, verwijder c uit U
• f (a) = 9, f (f ) = 12, verwijder d uit U
• f (f ) = 11, verwijder a uit U
• f (t) = 12, verwijder f uit U , verwijder t uit U
Het kortste s-t pad is (s, b, e, c, d, a, f, t) met lengte 12.
Opgave 3 (10 punten). Bewijs dat elke graaf G = (V, E) met maximale graad ∆ een coclique
heeft van cardinaliteit tenminste
|V |
.
∆+1
Oplossing 1. Bewijs met inductie naar |V |. Als |V | = 1 dan is ∆ = 0 en vormt het enige punt
een coclique van cardinaliteit 1/(0 + 1) = 1.
Beschouw nu een graaf G = (V, E) met |V | ≥ 2, kies een willekeurig punt v ∈ V en verwijder v
en al zijn buren uit de graaf. Dit geeft graaf G0 . We hebben maximaal ∆ + 1 punten verwijderd
en de maximale graad van G0 is hoogstens ∆, dus volgens de inductie hypothese heeft G0 een
coclique van cardinaliteit tenminste
|V | − 1 − ∆
|V |
=
−1
∆+1
∆+1
Punt v toevoegen aan deze coclique geeft een coclique van G met cardinaliteit tenminste
|V |
.
∆+1
3
Oplossing 2. Kleur de punten van G met (∆ + 1) kleuren. De kleur die het vaakste voorkomt
kleurt minimaal |V |/(∆ + 1) punten. Dus vormen de punten met deze kleur een coclique van
cardinaliteit tenminste |V |/(∆ + 1).
Opgave 4 (10 punten). Laat G = (V, E) een bipartiete planaire graaf zijn met |V | ≥ 3. Bewijs
dat
|E| ≤ 2|V | − 4.
Oplossing. De stelling van Euler zegt dat |V | + f = |E| + 2 met f het aantal facetten. Als f = 1
dan is G een boom en is |E| = |V | − 1 ≤ 2|V | − 4 (want |V | ≥ 3). Neem nu aan dat f ≥ 2.
Omdat G bipartiet is wordt elk facet omsloten door tenminste vier lijnen (een facet omsloten door
drie lijnen zou een oneven circuit vormen). Elke lijn zit in de rand van hoogstens twee facetten,
dus geldt |E| ≥ 4f /2 = 2f en f ≤ |E|/2. Invullen in de formule van Euler geeft
1
|E| = |V | + f − 2 ≤ |V | + |E| − 2
2
en dus
|E| ≤ 2|V | − 4.
Opgave 5 (20 punten). Geef voor elk van de onderstaande beweringen aan of ze waar (W) of
onwaar (O) zijn. Een argumentatie is niet nodig (verspil hier dus geen tijd aan). Elk correct
antwoord levert 2 punten op, elk fout antwoord −2 punten en elke vraag zonder antwoord 0
punten.
(a) Een algoritme met looptijd Θ(W (|V | + |E|)) voor een probleem met als invoer een gewogen
graaf G = (V, E) met maximum gewicht W is een polynomiaal algoritme.
Oplossing. Niet waar want de lengte van de invoer is een polynoom in |V |, |E| en log(W )
maar W is exponentieel in log(W ) en dus is W (|V |+|E|) exponentieel in |V |, |E| en log(W ).
(b) De lijngraaf van elke Euler graaf is een Hamilton graaf.
Oplossing. Waar. Als e1 , . . . , em een Euler tour in G is dan is ve1 , . . . , vem een Hamilton
circuit in de lijngraaf van G.
(c) Elke 3-reguliere Hamilton graaf heeft lijnkleurgetal 3.
Oplossing. Waar. Er zijn een even aantal punten door het handshaking lemma. Dus
kunnen de lijnen van het Hamilton circuit met twee kleuren gekleurd worden. De overige
lijnen verbinden punten in het circuit en kunnen dus met de derde kleur gekleurd worden.
(d) Elke k-reguliere bipartiete graaf heeft een perfecte matching, voor alle k ∈ N (met k ≥ 1).
Oplossing. Waar. Als een bipartiete graaf G = (U ∪ W, E) geen perfecte matching heeft,
dan zijn er volgens Hall’s Marriage Theorem, U 0 ⊆ U en W 0 ⊆ W zodanig dat de punten
in U 0 alleen buren in W 0 hebben en |W 0 | < |U 0 |. Dit is niet mogelijk wanneer alle punten
dezelfde graad hebben.
(e) Voor elke graaf G bestaat er een puntkleuring met maximaal d + 1 kleuren, als d het gemiddelde is van de graden van G.
Oplossing. Niet waar. Bijvoorbeeld als G een clique van vier punten bevat, maar ook veel
punten van lage graad waardoor d < 3.
4
(f ) Als een graaf precies 6 punten van oneven graad heeft en vier daarvan liggen in dezelfde
samenhangende component, dan bestaat er een pad tussen de overige twee punten met
oneven graad.
Oplossing. Waar. Anders zou er een samenhangende component zijn met een oneven
aantal punten van oneven graad. Dit is niet mogelijk volgens het Handshaking Lemma.
(g) Elke 4-reguliere graaf met 100 punten heeft een matching bestaande uit tenminste 40 lijnen.
Oplossing. Waar. Er zijn 200 lijnen en volgens de stelling van Vizing kunnen we die met 5
kleuren kleuren. De kleur die het vaakste voorkomt wordt gebruikt om tenminste 200/5 = 40
lijnen te kleuren. Dit vormt een matching van tenminste 40 lijnen.
(h) Elke graaf met tenminste 5 punten die niet 5-kleurbaar is heeft K3 als deelgraaf.
Oplossing. Niet waar volgens de stelling van Mycielski.
(i) Als G = (V, E) een samenhangende graaf is en voor e, e0 ∈ E geldt dat (V, E \ {e, e0 }) een
graaf is met twee samenhangende componenten H en H 0 , dan is het puntkleurgetal van G
gelijk aan het maximum van het puntkleurgetal van H en het puntkleurgetal van H 0 .
Oplossing. Niet waar. Bijvoorbeeld een oneven circuit is een tegenvoorbeeld.
(j) Elke 3-reguliere graaf met n ≥ 5 punten heeft een coclique met cardinaliteit tenminste
Oplossing. Niet waar. Bijvoorbeeld de onderstaande graaf is een tegenvoorbeeld.
n
2.
Opgave 6 (10 punten). Beschouw het volgende probleem. Gegeven is een gerichte graaf D =
(V, A), een capaciteitsfunctie c : A → R+ en een vraagfunctie d : V → R. Een (d, c)-circulatie
van D is een functie f : A → R+ waarvoor geldt:
0 ≤ f (a) ≤ c(a)
X
X
f (a) −
f (a) = d(v)
a∈δ − (v)
voor elke a ∈ A en
voor elke v ∈ V.
a∈δ + (v)
Gevraagd wordt om te beslissen of er een (d, c)-circulatie bestaat in een gegeven gerichte graaf D
voor een gegeven capaciteitsfunctie c en vraagfunctie d. Bewijs dat dit probleem oplosbaar is in
polynomiale tijd door het te formuleren als een maximum-stroom probleem.
(Merk op dat de vraagfunctie d(v) zowel positieve als negatieve waardes kan aannemen. Beschrijf je formulering in detail en geef aan hoe die gebruikt kan worden om te beslissen of er een
(d, c)-circulatie bestaat. Je hoeft niet te bewijzen dat je formulering correct is.)
Oplossing. Voeg een bron s en een put t toe. Voor elk punt v ∈ V waarvoor d(v) < 0, voeg
een pijl van s naar v toe met capaciteit c(v) = −d(v). Voor elk punt u ∈ V waarvoor d(u) > 0,
5
voeg een pijl van u naar t toe met capaciteit c(u) = d(u). Nu bestaat er een (d, c)-circulatie in
de originele gerichte graaf D dan en slechts dan als er een s-t stroom bestaat met waarde
X
X
c(a) =
c(a)
a∈δ − (t)
a∈δ + (s)
in de aangepaste gerichte graaf.
Opgave 7 (10 punten). Bewijs dat het onderstaande beslissingsprobleem NP-volledig is.
BUREN-INCIDENT
Gegeven: graaf G = (V, E) en k ∈ N.
Beslis: is er een deelverzameling V 0 van V met |V 0 | ≤ k zodanig dat voor elke lijn e ∈ E er een
punt v ∈ V 0 bestaat zodanig dat e incident is met v of met een buur van v.
Oplossing 1. BUREN-INCIDENT ∈ NP omdat gegeven een verzameling V 0 ⊆ V in polynomiale tijd gecontroleerd kan worden of elke lijn in E incident is met een punt in V 0 of incident
is met een buur van een punt in V 0 .
Bewijs NP-moeilijkheid d.m.v. een reductie vanuit het probleem VERTEX COVER. Gegeven een
instantie (G = (V, E), k) van VERTEX COVER, verkrijgen we een instantie (G∗ = (V ∗ , E ∗ ), k)
van BUREN-INCIDENT door voor elke lijn e = {u, w} twee punten veu , vew en drie lijnen {u, veu },
{w, vew }, {veu , vew } toe te voegen. Zie hieronder een voorbeeld.
u
e
ve u
u
w
vew
w
G¤
G
Neem eerst aan dat G een vertex cover heeft van cardinaliteit hoogstens k. Laat V 0 de punten in
de vertex cover zijn. Dan is V 0 ⊆ V ∗ en |V 0 | ≤ k. Voor elke lijn {u, w} ∈ E geldt dat u of w
in V 0 zit want V 0 is een vertex cover. Neem (zonder verlies van algemeenheid) aan dat u ∈ V 0 .
Dan zijn {u, w} en {u, veu } incident met u terwijl {w, vew } en {veu , vew } incident zijn met een buur
van u. Dus is elke lijn in E ∗ incident met een punt in V 0 of met een buur van een punt in V 0
(in G∗ ).
Neem nu aan dat er een verzameling V 0 ⊆ V ∗ bestaat met |V 0 | ≤ k zodanig dat elke lijn in E ∗
incident is met een punt in V 0 of met een buur van een punt in V 0 (in G∗ ). Dan kunnen we als
volgt een vertex cover K van G met |K| ≤ k vinden. Voor elke lijn e = {u, w} van G, als u of veu
in V 0 zit, stop dan u in K. Bovendien, als w of vew in V 0 zit, stop dan w in K. Tenminste ´e´en
van u, w, veu , vew zit in V 0 want anders was de lijn {veu , vew } niet incident met een punt in V 0 en
6
niet incident met een buur van een punt in V 0 . Dus zit tenminste ´e´en van u en w in K. Dus
wordt elke lijn van G overdekt door K en dus is K een vertex cover van G.
Oplossing 2. BUREN-INCIDENT ∈ NP omdat gegeven een verzameling V 0 ⊆ V in polynomiale tijd gecontroleerd kan worden of elke lijn in E incident is met een punt in V 0 of incident
is met een buur van een punt in V 0 .
Bewijs NP-moeilijkheid d.m.v. een reductie vanuit het probleem VERTEX COVER. Gegeven een
instantie (G = (V, E), k) van VERTEX COVER, verkrijgen we een instantie (G∗ = (V ∗ , E ∗ ), k)
van BUREN-INCIDENT door voor elke lijn e = {u, w} twee punten ve , ve∗ toe te voegen en de
lijn e te vervangen door drie lijnen {u, ve }, {ve , ve∗ }, {ve , w}. Zie hieronder een voorbeeld.
ve¤
u
e
w
u
ve
w
G¤
G
Neem eerst aan dat G een vertex cover heeft van cardinaliteit hoogstens k. Laat V 0 de punten
in de vertex cover zijn. Dan is V 0 ⊆ V ∗ en |V 0 | ≤ k. Voor elke lijn e = {u, w} ∈ E geldt dat u
of w in V 0 zit want V 0 is een vertex cover. Dan is, in G∗ , ve een buur van een punt in V 0 . Dus
alle drie de lijnen {u, ve }, {ve , ve∗ }, {ve , w} zijn incident met een buur van een punt in V 0 . Dus
is elke lijn in E ∗ incident met een punt in V 0 of met een buur van een punt in V 0 (in G∗ ).
Neem nu aan dat er een verzameling V 0 ⊆ V ∗ bestaat met |V 0 | ≤ k zodanig dat elke lijn in E ∗ incident is met een punt in V 0 of met een buur van een punt in V 0 (in G∗ ). Voor elke lijn e = {u, w}
van de originele graaf G geldt dat tenminste ´e´en van de punten u, w, ve , ve∗ in V 0 zit omdat anders de lijn {ve , ve∗ } niet incident zou zijn met een punt in V 0 of een buur van een punt in V 0 .
Als u of w in V 0 zit dan stoppen we hetzelfde punt in K. Als ve of ve∗ in V 0 zit dan stoppen
we willekeurig ´e´en van u en w in K. Dit doen we voor elke lijn e = {u, w} van G. Dan geldt
dat |K| ≤ k en bovendien dat voor elke lijn e = {u, w} van G tenminste ´e´en van u en w in K
zit. Oftewel, K is een vertex cover van G met cardinaliteit hoogstens k.
7

Download Report