O EFENTENTAMEN D ISCRETE STRUCTUREN 4-4-2011 —————————————————— Alleen als je cijfer voor de deeltoets minimaal een 6 was geeft dit vrijstelling voor Deel 1 van dit tentamen (afleggen van Deel 1 is altijd toegestaan). Voorzie de in te leveren bladen van je naam, en nummer ze. Schrijf op het eerste blad het aantal ingeleverde bladen. Bij elk van de opgaven is het maximale aantal te behalen punten vermeld. Antwoorden dienen altijd van een motivatie te worden voorzien. Succes!
Deel 1 Opgave 1. (10 pt) Gegeven is een universele verzameling U , met willekeurige deelverzamelingen A en B. a. Druk het verschil A − B uit door alleen gebruik te maken van de verzamelingoperaties vereniging ∪ en complement . b. Gebruik een Venndiagram om de uitdrukking A − (A − B) te vereenvoudigen. Geef vervolgens een bewijs dat de oorspronkelijke uitdrukking en de vereenvoudigde uitdrukking gelijk zijn. Geef in elke stap van het bewijs aan welke regels uit de verzamelingenalgebra worden gebruikt. Opgave 2. (5 pt) Gegeven de verzameling A = {a, b, c}. Hieronder wordt steeds een string uit A∗ gevolgd door een reguliere expressie over A. Geef voor elk van die gevallen aan of de string behoort tot de reguliere verzameling die correspondeert met de betreffende reguliere expressie. Verklaar je antwoorden. a. a b a∗ bc∗ b. a c b b ((a c b) ∨ b)∗ c. a b a c a (a b)∗ a c Opgave 3. (10 pt) Bewijs met volledige inductie dat 1 + 2n < 3n voor alle gehele getallen n > 2. Opgave 4. (15 pt) Laat R = {(1, 3), (2, 4), (3, 2), (4, 3)} een relatie zijn op A = {1, 2, 3, 4}. a. b. c. d.
Teken de graaf van R. Is de relatie R een functie? Bepaal R−1 . Is de relatie R−1 een functie? Bepaal de kleinste equivalentierelatie die R bevat en teken de bijbehorende graaf. e
Opgave 5. (10 pt) In de figuur hiernaast is het Hasse diagram van een parti¨ele ordening ≤ op L = {a, b, c, d, e} weergegeven.
d c
b
a. Bewijs dat L een tralie is. b. Het tralie L is begrensd. Leg uit waarom. Wat is het grootste element I en het kleinste element O ? c. Als voor een element x van een begrensd tralie geldt dat er een element x0 in het tralie is met x ∨ x0 = I en x ∧ x0 = O dan heet x0 een complement van x. Geef voor elk element van het tralie L een complement.
a
Discrete structuren, 4-4-2011
2
Deel 2 Opgave 6. (10 pt) x y
z a. Geef de Boolese expressie p(x, y, z) die correspondeert met de uitvoer van het logische diagram hierboven. b. Gebruik de regels van de Boolese algebra om de expressie p te herschrijven zodat een minimaal aantal variabelen en operaties wordt gebruikt. Teken het logische diagram van de nieuwe expressie. Opgave 7. (10 pt) Gegeven is een gelabelde boom (T, v0 ) met labels uit de verzameling {×, ÷, +, −, 1, 2, . . . , 9}. Hierin zijn ×, ÷, +, − de gebruikelijke rekenkundige bewerkingen op de gehele getallen. a. De expressie 4 2 − 2 6 3 ÷ + × is het resultaat van een postorder wandeling (“postorder search”) door de boom T . Teken de bijbehorende boom, inclusief labels, en evalueer de expressie. b. Gegeven is een willekeurige eindige string a1 , a2 , a3 , . . . , an . Laat zien dat elke letter van de string gekozen kan worden als wortel van een binaire boom waarvan de inorder wandeling (“inorder search”) deze string oplevert. Opgave 8. (10 pt) Deze opgave gaat over ongerichte grafen van symmetrische relaties. a. Wanneer heet een graaf samenhangend? b. Wanneer is een samenhangende graaf een boom? c. In een graaf G defini¨eren we een relatie ≡ tussen paren x, y van knopen als volgt: x ≡ y d.e.s.d.a. x = y of als er een pad van lengte n > 1 van x naar y loopt. Is ≡ een equivalentierelatie? Zo ja, wat zijn de equivalentieklassen? d. Bewijs de volgende bewering: als er een pad is in een ongerichte graaf G van knoop u naar knoop v, dan is er ook een pad van u naar v dat elke knoop hoogstens eenmaal bevat. Opgave 9. (10 pt) a
Deze opgave gaat over minimale opspannende bomen (“minimal spanning trees”) van ongerichte grafen van samenhangende symmetrische relaties.
3
c 3
1
2
e
2 1
b
4
d
a. Bepaal een minimale opspannende boom van de graaf G5 in bovenstaande figuur volgens het algoritme van Prim, als gestart wordt bij knoop a (linksboven in de figuur). Geef ook aan in welke volgorde de kanten van de minimale opspannende boom door dit algoritme worden opleverd. b. Stel dat de gewichten van de kanten van een graaf G zijn geordend naar grootte: w1 < w2 < . . . . Als de graaf G meerdere kanten heeft met hetzelfde minimale gewicht w1 , maken deze kanten dan altijd deel uit van een minimale opspannende boom? Verklaar je antwoord. Opgave 10. (10 pt) Bekijk nogmaals de graaf G5 uit Opgave 9. a. b. c. d.
Heeft de graaf G5 een Euler circuit? Zo ja, geef zo’n circuit. Zo nee, leg uit waarom niet. Heeft de graaf G5 een Hamiltoniaans circuit? Zo ja, geef zo’n circuit. Zo nee, leg uit waarom niet. Geef een kleuring van de graaf G5 met een minimaal aantal kleuren. Voor welke waarden van n heeft de volledige graaf Kn met n knopen een Euler circuit? En een Hamiltoniaans circuit? Verklaar je antwoorden.
Discrete structuren, 4-4-2011
1
Uitwerking Opgave 1.
Venndiagram: a. A − B = A ∩ B = (A ∪ B). Hierbij volgt de eerste gelijkheid uit de definitie van het verschil, en de tweede uit de Morgan en de involutie-eigenschap van het complement (d.w.z., B = B). b. In het Venndiagram hierboven is het gele deel A − B. Als we dit weglaten uit A krijgen we precies A ∩ B. We gaan dus bewijzen dat A − (A − B) = A ∩ B. A − (A − B) = { definitie − } A ∩ (A ∩ B) = { de Morgan } A ∩ (A ∪ B) = { involutie-eigenschap complement } A ∩ (A ∪ B) = { distrib. } (A ∩ A) ∪ (A ∩ B) = { eigenschap complement } ∅ ∪ (A ∩ B) = { eigenschap lege verzameling } A∩B Opgave 2. a. a b behoort tot de reguliere verzameling die hoort bij a∗ bc∗ , want daarin zitten: alle strings bestaande uit e´ e´ n b voorafgegaan door 0 of meer a’s en gevolgd door 0 of meer c’s. b. a c b b behoort tot de reguliere verzameling die hoort bij ((a c b) ∨ b)∗ , want daarin zitten: de lege string, en alle eindige strings die je krijgt door voor elk symbool van de string steeds (a c b) of b te kiezen. c. a b a c a behoort niet tot de reguliere verzameling die hoort bij (a b)∗ a c, want daarin zitten: de string a c, voorafgegaan door 0 of meer concatenaties van de string a b. Opgave 3. Het bewijs verloopt met inductie naar de grootte van n. Laat P (n): 1 + 2n < 3n voor alle gehele getallen n > 2. (B) Basisgeval: P (2) zegt dat 1 + 22 < 32 , d.w.z. 5 < 9. Dit klopt. (H) Inductiehypothese: P (k) is waar voor zekere k > 2. (I) Inductiestap: te bewijzen dat P (k + 1) waar is. 1 + 2k+1 = 1 + 2 · 2k < 1 + 2 · (3k − 1)
(inductiehyp.)
= −1 + 2 · 3k < 2 · 3k k
(k > 2) k+1
<3·3 =3
Dus we hebben bewezen dat 1 + 2k+1 < 3k+1 , d.w.z. P (k + 1) is waar. Conclusie: P (n) is waar voor alle n > 2.
Discrete structuren, 4-4-2011
2
Opgave 4. 1
2
1
2
4
3
4
3
Figuur 1: Links: de graaf van R; rechts: de graaf van tsr(R)
a. b. c. d.
De graaf van R staat in figuur 1, links. De relatie R is een functie, want bij elke a ∈ A hoort hoogstens (in dit geval precies) e´ e´ n b ∈ A. R−1 = {(3, 1), (4, 2), (2, 3), (3, 4)}. R−1 is geen functie, want 3 heeft de relatie R−1 met zowel 1 als 4. De kleinste equivalentierelatie die R bevat is tsr(R). D.w.z., eerst nemen we de reflexieve afsluiting (voeg loops toe voor elke knoop van de graaf); dan de symmetrische afsluiting: overal waar een kant is voegen we een kant in omgekeerde richting toe; tenslotte de transitieve afsluiting: we kunnen van 1 → 3 en 3 → 2, dus moeten we ook de kant van 1 → 2 toevoegen, en op dezelfde manier ook die van 2 → 1, 1 → 4 en 4 → 1. De bijbehorende graaf staat in figuur 1, rechts.
Opgave 5. a. L is een tralie, want elk tweetal elementen x en y van L heeft een supremum (kleinste bovengrens) en een infimum (grootste ondergrens). b. Het tralie L is begrensd: het grootste element is e en het kleinste element is a. c. Complementen: a0 = e, e0 = a, b0 = c, c0 = b (of d), d0 = a (of c). Opgave 6. x z y a. p(x, y, z) = ((x ∧ y) ∨ (y ∧ z))0 . b. Met commutativiteit en distributiviteit vinden we: p(x, y, z) = ((x ∧ y) ∨ (y ∧ z))0 = ((y ∧ x) ∨ (y ∧ z))0 = (y ∧ (x ∨ z))0 . Het bijbehorende diagram staat hierboven. Opgave 7. a. Een postorder wandeling gaat als volgt: linkersubboom, rechtersubboom, wortel (recursief). We combineren steeds 2 opeenvolgende bladeren met de erachter staande operatie. Begin links. Eerst 4-2=2. Dan wordt de expressie: 2 2 6 3 ÷ + ×. Dan 6 ÷ 3 = 2, de expressie wordt 2 2 2 + ×. Dan 2 + 2 = 4, de expressie wordt 2 4 ×. Tenslotte 2 × 4 = 8. De waarde van de expressie is dus 8. De bijbehorende boom staat hieronder. b. Kies een willekeurig element van de string a1 , a2 , a3 , . . . , an , en label dit element als wortel. Plaats de elementen links ervan in een linker subboom, de elementen rechts ervan in een rechter subboom. Herhaal dit proces recursief voor de linker- en rechtersubbomen.
Discrete structuren, 4-4-2011
3
x _
+
2
2
4
:
6
3
Opgave 8. a. Een graaf G heet samenhangend als er een pad is van elke knoop van G naar elke andere knoop van G. b. Een samenhangende graaf is een boom als hij acyclisch is. c. ≡ is een equivalentierelatie. ≡ is per definitie reflexief. ≡ is symmetrisch, want er is gegeven dat de graaf ongericht is, dus als er een pad is van u naar v, dan ook van v naar u. Tenslotte is ≡ transitief, want als er een pad is van u naar v en een pad van v naar w, dan levert de samenstelling van deze paden een pad van u naar w. De equivalentieklassen zijn de samenhangende componenten (“connected components”) van G. d. Bekijk alle paden van u naar v, een kies een pad van kortste lengte. Zo’n pad is kan geen knoop w tweemaal bevatten, want anders zouden we het tussenstuk van w naar w kunnen weglaten en een korter pad vinden. Opgave 9.
a
3
c 3
1
2
e
2 1
b
4
d
a. Prim’s algoritme levert de volgende reeks kanten: {a, b}, {b, c}, {c, d}, {d, e}. Zie plaatje hierboven. b. Dit is niet altijd het geval. Als er drie kanten met gewicht w1 zijn die een cykel vormen kunnen deze nooit allemaal in de minimale opspannende boom terechtkomen (want een boom heeft geen cykels). Opgave 10. a. G5 heeft geen Euler circuit, want er zijn knopen met oneven graad. b. G5 heeft een Hamiltoniaans circuit a, b, d, e, c, a. c. G5 heeft K3 als subgraaf (knopen a, b, c, of knopen c, d, e), dus er zijn in elk geval 3 kleuren nodig. Maar daarmee kan het ook. B.v., a rood, b geel, c blauw, d rood, e geel. d. Een graaf heeft een Euler circuit d.e.s.d.a. elke knoop even graad heeft. Voor Kn is dat het geval als n oneven is, want in de volledige graaf Kn is elke knoop verbonden met alle andere n − 1 knopen. Kn heeft altijd een Hamiltoniaans circuit. Als de knopen genummerd zijn als 1, 2, . . . n, wandel dan bijvoorbeeld van knoop 1 naar 2, van 2 naar 3, . . ., van n − 1 naar n, en tenslotte van n naar 1. Zo’n pad is er altijd, omdat in Kn elke knoop verbonden is met elke andere knoop.
