LEKTION 03-24

Lt a, b vara noder i en graph G. En väg från a till b defineras som en elternande foljd av noder och kanter

a = a_{0}, e_{1}, a_{1}, e_{2}, ..., e + n, a_{n} = b

sådan att e_{i} = a_{i−1}a_{i} och sådan att inte använder samma kant flera gånger. Talet n kallas vägens längt.

Vi ska betekna vägen bara med a_{1}a_{2}...a_{n}.

• Två noder a och b kallas grannar om ab är en kant i grafen.

• En väg som passerar varje nod högst en gång kallas en enkel väg eller en stig.

• En väg som börjar och slutar i samma nod och som passerar andra noder högst en gång kallas en cykel.

• En väg som inte är en cykel kallas en oppen väg.

Exempel.

K_{5} : [figure: e; c; d; a; b]

abcde är en enkel oppen väg från a till e, av längt 4. abcdbe är en icke-enkel väg från a till e av längt 5. Övning: Beräkna alla cyklar i K_{5}.

Avståndet mellan två noder a, b är längden av den kortaste väg från a till b. Vi ska betekna det med: av(a, b)

Exempel.

• Avståndet mellan varje par noder i K_{n} är lika med 1.

• Betrakta grafen W_{4}: [figure: a; b; c; d; e]av(d, e) = 1, av(e, a) = 2.

1

Definition 0.1. Låt G = (V, E) vara en enkel graf och v ∈ V vara en nod av G. Med valensen eller graden av v, deg(v), menas antalet kanter som är ändpunkt i v.

Exempel.

För varje nod v i K_{n} gäller deg(v) = n − 1. Valencer av noder berår på antalet kanter, på grund av följande satsen:

SATS. Låt G = (V, E) vara en enkel graf. Då är:

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

Bevis. Varje kant e = ab ger bidraget 1 till deg(a) och deg(b). Så varje kant ger bidraget 2 till ∑_{v∈V} deg(v).

Exempel.

• Det är klart att om en graf har n noder är 0 ≤ deg(v) ≤ n − 1 för varje nod v.

Om en graf G har n noder och deg(v) = n−1 för varje nod i G är alla par noder förbunda. Så G = K_{n}.

Om G ≠ K_{n} kan man säga att deg(v) ≤ n − 2 för någon nod i G.

• Om en graf har alla noder med udd grad så är antalet noder jämt.

• En enkel graf har 20 kanter, och alla noder har samma grad. Hur många noder

har grafen?

Antag att grafen har n stycken noder och deg(v) = k för varje nod v. Det gäller att

kn = 2 · 20 = 2^{3} · 5

Det finns alltså 4 olika alternativ:

(1) n = 40, k = 1: [figure]

(2) n = 20, k = 2 [figure]

(3) n = 10, k = 4: [figure]

(4) n = 8, k = 5 [figure]

Grafen (a) är en ej-sammanhängande (connected) och har 20 komponenter.

Definition 0.2. En graf kallas sammanhängande om varje två noder kan förbindas.

En nod som är inte förbindat till ingen annan nod kallas isolerade.

Definition 0.3. Låt G vara en graf. Då kallas grafen G′ = (V′, E′) en delgraf till G om ∅ ≠ V′ ⊆ V och E′ ⊆ E.

Notera att varje graf med n noder kan tänkas son en delgraf av en kompletta graf K_{n}. Då kan vi definera:

Definition 0.4. Låt G vara en graf med n noder. Med komplement \overline{G} menas den delgraf av K_{n} som innehåller alla noder av G och alla kanter som inte finns i G.

Exempel. Låt G vara en enkel grak med n noder sådan att G har 175 kanter och dess komplement 56 kanter. Brstäm n.

grafen K_{n} har \binom{n}{2} kanter, dt här talet måste vara lika med antalet kanter i G plus antalet kanter i \overline{G}:

231 = 175 + 56 = \binom{n}{2} ↔ 231 = \frac{n(n − 1)}{2}

Vi ska lösa ekvationen n^{2} − n − 462 = 0 som har lösningar n = 22, −21. Det är klart att n = −21 är ejgodkänt, så svaret är n = 22.

Övning

(1) Sju städer A, B, C, D, E, F, G är förenade med ett vägsystem på följande sätt: • En väg går mellan A och C och passerar därvid B.

• En väg går från C till i ordning D, B, F.

• En väg går från D genom E till A.

• en väg går från F till B via G.

• en väg går mellan D och G.

(a) Rita en graf med städerna som noder som beskriver denna situation.

(b) Ange alla enkla vägar från G till A.

(c) Är det möjlight att starta i C och passera samtliga städer precis en gång och

sedan återvända till C?

(2) Bestäm |V | om grafen G = (V, E) har 9 kanter och varje nod har grad 3.

(3) En viss graf G har n noder, alla av grad 4, I dess komplement har alla noder grad 6. Bestäm n.

(4) Hur många delgrafer H = (V, E) i K_{6} uppfyller |V | = 3?

(5) Antag att grafen G har 20 stycken kanter och att alla noder har samma grad. Hur många noder har grafen?

(6) Visa att om G är en sammanhängande graf finns det en enkel väg mellan två godtyckliga noder.