KTH Matematik

5B1118 Diskret Matematik Lösningar till Kontrollskrivning 3 Fredagen den 1 22 Mars, 2004

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

• Bestäm |V | om |E| = 9 och varje nod har grad 3. Låt |V | = n. Vi har att:

∑_{v∈V} deg(v) = 3n = 2|E| = 18

Så n = 6.

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

[figure]

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

G är sammangande. Eftersom alla noder har odd grad kan G inte vara en eulerskgraf.

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

G_{1} = [figure] G_{2}= [figure] Två isomorfa grafer måste ha motsvarande noder av samma graed. Efter ger man en ordning till noder i G_{1} pch G_{2} kan man skriva sekvensen av

grader i G_{1}, γ_{G_{1}}, och sekvensen av grader i G_{2}, γ_{G_{1}}:

γ_{G_{1}} = (3, 3, 3, 3, 4)
γ_{G_{2}} = (2, 3, 3, 4, 4)

Det visar att G_{1} och G_{2} inte är isomorfa.

(3) • 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} )

G har 5 noder, v_{1}, v_{2}, ..., v_{5} av grad (1, 2, 2, 2, 3), och 5 kanter. Enligt matrisen har vi:

[figure]

• Är G en träd? (Motivera ditt svaret.) G innehåller en cykel (av längd 4) då inte är en träd.

• Bestäm χ(G).

For varje graf är χ(G) ≥ 2. Man kan ha en graffärgning av G med 2 färger A,B:

[figure: A; B; B; A; A]

då är χ(G) = 2.