Facit till rekommenderade uppgifter vecka 5

8.1.1

Nej

8.1.4

Ta exempelvis en graf med hörnen {1,2,3,4,5} och kanter som går från de första två jämna till alla de tre udda. På det viset får vi 6 kanter {12,14,23,25,34,45} och det kan inte finnas någon trecykel eftersom minst två av tre hörn har samma paritet, och det går då ingen kant mellan dem. Detta är ett exempel på en fullständig bipartit graf som vi betecknar K_2,3.

8.2.1

Den andra grafen saknar trecykler.

8.2.2

En isomorfi ges av s(a)=0, s(b)=1, s(c)=2, s(d)=8, s(e)=5, s(f)=7, s(g)=6, s(h)3=, s(i)=9 och s(j)=4, men det finns flera möjliga isomorfier.

8.3.1

(i) Nej. (ii) Ja. (iii) Nej. (iv) Nej.

8.3.5

Samma graf kan inte ha ett hörn med valens och ett av valens n-1, eftersom dessa hörn både skulle ha kant mellan sig och inte. Det finns däemed bara n-1 möjliga värden och n hörn som skall fördelas bland dessa. Duvlagsprincipen ger därför två hörn med samma valens.

8.4.1

3.

8.4.3

Följ tre kanter på en sida och gå sedan via en kant över till mostående sida. Där kan man nu följa tre kanter i motsatt riktning mot tidigare och sedan gå tillbaka till den första sidan.

8.5.1

Om vi skriver upp valenserna för hörnen i träden finns det fem möjligheter 2,2,2,2,1,1, 3,2,2,1,1,1, 3,3,1,1,1,1, 4,2,1,1,1,1 och 5,1,1,1,1,1. För den andra listan finns två möjliga träd, beroende på om de två hörnen av valens 2 har kant mellan sig eller inte. För resterande listor finns bara en variant av varje.

8.5.4

Eftersom ett träd med n hörn har n-1 kanter får vi totala antalet kanter som (n₁-1) + (n₂-1) + ... + (n_c-1) = n₁+n₂+...+n_c -c = |V|-c om skogen består av c träd med n₁, n₂, ..., respektive n_c hörn.

8.6.1

(i) n. (ii) 2. (iii) 3.

8.6.3

Om det går att färga grafen med en enda färg kan det inte finnas några kanter över huvud taget och det går ocskså att färga varje sådan graf med en färg.

8.8.1

För alla udda n finns en eulerväg i K_n, men för jämna n finns bara en eulerväg om n=2, eftersom det får finnas högst två hörn av udda valens.

8.8.4

I en bipartit graf finns inga cykler av udda längd. En Hamiltoncykel i en graf med ett udda antal hörn är en cykel av udda längd. Alltså kan det inte finnas några Hamiltoncykler i en bipartit graf med ett udda antal hörn.

8.8.5

(i) Varje hörn är förbundet med precis de hörn som man får genom at ändra ett tecken i ordet som namnger hörnet. Det finns k positioner att ändra på och det finns bara ett sätt att ändra. Alltså har alla hörn valens k. (ii) Om vi färgar hörnen med ett udda antal ettor med den ena färgen och de med ett jämnt antal ettor med den andra så får vi en tillåten hörnfärgning eftersom det inte går kanter mellan hörn med samma paritet. (Om vi ändrar en etta till en nolla eller tvärtom kommer antalet ettor antingen öka med ett eller minska med ett, och det går från udda till jämnt eller tvärtom.)

8.8.2

För m=1 har vi att antalet kanter i en graf med 2m=2 hörn är högst ett och det kan inte finnas några trecykler i en sådan graf. Alltså är |E| högst m² i det fallet.

Antag nu att detta gäller för alla grafer med 2m hörn. Vi vill nu visa att det också gäller för grafer med 2m+2 hörn. Om vi tar bort två hörn som det går en kant mellan finns det nu högst m² kanter kvar enligt induktionsantagandet. Vi har tagit bort ett antal kanter, men eftersom det inte finns några trecykler kan inte de två hörnen vi tagit bort ha kant till samma hörn. Det går därmed högst 2m kanter från dessa två hörn till de övriga 2m hörnen. Å andra sidan gick det en kant mellan de två hörnen. Alltså finns högst m² + 2m +1 = (m+1)² kanter i grafen. Vi har nu visat att kriteriet gäller för grafer med 2m+2 hörn om det gäller för grafer med 2m hörn. Enligt induktionsprincipen gäller kriteriet för grafer med 2m hörn för alla positiva heltal m.

10.1.1

Kantmängden blir {{2,100},{2,102},{3,99},{3,102},{5,100},{11,99}} och vi får att de två summorna blir 2+2+1+0+1=6, respektive 2+2+0+2+0=6.

10.1.2

(i) s. (ii) r. (iii) rs.

10.2.1

(i) 3. (ii) 5. (iv) 3.

10.2.3

Färga kanterna med färgerna 0,1,2,...,n-1 så att kanten mellan x_i och y_j får färg k om skillnaden mellan i och j ger rest k vid division med n.

10.3.1

Om vi numrerar kolonnerna 1,2,3,4,5 får vi en bipartit graf från den givna rektangeln och den komplementära bipartita grafen ges av kanterna {1D,1E,2A,2E,3A,3D,4B,4C,5B,5C}. Denna består av två kompontenter och vi kan välja färgningarna av dessa oberoende av varandra på två sätt. Vi får därför fyra möjligheter för de två sista raderna DEABC och EADCB, DEACB och EADBC, i någon ordning.

10.3.3

Om vi kallar kvadraten för A kan vi bilda en större kvadrat genom

A	B
B	A

om vi har en annan latinsk kvadrat B med n andra symboler.

10.4.1

De gemensamma grannarna till {x₂,x₃,x₄} är {y₂,y₄}.

10.7.16

Använd samma princip som i 10.2.3 och ta bort de sista hörnen på ena sidan.

10.7.17

Om det fanns en kantfärgning av en k-regulär graf med k färger måste kanterna från varje hörn ha alla k färger. Om n är antalet hörn och vi räknar antalet kanter med en viss färg får vi n/2 eftersom vi räknar varje kant två gånger. För att detta skall vara ett heltal krävs att n är jämnt, och det går inte att färga med k färger om n är udda.