DISKREETTI MATEMATIIKKA Harjoitus 8, syksy 2005 1. Ovatko seuraavat suunnatut verkot isomor set? a) •

DISKREETTI MATEMATIIKKA Harjoitus 8, syksy 2005

1. Ovatko seuraavat suunnatut verkot isomorset?

a)

• •^//

•

•

OO

•

]]::::::

oo

•

oo •::::::

•

• •^//

OO AA

b)

•

//•

• ^//

..

•

mm

•

OO

oo • PP

•

•

•

{{wwwww^dd •

jj !!CCCC

•

::

ii •

2. Määrää vahvasti yhtenäiset komponentit suunnatulle verkolle D:

?>=<

89:;x1 //?>=<89:;x2

))?>=<

89:;x3

//?>=<89:;x4

?>=<

89:;x5

||

?>=<

89:;x6

uu OO

GFED

@ABCx11 GFED@ABCx10 66

<<

?>=<

89:;x9 //?>=<89:;x8

OO

?>=<

89:;x7

OO

hhRRRRRRRRRRRRRRRRRRRRRRRRRR

3. Ovatko seuraavat suunnatut verkot vahvasti yhtenäiset? Onko niissä Eu- lerin polkuja? Perustele vastauksesi.

D₁:

•

oo •

oo •

•

??????

? •

oo //•

__??????? //

•

__???????

qq

• •^{// //}

OO

• •^//??

__???????

OO D₂:

•

,,•



•

33g

gg gg gg gg gg gg gg

gg •

__??????

^oo • •

kkWWWWWWWWWWWWWWWW

•

RR 22•

__?????? NN

4. Olkoot f₁ ∈ O(g₁)ja f₂ ∈ O(g₂). Osoita, ettäf₁f₂ ∈ O(g₁g₂).

5. Olkoot a, b >1. Osoita, että log_an ∈Θ(log_bn) ja bⁿ≺ n!. Käytä jälkim- mäisessä relaation≺ ja raja-arvojen yhteyttä.

6. Valitse (ja perustele valintasi) joukosta{1, n^k,logn, nlogn, kⁿ}, missäk ∈ Z+, funktio g, jolle f ∈Θ(g), kun

a)f(n) = n⁴+ 6n²−8n−5, b) f(n) =nlogn+n², c)f(n) = 30, d) f(n) = 1 + 2 +· · ·+n,

e)f(n) = 1 + 2 + 2²+· · ·+ 2ⁿ, f) f(n) = log(an+b), a, b∈R+.