Föreläsningar 1,2 (03,05/04/02)

Vi börjar med en rad definitioner :

Definition 1.1 : En (ändlig) graf G = (V, E) består av en ändlig mängd V = {v_{1}, ..., v_{n}} och en samling E av 2-element delmängder till V.

Elementen av V kallas för grafens noder och elementen av E för dess kanter. En kant {v_{i}, v_{j}} kallas för en kant mellan v_{i} och v_{j}.

I en multigraf tillåter vi multipla kanter mellan samma par av noder. I en enkel graf tillåts högst en kant mellan varje par av noder.

Obs! Både enkla och multigrafer uppstår i en rad praktiska problem. Av de viktiga satserna i grafteori finns det alltså många som gäller för både enkla och multigrafer, men också många som gäller (t.o.m. är meningsfulla) BARA för enkla grafer - var försiktig alltså !

Notation : |V |, |E| ska beteckna antalet noder resp. kanter i en graf.

Definition 1.2 : En riktad graf G = (V, E) är samma sak som en graf med det viktiga undantaget att E består nu av ORDNADE par av noder. Paret (v_{i}, v_{j}) kallas nu för en kant från v_{i} till v_{j}.

Obs! En hel del av terminologin i grafteori är olika för riktade och ickeriktade grafer. Det är inte alltid intuitivt klart vilken för vilket alternativ en viss term gäller, så man måste helt enkelt lära termerna utantill.

Också, det finns en del satser som gäller både för riktade och icke-riktade grafer, trots att de flesta gäller för bara den ena eller den andra. Alltså, i fortsättningen ska vi adoptera fölajnde konventioner :

Ordet ‘graf’ ska betyda antingen en riktad eller icke-riktad graf’. Betekningen R-graf ska stå för ‘riktad graf’. Beteckningen IR-graf ska stå för ‘en icke-riktad graf som kan vara antingen enkel eller en multigraf’. Beteckningen IRE-graf ska stå för ‘icke-riktad enkel graf’.

Definition 1.3 : Den underliggande grafen av en R-graf G är den IRgraf man får om man ignorerar riktningarna av kanterna i G.

Definition 1.4 : Låt x, y vara noder i en IR-graf G. En väg (path) från x till y är en sekvens av kanter i G som tar man från x till y. Om x = y då pratar man om slutna vägar eller cyklar (cycles). En väg kallas för enkel om den inte går igenom någon nod mer än en gång. En cykel kallas för enkel om vi får en enkel väg när vi tar bort den första (eller sista) kanten i cykeln.

Motsvarande termerna för R-grafer är kedje, sluten kedje eller circuit, enkel kedje och enkel circuit.

Definition 1.5 : En IR-graf G kallas för sammanhängande om, för varje par v, w av noder i G, det finns minst en väg i G mellan v och w.

En R-graf kallas för svagt sammanhängande om, för varje par v, w ∈ V (G), det finns antingen en kedje från v till w eller en kedje från w till v. En R-graf kallas för starkt sammanhängande om, för varje par v, w ∈ V (G), det finns både en kedje från v till w och en kedje från w till v. En R-graf kallas för sammanhängande om den underliggande IR-grafen är sammanhängande.

Det är klart att, för en R-graf

skarkt sammanhängande ⇒ svagt sammanhängande ⇒ sammanhängande.

Proposition 1.6 Låt G = (V, E) vara en IR-graf. Då finns det unika uppdelningar

V = V_{1} ⊔ V_{2} ⊔ ⋯ ⊔ V_{k},
E = E_{1} ⊔ E_{2} ⊔ ⋯ ⊔ E_{k},

så att

(i) varje V_{i} ≠ ϕ, (ii) E_{i} består av alla kanter i G som går mellan ett par noder i V_{i} (som medför att det finns inga kanter i G mellan noder i två olika V_{i}), (iii) graferna G_{i} = (V_{i}, E_{i}) är sammanhängande.

Bevis : Vi avstår därifrån.

Graferna G_{i} i Prop. 1.6 kallas för de sammanhängande komponenterna av G.

Exempel 1.7 : ‘Königsberg (= Kaliningrad nuförtiden) bro problemet’ betraktas som ursprungen av grafteori. Leonhard Eulers studiet av problemet ledde till

Definition 1.8 : En Euler väg (resp. cykel) i en IR-graf G är en väg (resp. cykel) som korser varje kant av G precis en gång. I R-grafer pratar man om Euler kedjar och circuits.

Definition 1.9 : Låt G vara en IR-graf och v en nod i G. Antalet kanter i G som går igenom v kallas för graden av v och betecknas deg(v).

Låt G vara en R-graf och v ∈ V (G). Antalet kanter som går in mot v kallas för in-graden av v och betecknas indeg(v). Antalet kanter som går ut från v kallas för ut-graden av v och betecknas outdeg(v).

Sats 1.10 (i) En IR-graf har en Euler cykel om och endast om varje nod har jämn grad. (ii) Låt G vara en IR-graf och v, w ∈ V (G) där v ≠ w. Då har G en Euler väg mellan v och w om och endast om både deg(v) och deg(w) är udda, och graden av varje annan nod är jämn. (iii) En R-graf G har en Euler circuit om och endast om indeg(v) = outdeg(v) för varje v ∈ V (G). (iv) Låt G vara en R-graf och v, w ∈ V (G), där v ≠ w. Då har G en Euler kedje från v till w om och endast om följande tre villkor satisfieras -

(a) outdeg(v) = indeg(v) + 1,

(b) indeg(w) = outdeg(w) + 1,

(c) outdeg = indeg för alla kvarstående noder i G.

Bevis : Det är lätt att se att de olika villkoren är nödvändiga. Vi avstår för tillfället ifrån beviset av deras tillräcklighet, men återkommer under en senare föreläsning.

Ett enklet men viktigt faktum om grader av noder är

Proposition 1.11 Låt G vara en graf. Då är summan av graderna av alla noderna i G ett jämnt tal. Mer precis,

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

Bevis : Varje kant av G räknas två gånger på VL.

Exempel 1.12 : NFL problemet.

Definition 1.13 : En Hamilton väg i en IR-graf G är en väg som går igenom varje nod precis en gång. En Hamilton cykel är en cykel så att vi får en Hamilton väg när vi tar bort den första (eller sista) kanten i cykeln.

I R-grafer pratar man naturligtvis om Hamilton kedjar och circuits.

Det är väldigt svårt att avgöra om en slumpligt vald graf G har en Hamilton cykel/circuit eller inte. Mer precis, det är känd att vara ett s.k. NPkomplett problem att skriva en algoritm som tar en godtycklig graf och avgör om grafen har en Hamilton cykel/circuit eller inte. Vi återkommer med en diskussion om komplexitet av alkgoritmer.

Därför är det allt viktigare att kunna hitta tillräckliga villkor för att en graf har en Hamilton cykel som gäller för ‘ganska många’ grafer. Den enklaste satsen av denna typ som jag känner till är

Sats 1.14 Låt G vara en IRE-graf med n noder. Om deg(v) ≥ n/2 för varje v ∈ V (G), då har G en Hamilton cykel.

Bevis (following [1]) : The proof is by contradiction. Suppose the theorem is not true and let G be a graph satisfying the hypothesis for some n but having no Hamilton cycles. We may take G to be such a counterexample with the maximum number of edges ; then the addition of any edge to G must create a Hamilton cycle.

So let y and z be non-adjacent vertices. Adding the edge {y, z} creates a Hamilton cycle. Any such cycle must of course include the newly-added edge and so can be written as

y = x_{1} → x_{2} → ⋯ → x_{n} = z → y,

i.e.: the edge {y, z} is put at the end of the cycle, and x_{1}, ..., x_{n} are the n different nodes of G. Now the sets

S = {i : y is adjacent to x_{i+1} in G},
T = {i : z is adjacent to x_{i} in G}

each have size at least n/2, by hypothesis. But each is a subset of {1, ..., n − 1}. By the pigeonhole principle, the two sets must intersect. Let i_{0} be an element of both. Then the cycle

y = x_{1} → x_{2} → ⋯ → x_{i_{0}} → z = x_{n} → x_{n−1} → ⋯ → x_{i_{0}+1} → x_{1} = y, is a Hamilton cycle in G. This is a contradiction, which completes the proof.

Exempel 1.15 : Den s.k. Petersen grafen (se övning 8.2.2 i boken) är en IRE-graf med 10 noder, som har enkla cyklar av längd 5,6,8,9 (kolla !) men ingen Hamilton cykel (= enkel cykel av längd 10).

Exempel 1.16 : Portkod problemet. Notera att det är inte så lätt att bevisa att R-grafen för detta problem faktiskt har en Hamilton cicruit. Grafen är faktiskt ett exempel av en s.k. de Bruijn graf ([1], kap. 8).

Definition 1.17 : Låt G vara en IR-graf och k > 0 ett heltal. En kfärgning av G är en färgning av dess noder med k st. olika färger så att två sammansatta noder aldrig får samma färg.

Det kromatiska talet av en IR-graf G är det minsta positiva talet k så att grafen har en k-färgning. Det betecknas χ(G).

Det är känd att vara ett NP-komplett problem att skriva ett program som beräknar χ(G) för en godtycklig IR-graf G. Åandra sidan den s.k. giriga algoritmen ofta ger en färgning med ‘tillräckligt få’ färger för praktiska tillämpningar (i praktiska färningsproblem - se nedan - är det sellan att man behöver en optimal färgning). En ‘nedre gräns’ för algoritmens effektivitet ges av

Sats 1.18 em Låt G vara en IR-graf där varje nod har grad högst k, för något fixt heltal k. Då ger den giriga algoitmen, för varje ordning av noderna, en färgning av G som använder högst k + 1 färger.

Bevis : Sats 8.7.1(i) i boken.

Studiet av graf-färgning har sitt ursprung i schema-uppläggnings problem.

Exempel 1.19 : We want to assign dates for exams in all math courses during lp-4 in such a way that two exams are not scheduled on the sae day whenever there is a student taking both corresponding courses. Obviously, we’d like to do this with as few exam dates as possible.

We translate this into a graph coloring problem as follows : take a IREgraph G whose nodes are the various math courses, and join two nodes whenever there is at least one student taking both of the corresponding courses. Then to find an admissable exam schedule which uses k different dates is the same thing as finding a k-coloring of G. Since it’s probably not important to find a schedule which is absolutely optimal (i.e.: to find χ(G)), we’d start by coloring G using the greedy algorithm and see if we can live with the resulting schedule !

Definition 1.20 : En IR-graf G med χ(G) = 2 kallas för en bipartite graf.

Anmärkning 1.21 : Följande är en av de mest berömde satserna i grafteori :

Four color theorem Låt G vara en plan IR-graf, dvs en graf som kan ritas i planet på ett sådant sätt att nget par av kanter korser varandra. Då är χ(G) ≤ 4.

References

[1] J.H. van Lint and R.M. Wilson, A course in combinatorics, Cambridge University Press, 1992.