5B1118 Diskret Matematik Kontrollskrivning 3 Fredagen den 2 April, 2004

• Skrivtid:9:15-10:15.

• Tillåtna hjälpmedel: Miniräknare med sifferdisplay.

• \underline{Motivering krävs}!

• För godkänt resultat krävs minst 5 poäng. Personnummer:

Namn:

(1) (3p) Låt G = (V, E) vara en enkel graf.

• Bestäm |V | om |E| = 9 och varje nod har grad 3.

• Ge en geometrisk representation av G, dvs rita grafen G.

• Är G en eulersk graf?(Motivera ditt svar)

(2) (3p) Avgör om dessa grafer är isomorfa.(Motivera ditt svar).

G_{1} = [figure] G_{2}= [figure]

(3) (3p)

• Rita en graf med incidensmatris:

A_{G} = ( \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \end{matrix} )

• Är G ett träd? (Motivera ditt svaret.)

• Bestäm χ(G).

betyg: Upp.(1) Upp. (2) Upp. (3) Tot.

2

KTH, Matematik, 5B1118, KS3. Namn:

3

KTH, Matematik, 5B1118, KS3. Namn:

4

KTH, Matematik, 5B1118, KS3. Namn: