Oppgave 1

a)

Det er 5 valg for hvilket hjul som plasseres i spor I. Deretter gjenstår det 5-1 = 4 valg for hvilket hjul som plasseres i spor II. Til slutt er det 5-2 = 3 valg for hjulet i spor III. Samlet er det 5 x 4 x 3 = 60 mulige valg.

b)

Det er 26 innstillinger for hvert av de tre hjulene, samlet 26 x 26 x 26 = 17 576 ulike innstillinger.

c)

26 elementer kan deles i 10 grupper av 2 elementer (par) og 6 grupper av 1 element på 26!/((2!)^10 1!^6) = 26!/2^10 ulike måter, når de 10 og 6 gruppene er nummerert. Det er 10! x 6! ulike måter å nummerere gruppene, så antallet mulige ombyttinger av tegn er 26!/(2^10 x 10! x 6!) = 150 738 274 937 250 = 1,50738 x 10^14.

Oppgave 2

a)

La x og y være to hjørner i den simple homogene grafen G. Det finnes en isomorfi f fra G til G som tar y til y = f(x). Det er da en kant i G mellom x og et hjørne h hvis og bare hvis det er en kant i G mellom y og f(h). Spesielt er det like mange kanter i G med en ende i x som det er kanter i G med en ende i y. Derfor har x og y samme grad. Siden x og y var vilkårlig valgt, har alle hjørnene i G samme grad.

b)

Grafen G har n hjørner, som alle har samme grad. Hvis graden er et oddetall, så har G n hjørner av odde grad. Ved “handshaking lemma” er antallet hjørner av odde grad alltid et partall, så n må da være et partall. Det følger at hvis n er et oddetall, så kan ikke graden til hjørnene være et oddetall, dvs. den felles graden til hjørnene er et partall.

c)

Det er tre isomorfi-klasser:

(1) Grad 0: en graf med fem hjørner og ingen kanter.

(2) Grad 2: en regulær femkant (eller et pentagram).

(3) Grad 4: den komplette grafen på 5 hjørner.

Oppgave 3

a)

Hver kant i grafen G er sydd sammen av to kanter fra lappene. Hver av de P femkantede lappene har 5 kanter, og hver av de H sekskantede lappene har 6 kanter. Til sammen er det 5P + 6H kanter på lappene, og det blir halvparten så mange kanter i grafen, dvs. E = (5P + 6H)/2.

b)

Hver kant i grafen har 2 ender, så det er 2E = 5P + 6H kant-ender. I hvert hjørne kommer det 3 kantender sammen, så antallet hjørner er en dredjedel av antallet kant-ender, dvs. V = 2E/3 = (5P + 6H)/3.

c)

Fra Eulers formel er

V – E – F	= (5P + 6H)/3 – (5P + 6H)/2 + (P + H)

= (5/3 – 5/2 + 1)P + (6/3 – 6/2 + 1)H

= (1/6)P

lik 2, så (1/6)P = 2 og P = 12. Det er alltid 12 femkantede lapper.

2005-04-11T13:39:40