1. Grafrepresentasjon: ⟨V,E⟩ og nabomatrise

En enkel uretttet graf er et ordnet par \(G=\langle V,E\rangle\) der \(V\) er nodemengden og \(E\) er en mengde av uordnede par \(\{u,v\}\) (kanter), uten løkker og uten multiple kanter. Nabomatrisen \(A\) har \(A_{ij}=1\) hvis \(\{i,j\}\in E\), ellers \(0\).

Nabomatrise — egenskaper (enkel uretttet graf):

• Symmetrisk: \(A_{ij}=A_{ji}\)
• Null på diagonalen (ingen løkker)
• Radsum \(i\) = \(\deg(i)\)
• \((A^k)_{ij}\) = antall vandringer av lengde \(k\) fra \(i\) til \(j\)
• Rettet graf: \(A_{ij}=1\) betyr kant \(\langle i,j\rangle\); matrisen er generelt usymmetrisk

Maksimalt antall kanter i en enkel graf på \(n\) noder er \(\binom{n}{2}=\frac{n(n-1)}{2}\) (gir \(K_n\)).

Eksempel 1: Gitt \(A=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}\). Beskriv grafen og finn antall kanter.

Symmetrisk, 0 på diagonal: gyldig enkel uretttet graf.

Kanter: \(\{1,2\},\{1,3\},\{2,3\}\) — alle par forbundet.

Sum av alle elementer \(=6\); hver kant telles to ganger.

Antall kanter \(=6/2=3\). Dette er \(K_3\) (trekanten), hver node har grad 2.

2. Grad, stier og sammenheng

Graden \(\deg(v)\) er antall kanter ved \(v\). En vandring tillater gjentakelser; en tur har ingen gjentatte kanter; en sti har ingen gjentatte noder. Grafen er sammenhengende hvis det finnes en sti mellom hvert par av noder.

Handshaking-lemmaet: \(\displaystyle\sum_{v\in V}\deg(v)=2|E|\).

Konsekvens: Antall noder med oddetallsgrad er alltid et partall.

En sammenhengende graf på \(n\) noder har minst \(n-1\) kanter (tre).

Eksempel 2: En enkel graf har 6 noder, hver av grad 3. Hvor mange kanter?

Gradsum \(=6\cdot 3=18\).

Handshaking: \(2|E|=18\).

\(|E|=18/2=9\). En 3-regulær graf på 6 noder (f.eks. \(K_{3,3}\)) har 9 kanter.

3. Euler-vei og Euler-krets

En Euler-krets bruker hver KANT nøyaktig én gang og er lukket; en Euler-vei er den åpne varianten. Euler ga et fullstendig (nødvendig og tilstrekkelig) gradkriterium.

Eulers gradkriterium (sammenhengende graf, ≥1 kant):

• Euler-krets ⟺ ALLE noder har partallsgrad.
• Euler-vei (åpen) ⟺ NØYAKTIG to noder har oddetallsgrad (start/slutt).
• Flere enn to oddenoder ⟹ verken vei eller krets.

Eksempel 3: Königsbergs broer — multigraf med gradsekvens \((3,3,3,5)\). Finnes en Euler-vei?

Tell oddenoder: alle fire grader \(3,3,3,5\) er oddetall.

Euler-vei krever nøyaktig to oddenoder; her er det fire.

Konklusjon: ingen Euler-vei og ingen Euler-krets. (Eulers svar, 1736.)

4. Hamilton-vei og Hamilton-sykel

En Hamilton-sykel besøker hver NODE nøyaktig én gang og returnerer til start; en Hamilton-vei er den åpne varianten. I motsetning til Euler finnes INTET enkelt gradkriterium — å avgjøre Hamilton-sykel er NP-komplett. Vi har kun tilstrekkelige betingelser.

Tilstrekkelige betingelser (enkel graf, \(n\ge 3\)):

• Dirac: hvis \(\deg(v)\ge n/2\) for alle \(v\) ⟹ Hamilton-sykel.
• Ore: hvis \(\deg(u)+\deg(v)\ge n\) for alle ikke-naboer \(u,v\) ⟹ Hamilton-sykel.
• Nødvendig: ingen node av grad 1; \(K_{m,n}\) har Hamilton-sykel kun når \(m=n\).

Eksempel 4: Har \(K_{2,3}\) en Hamilton-sykel?

Bipartite: deler av størrelse 2 og 3.

En sykel i en bipartite graf veksler mellom delene, så lik størrelse kreves.

\(2\ne 3\) ⟹ ingen Hamilton-sykel finnes.

5. Isomorfi og automorfier

To grafer er isomorfe (\(G_1\cong G_2\)) hvis det finnes en bijeksjon \(f:V_1\to V_2\) med \(\{u,v\}\in E_1\iff\{f(u),f(v)\}\in E_2\). En automorfi er en isomorfi fra \(G\) til seg selv; mengden av disse er automorfigruppen \(\operatorname{Aut}(G)\).

Invarianter (bevares under isomorfi): antall noder, antall kanter, gradsekvens, antall komponenter, antall sykler av gitt lengde, bipartithet.

Bevisstrategi: Ulik invariant ⟹ IKKE isomorfe. For å BEVISE isomorfi: oppgi konkret bijeksjon og verifiser alle kanter. Lik gradsekvens er nødvendig, men IKKE tilstrekkelig.

Eksempel 5: Finn alle automorfier til stigrafen \(P_3\): \(a-b-c\).

Grader: \(\deg(b)=2\), \(\deg(a)=\deg(c)=1\).

Automorfi bevarer grad ⟹ \(b\) må fikseres.

Endene: enten begge fikseres (identitet) eller byttes \(a\leftrightarrow c\).

Begge bevarer kantene \(\{a,b\},\{b,c\}\). Altså \(|\operatorname{Aut}(P_3)|=2\).

Studieguide: Grafteori

Studieguide: Grafteori