LEKTION 03-29

Idag går vi genom några klasser av grafer.

Definition 0.1. Grafen G = (V, E) kallas bipartit om noderna kan delas upp i två disjunka delar V = V_{1} ∪ V_{2}, V_{1} ∩ V_{2} = ∅, sådan att varje kant är av formen ab där a ∈ V_{1} och b ∈ V_{2}.

Om varje nod i V_{1} är förbunda till varje nod i V_{2} får vi den fullständiga bipartit grafen. Denna betecknas K_{m,n} när |V_{1}| = m och |V_{2}| = n.

Exempel. Visa atta alla cykler i en bipartit graf är av jämn längt.

Låt γ vara en cykel som börjar och slutar i a ∈ V_{1}. Måste första och sista kant vara av formen ab_{1}, b_{n}a där b_{1}, b_{2} ∈ V_{2}. Cyklen är av formen ab_{1}a_{1}b_{2}a_{2}...b_{n}a där b_{i} ∈ V_{2} och a_{i} ∈ V_{1}. Vi ser att cyklen har jämn längd.

Definition 0.2. En sammanhängande graf utam cykler kallas en träd.

• Noder med graden 1 kallas löv.

Vi har att:

Sats Låt T = (V, E) vara ett träd, då

|E| = |V | − 1

Bevis. Vi ska bevisa det med hjälp an induktionen på |V |.

Om |V | = 1 vi måste ha |E| = 0, då är satsen sant. Antag att satsen gäller för varje träd med |V | = k. Vi ska visa at den gäller for en träd med |V | = k + 1. Låt ab vara en kant i T. Eftersom det finns bara den här kanten mellas a och b får vi två träd när vi tar borta ab från T. Beteckna dem med T_{1} = (V_{1}, E_{1}), T_{2} = (V_{2}, E_{2}). Enligt induktion |E_{1}| = |V_{1}| − 1 och |E_{2}| = |V_{2}| − 1. Eftersom |E| = |E_{1}| + |E_{2}| + 1 är vi klara.

Exempel Hur många icke-isomorfa träd med 6 noder finns det?

Definition 0.3. En fraf kallas planär om den (precist ska vi säga någon geometrisk representation av den) kan ritas i ett plan utan att några kanter skär varandra utanför noderna.

Grafer K_{1}, K_{2}, K_{3}, K_{4} är planära. Grafen K_{5} är inte planär.

Låt G = (V, E) vara en sammanhängande planär graf. Antalet delytor beteknar vi med r. Man kan visa att: Eulersats. Det gäller att:

|V | − |E| + r = 2

Så om K_{5} var en planär graf skulle man rita den i planet med 7 delytor. Den är faktiskt omöjligt!

Definition 0.4. En graffärgning är en färgning av noder sådan att grannar alltid har olika färg. Den minsta antal färger som behövs för en graffärgning kallas den kromatiska talet av krafen G och skrives χ(G).

En graf kan få många olika graffärgningar. Hur många? Exempel

• Herschels graf.

• χ(G) = 1 om och endast om G består av isolerade noder, dvs |E| = 0.

• Om G är sammanhängande och har n noder gäller att 2 ≤ χ(G) ≤ n.

• Varje bipartit graf G har χ(G) = 2.

• χ(K_{n}) = n Vi definerar P_{G}(λ) som antalet graffärgningar av grafen G med λ stycken färger. Man kan bevisa at P_{G}(λ) är ett polynom i λ och därför kallas det det kromatiska

polynomet Exempel 7.8 i boken.

Övning

(1) Låt C_{n} vara en cykel av läncg n. Bestäm n om χ(G) = 2.

(2) Betrakta grafen K_{n,m}. Bestäm graden av alla noder.

(3) Bestäm när K_{n,m} eulerisk.

(4) Bestäm alla icke-isomorfa träd med 7 noder.

(5) Visa med hjälp av Eulersats att K_{3}, 3 är inte planär.