Övning 2: Hur många kanter har den kompletta grafen K₇?

Komplett graf Kₙ har n(n-1)/2 kanter För K₇: 7×6/2 = 42/2 = 21 kanter Alternativt: C(7,2) = 7!/(2!×5!) = 21 sätt att välja 2 noder från 7 Svar: 21 kanter

Grundläggande

Grundläggande grafteori

Grafer, noder, kanter och grundläggande grafegenskaper.

graf nod kant grad väg cykel

Tänk på kartan över stockholms tunnelbana - stationer förbundna med linjer, eller ditt sociala nätverk på Facebook där vänskap förbinder människor. Detta är grafer! Inte grafer med x- och y-axlar, utan nätverk av punkter (noder) förbundna med linjer (kanter). Grafteori hjälper oss att förstå och analysera sådana nätverk, från internets struktur till hjärnans neurala kopplingar.

Fördjupning

En graf G = (V, E) består av en mängd noder (vertices) V och en mängd kanter (edges) E som förbinder paren av noder. Grafteori studerar egenskaper hos dessa strukturer som sammanhang, vägar, cykler och grader. Detta ger oss verktyg för att lösa problem inom nätverk, schemaläggning, optimering och mycket mer.

Definition av grafer

En graf G = (V, E) består av en ändlig mängd noder V och en mängd kanter E där varje kant förbinder två noder. Kanter kan vara riktade (ordnade par) eller oriktade (mängder av två element). En graf kallas enkel om den inte har parallella kanter eller självloopar.

Definition av graf: G = (V, E) där V är noder och E \subseteq V \times V är kanter

Exempel på grafer

Graf G = (V, E) med:

· V = {A, B, C, D} (fyra noder)

· E = {(A,B), (B,C), (C,D), (D,A), (A,C)} (fem kanter)

Speciella grafer:

· Komplett graf Kₙ: alla möjliga kanter finns

· Cykkel Cₙ: noderna bildar en sluten cykel

· Stjärna: en central nod förbunden till alla andra

Visualisering av olika grundläggande graftyper

Grader och gradsekvenser

Graden av en nod är antalet kanter som är förbundna till noden. I riktade grafer skiljer vi mellan ingrad (kanter in till noden) och utgrad (kanter från noden). Gradsekvensen är listan av alla noders grader i ordning.

Definition av nodgrad: deg(v) = antalet kanter incident till v

Handskakningssatsen: Σ deg(v) = 2|E| för alla noder v

Beräkning av grader

Graf med noder {A,B,C,D} och kanter {AB, BC, CD, DA, AC}

deg(A) = 3 (förbunden till B, C, D)

deg(B) = 2 (förbunden till A, C)

deg(C) = 3 (förbunden till A, B, D)

deg(D) = 2 (förbunden till A, C)

Summa grader: 3+2+3+2 = 10 = 2×5 kanter ✓

Handskakningssatsens tillämpning

Konsekvenser:

· Summan av alla grader är alltid jämn

· Antalet noder med udda grad är alltid jämnt

· I en social nätverk: totala antalet vänskapsrelationer = (summa av alla personers antal vänner) / 2

Vägar och sammanhang

En väg (path) i en graf är en sekvens av noder där varje par av konsekutiva noder är förbundna med en kant. En enkel väg innehåller inga upprepade noder. En graf är sammanhängande om det finns en väg mellan varje par av noder.

Definition av väg: sekvens v₁, v₂, ..., vₖ där (vᵢ, vᵢ₊₁) \in E

Exempel på vägar, enkla vägar och sammanhang i grafer

Analys av sammanhang

Graf G med noder {1,2,3,4,5} och kanter {12, 23, 45}

Väg från 1 till 3: 1→2→3 (längd 2)

Ingen väg från 1 till 4 (olika komponenter)

Graf har 2 sammanhängande komponenter: {1,2,3} och {4,5}

Cykler och träd

En cykel är en väg som börjar och slutar i samma nod utan att upprepa andra noder. En graf utan cykler kallas acyklisk. Ett träd är en sammanhängande acyklisk graf. Träd har många speciella egenskaper och är fundamentala strukturer.

Definition av cykel: väg v₁, v₂, ..., vₖ, v₁ där alla vᵢ är distinkta

Träd egenskaper: sammanhängande \land acyklisk ⟺ |E| = |V| - 1

Identifiering av cykler

Graf med kanter {AB, BC, CD, DA}:

· Cykel: A→B→C→D→A (längd 4)

· Ta bort en kant → träd

· Lägg till en kant → flera cykler

Exempel på cykler och träd med olika strukturer

Speciella graftyper

Vissa graftyper förekommer så ofta att de har egna namn och egenskaper. Kompletta grafer, bipartita grafer, reguljära grafer och planära grafer har alla specifika tillämpningar och teoretiska betydelse.

Komplett graf Kₙ: varje par av noder är förbundet, |E| = n(n-1)/2

Bipartit graf: V = A \cup B, A \cap B = \emptyset, alla kanter mellan A och B

Bipartita grafer i praktiken

Exempel på bipartita grafer:

· Studenter och kurser (kanter = 'tar kursen')

· Jobb och kandidater (kanter = 'kvalificerad för')

· Kunder och produkter (kanter = 'köpt produkten')

Egenskap: Bipartita grafer innehåller inga udda cykler

Visualisering av kompletta, bipartita och reguljära grafer

Grafrepresentationer

För att lagra och bearbeta grafer i datorer använder vi olika representationer. Adjacency-matriser är bra för täta grafer, adjacency-listor för glesa grafer, och edge-listor för vissa algoritmer. Valet av representation påverkar algoritmers effektivitet.

Adjacency-matris: A[i,j] = 1 om kant finns mellan nod i och j

Jämförelse av representationer

Graf med 4 noder {A,B,C,D} och kanter {AB, BC, AD}:

Adjacency-matris (4×4):

```

A B C D

A 0 1 0 1

B 1 0 1 0

C 0 1 0 0

D 1 0 0 0

```

Adjacency-listor:

A: [B, D]

B: [A, C]

C: [B]

D: [A]

Visualisering av olika sätt att representera samma graf

Vanliga misstag

❌ Förväxla graf med funktionsgraf

Grafer i grafteori är nätverk av noder och kanter, inte koordinatsystem med x- och y-axlar

Exempel: En 'graf' i grafteori kan vara ett socialt nätverk, inte en kurva y = f(x)

❌ Räkna fel antal kanter i komplett graf

Komplett graf med n noder har n(n-1)/2 kanter, inte n² kanter

Exempel: K₄ har 4×3/2 = 6 kanter, inte 16 kanter

❌ Glömma handskakningssatsen

Summan av alla grader måste vara jämn (dubbelt så många som antal kanter)

Exempel: En graf kan inte ha grader [1, 2, 3] eftersom 1+2+3 = 6 är jämnt, men kan ha [1, 1, 2]

Tillämpningar

Sociala nätverk

Vänskap, följare och kontakter modelleras som grafer för att analysera påverkan och communities

Exempel: Facebook använder grafteori för att föreslå vänner och analysera informationsspridning

Transportnätverk

Vägar, flygrutt och kollektivtrafik representeras som grafer för routning och optimering

Exempel: GPS-system använder grafalgoritmer för att hitta kortaste vägen mellan destinationer

Datastrukturer

Träd används för hierarkiska strukturer, grafer för allmänna relationer

Exempel: Filsystem (träd), webbsidor och länkar (riktad graf), databas-relationer (graf)

Övningar

1 Lätt

En graf har 6 noder med grader 2, 2, 3, 3, 4, 4. Hur många kanter har grafen?

Tips

Använd handskakningssatsen

Visa facit

Summa av grader = 2+2+3+3+4+4 = 18
Enligt handskakningssatsen: Σ deg(v) = 2|E|
18 = 2|E|
Därför |E| = 9 kanter

Svar: 9 kanter

2 Lätt

Hur många kanter har den kompletta grafen K₇?

Tips

I komplett graf är alla par av noder förbundna

Visa facit

Komplett graf Kₙ har n(n-1)/2 kanter
För K₇: 7×6/2 = 42/2 = 21 kanter
Alternativt: C(7,2) = 7!/(2!×5!) = 21 sätt att välja 2 noder från 7

Svar: 21 kanter

3 Medel

Bevisa att i en graf med minst 2 noder finns det alltid minst 2 noder med samma grad.

Tips

Använd duvhålsprincipen och tänk på möjliga gradvärden

Visa facit

Graf med n noder: möjliga grader är 0, 1, 2, ..., n-1
Men grad 0 och grad n-1 kan inte båda förekomma
(grad 0 = isolerad nod, grad n-1 = förbunden till alla andra)
Därför max n-1 olika gradvärden för n noder
Enligt duvhålsprincipen: minst 2 noder har samma grad

Svar: Sant enligt duvhålsprincipen

Sammanfattning

Grafer består av noder förbundna med kanter och modellerar relationer i nätverk. Viktiga begrepp inkluderar nodgrader (handskakningssatsen), vägar och sammanhang, cykler och träd. Speciella graftyper som kompletta och bipartita grafer har unika egenskaper. Olika representationer (matriser, listor) passar olika tillämpningar. Grafteori är grunden för att analysera nätverk från internet till sociala medier.