Grafer I

Referenser

[EG]   avsnitt 6.1, 5.4, 5.5 (ej 5.5.1), 6.2, 6.3 (ej 6.3.3);
och nedanstående text.

Nyckelord

Grafer, terminologi för grafer, Euler och Hamilton, modellering med grafer. Permutationer, kombinationer.

Inledning

Denna del av den diskreta matematiken är mycket spännande. Många av problemen är väldigt lätta att förstå, men lösningarna kan vara så svåra att det nästan krävs en doktorsexamen för att ens kunna inse riktigheten i dem! Flera problem som vi möter varje dag kan modelleras med grafteori. De följande är några exempel.

Hur kan en utslagsturnering i tennis arrangeras så att precis fyra spelare återstår till semifinalerna? Hur ska kablarna dras så att kostnaden för bredband till alla i Sverige blir så låg som möjligt? Hur reser man billigast från Söråker till Birmingham i England? Hur kan bensenmolekyler vara sammansatta?

Hur ska scheman läggas så att konflikter undviks, d.v.s. så att varje student bara har en lektion i taget? Hur är det möjligt att ge var och en av tio frivilliga ett av tio arbeten de är kvalificerade för? Hur många färger behövs för att färga en karta så att länder med gemensam gräns ej färgas i samma färg? Hur bör man färdas om man vill besöka alla vinslotten i Frankrike med så kort resväg som möjligt? Bredd-först och djup-först sökmetoderna är baserade på träd, som är en speciell slags grafer.

1. Grafer

Läs nu inledningen till kapitel 6 i [EG] och avsnitt 6.1 t.o.m. sidan 144. Här introduceras  grafer.

Grafteori är inte konsekvent när det gäller terminologi, dvs. olika böcker använder olika ord för samma sak.  På engelska finns det åtminstone två uppsättningar med terminologi, och några blandar dem t.o.m. Byter man bok om grafteori är det väldigt viktigt att kontrollera vilka definitioner som används i den nya boken. Som exempel, en stig (path) som uppfyller definition sidan 141 [EG] tillåter inte att hörn och kanter upprepas,  medan man i annan litteratur tillåter båda upprepade hörn och upprepade kanter i en stig. Var uppmärksam på detta!

Notera att en graf består av hörn (vertices) och kanter (edges) och inte punkter och linjer. En möjlig förklaring till varför vi inte säger punkter och linjer är den följande. En linje går igenom flera punkter men en kant har bara hörn vid sina ändpunkter. En linje skapar en idé om en given form, d.v.s. en rak linje, medan en kant kan vara krokig som en slalombacke!

Vid visst datorarbete kan det ibland vara fördelaktigt att studera grafer utan hörn men vi ska i denna kurs studera grafer med åtminstone ett hörn.

Innan vi kan fortsätta med grafer måste vi lära oss lite kombinatorik:

2. Permutationer och kombinationer

Läs nu [EG] 5.4. I detta avsnitt introduceras begreppet permutation. Generellt kallas en permutation av r objekt från en mängd med n element en r-permutation från n objekt, och är helt enkelt en ordnad lista av r objekt utvalda bland de n objekt i mängden utan upprepad användning av samma element.

Exempel
Låt t.ex. M = {a, b, c, d, e, f}, då är (a,b,c), (b,a,c), (f,a,b) och (b,a,f) exempel på 3-permutationer från M (Finns det fler?). Observera att vi använder rundade parenteser '(' och ')' omkring permutationer, eftersom permutationer är ordnade listor av element och inte bara mängder, dvs. permutationerna (a,b,c) och (b,a,c) är  olika, fastän de består av  samma element.

Antalet  r-permutationer från en mängd med n element kallas

P(n, r),
och det kan visas att (jmf. [EG] Sats 5.5 sida 117, att

P(n, r)

=

n!  (n - r)!

Exempel
Låt t.ex. M = {a, b, c, d, e, f}. Antalet  3-permutationer från M är P(6, 3) = 6x5x4 =120.
 

När vi beräknar permutationer, är ordningen av  elementen viktig, dvs. när vi har samma element, men i en annan ordning, så är de två permutationerna olika.

Läs nu [EG] avsnitt 5.5, här definieras det nästa nya begrepp: kombinationer. Här är ordningen av elementen utan betydelse. En r-kombination från en mängd M med n element är endast en delmängd av M, som innehåller r av M:s element.

Exempel
Låt M = {a, b, c, d, e, f}, då är t. ex. {a, b, c} och {f, a, b} exempel på 3-kombinationer från M. Observera att vi använder krullparenteser '{' och '}' omkring kombinationer, eftersom kombinationer är mängder, dvs. oordnade listor av element. Kombinationerna {a,b,c} och {b,a,c} är alltså desamma, eftersom de innehåller precis samma element, och ordningen av elementen saknar betydelse.
 

Om du har träffat på antalet  r-kombinationer från en mängd med n element kallas  i gymnasiet har du säkert använd notationen C(n, r) för dessa. Det kan visas att

C(n, r)

=

P(n, r) r!

Dvs. vi har att

C(n, r)

=

n! r! (n - r)!

Exempel
Låt t.ex. M = {a, b, c, d, e, f}. Antalet  3-kombinationer från M är C(6, 3) = (6x5x4)/(3x2x1) =20.

Notationen C(n, r) för att beteckna antalet r-kombinationer, är inte helt standard. De flesta författare ( t.ex. [EG] använder notationen

(

n r

)

=

C(n, r).

Exempel
Låt t.ex. M = {a, b, c, d, e, f}. Antalet 3-kombinationer från M är

(

6 3

)

=

C(6, 3)  = 20.

Du skall känna till och kunna använda båda notationerna för kombinationer.

3. Euler och Hamilton

Läs nu [EG] 6.2.

4. Modellering med grafer

Läs nu [EG] 6.3 kursivt.

5. Förslag till övningsuppgifter

Övningsuppgifter från [EG] kapitel 5, 6:

6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 6.7, 6.9
5.27, 5.28, 5.29, 5.31, 5.32, 5.34, 5.35
5.37, 5.38, 5.41, 5.42, 5.45, 5.46, 5.47
6.10, 6.11, 6.12, 6.13, 6.16,
6.18, 6.19, 6.20, 6.21, 6.22, 6.23,
6.24, 6.25, 6.26, 6.27, 6.28, 6.29,
6.31, 6.32, 6.33, 6.34,
6.90, 6.91.

Week Exercise 8

Uppgifter 5.78, 5.91(a) och 6.91 i [EG].