LEKTION 03-26

Notera att om vi tar en graf G = (V, E) antag vi bara att ∅ ≠ V. Så det är möjligt att få ett antal isolerade noder som en graf. När vi vill inte ha ett antal isolerade noder som en graf då säger vi att ∅ ≠ E.

Låt G = (V, E) vara en enkel graf med V = {v_{1}, ..., v_{n}} och E = {k_{1}, ..., k_{e}}. Man kan bilda två matriser fån grafen G.

• En n × e matrisen A_{G} = (a_{ij}) definerat som:

a_{ij} = \{ \begin{matrix}1 & om k_{i} är incident till v_{j} \\ 0 & annars \end{matrix}

Denna matrisen kallas den incidensmatrisen.

• En n × n matris, den grannmatrisen, X_{G} = (x_{ij}) där

x_{ij} = \{ \begin{matrix}1 & om det finns en kant mellan noder v_{i}, v_{j} \\ 0 & annars \end{matrix}

Exempel. Betrakta grafen G: [figure: v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; k_{1}; k_{2}; k_{3}; k_{5}; k_{4}; k_{6}]

A_{G} = ( \begin{matrix}1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) X_{G} = ( \begin{matrix}0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{matrix} )

Notera:

• Antalet ettor i en rad av incidensmatricen är lika med graden av motsvarande nod.(Bevisa det)

• Varje kolumn i incidensmatrisen innehåller precis två ettor. (Bevisa det)

• En gannmatris är alltid symmetrisk.

• Permutation av rader och kolumner i gannmatrisen innebär bara omnumrering av noderna.

• Permutation av rader och kolumner i incidenstrisen innebär bara omnumrering av noderna och kanter.

Betrakta grafer G: [figure] G′: [figure]

De ser olika ut med kan ritas på samma sätt. Vi säger att de är isomorfa grafer.

Definition 0.1. Två enkla grafer G, G′ är isomorfa, G ≅ G′, om och endast om matrisen A_{G} kan fås från A_{G′} genom att permutera raderna och kolumner.

Det betyder att G ≅ G′ om och endast om A_{G} = A_{G′} efter , eventuellt, vi ger en annan ordning till noder och kanter i grafen G′.

Man kan definera en isomorfi mellan grafer G = (V, E) och G′ = (V′, E′), f : G → G′. Det består av en bijektiv funktion f : V → V′ så att:

för alla a, b ∈ V ab ∈ E ↔ f(a)f(b) ∈ E′

Notera:

• Två isomorfa grafer har samma antalet komponenter.

• Två isomorfa grafer har samma antalet kanter och samma antalet noder.

• Motsvarande noder i isomorfa grafer har samma graden!

• Isomorfa grafer har samma antalet cykler.

Exempel. Rita alla icke isomorfa grafer med 4 noder som finns.

Det finns 11 alternativ.

[figure]

[figure]

[figure]

Definition 0.2. • En hamiltonstig är en stig some besöker \underline{varje nod} precis \underline{en gång}. • En hamiltonscykel är en cykel som besöker \underline{varje nod} en gång.

• En eulersväg är en väg som passerar \underline{varje kant} precis \underline{en gång}.

• En eulerkrets är en sluten väg (en väg som börjar och sultar påsamma nod) som passerar \underline{varje kant} precis \underline{en gång}.

• En graf kallas eulersk om den har en Eulerkrets och kallas hamiltonsk om den kar en hamiltonscykel.

Att avgöra om en graf är hamiltonsk är jättesvårt.

Exempel Betrakta grafen: [figure]

Den är en emiltonsgraf, men det finns ingen emiltonscykel. För att bestämma det man måste försöka att bilda en emiltoncykel från varje nod och visa att det är omöjligt att göra det.

Det är mycket lättare att avgöra om en graf är eulersk.

STAS 1. En graf G utan isolerade noder har en eulerkrets om och endast om är sammanhängande och har varje nod har jämn grad. Bevis. Antag att G har en eulerkrets, då är G sammarhängande. Om en graf består av två komponenter är det omöjligt att bilda en sluten väg som passerar varje kant. Låt γ = v_{0}v_{1}...v_{0} vara en eulerstig i G. När vi går från a_{0} använder varje kant, till v_{i} och från v_{i}. Det ger bidraget 2 varje gången till deg(v_{i}).

Antag nu att G är sammanhängande och har varje nod har jämn grad. börja med en nod s. Säkert kan man går vidare och bilda en stig γ som slutar i s, eftersom s har jämn grad. Om gamma innehåller alla kanter är vi klara. Antag att σ inte innehåller alla kanter och bilda delgrafen H \ γ genom att ta borta alla kanter i γ. Varje nod i H har jämn grad och H är någon icke-isolerade nod v, eftersom G är sammanhängande. Så kan man konstruera en stig α från v. Om stigen γ ∪ α inte innehåller alla kanter i G fortsätter man med grafen G \ γ ∪ α

STAS 2 En graf utan isolerade noder har en eulerväg om och endast om är sammanhängande och har högst två noder av udda grader. Bevis. Antag G har en eulerväg, då är G sammanhängande och man kan visa at den har högst två noder av udda grader på samma sätt än i Sats 1.

Antag nu att G är sammanhängande och har högst två noder av udda grader. Om alla noder har jämn grad då finns det en eulerstig och därför en eulerväg.

Det kan inte vara att bara en nod har odd grad eftersom då summan av grader måste vara jämn. Så vi kan antag att det finns exact två] noder a, b med odd grad. Låt G′ vara delgrafen genom att förbinda a och b med en ny kan e. G′ är sammanhängande och har varje nod har jämn grad. Enligt Sats 1 G′ har en eulerstig γ. Det följer att γ − e är en eulerväg i G.

Exempel.

• Grafen i förre exempel har ingen eulrväg eller eulerstig, eftersom det finns 6 stycken noder med grad 3.

• K_{n} är eulersk bara när n är udd.

• K_{n} har en Eulerväg bara bara när n är udd eller n = 2.

Övning

(1) Låt G = (V, E) vara en en enkel graf. Bestäm |V | om G har 15 kanter och alla noder har samma grad.

(2) Rita grafen med incidensmatris:

A_{G} = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & & 0 & 0 & 1 & 1 \end{matrix} )

Är grafen eulersk? Har grafen en eulerväg. Om svaret är jag hitta den.