disM/LaTeX/Grafteori.md

• Grafer
  • Def: en graf G är ett ordnat par av mängder: G = (V,E) där V\neq\emptyset, E=\{\{u,v\}:u,v\in V\}
    • Ex: V=\{1,2,3,4,5\}, E=\{\{1,2\},\{1,3\},\{1,4\},\{4,5\}\}
  • V: Mängd av noder/hörn. E: mängd av kanter
  • Notation: u,v,...\in V, e,\{u,v\}...\in E
  • Grannar: Två noder u och v i V är grannar om \{u,v\}\in{E}
  • Riktad/oriktad graf: Kanterna är riktade/oriktade
  • Multigraf: Om två hörn hat flera kanter (E är multiset)
  • Ögla: Ev\in{V}:\{v,v\}\in{E}
  • Enkel graf: Ögelfri och med högst en kant mellan varje par
  • Viktad graf: Kanter har längd
• Gradtal
  • Def: Gradtal dv av ett hörn v är antal grannar till v
  • Theorem: Låt G=(V,E) vara en graf. Då är$\sum_{v\in{V}}dv=2\mid{E}\mid$
  • Ex. Enekel ögelfri graf G vars alla noder har samma antal gradtal har 15 kanter. Hur många noder kan G ha? \begin{align*}\text{låt}\mid{A}\mid=n\\\text{enligth satsen}\\\sum_{v\in{V}}dv=2\mid{E}\mid = 2*15=30\\\Leftrightarrow{nd}=30\end{align*}
  • Theorem: I varje (ändlig) graf måste antalet hörn med udda gradtal vara jämnt
• Kompletta grafer
  • Def: Enkomplett graf är en graf där varje par av hörn har en kant.
  • Notation: Kn är den kompletta grafen på n hörn.
  • Varje hörn har gradtal n-1.
  • Antal kanter: \left|{E_{K_n}}\right|\:=\binom{n}{2}=\frac{n(n-1)}{2}
  • Ex: Beräkna \left|E_{K_15}\right| = \left|{E_{K_15}}\right|\:=\frac{15\times14}{2}=105
• Isomorfa grafer
  • Def: En isomorfism mellan grafer G_1 = (V_1,E_1) och G_2=(V_2,E_2) är en function f: V_1\longrightarrow{V_2} så att (u,v)\in{E_1}\Leftrightarrow(f(u),f(v))\in{E_2}
  • Grafer G_1 och G_2 är isomorfa om det fins en isomorfism f mellan G_1 och G_2
  • f är en isomorfism G_1\cong{G_2}
  • Ex

Kanter G_1	Kanter G_2
\{1,2\}	\{f(1),f(2)\}=\{b,f\}
\{2,3\}	\{f(2),f(3)\}=\{f,c\}
\{2,4\}	\{f(2),f(4)\}=\{f,a\}
\{4,5\}	\{f(4),f(5)\}=\{a,e\}
\{5,6\}	\{f(5),f(6)\}=\{e,d\}

• Väger i grafer
  • Väg: En följd av hörn längst kanterna. Längd är antal kanter i vägen
  • Notation: v_0\to{v_2}\to\dots{v_{n-1}}\to{v_n}. (längd n)
  • Sluten väg: v_0=v_n. Öppen väg: v_0\neq{v_n}
  • Enkel väg/stig: Alla hörn är olika, v_i\neq{v_j}, 1\leq{i},j\leq{n}
  • Avstånd d(v_i,v_j) är längd av korstaste stigen från v_i till v_j.
  • Cykel (längd n): Sluten väg v_0\to{v_1}\to\dots{v_{n-1}}\to{v_0}
• Eulerväg
  • Def: En Eulerväg i en graf är en väg som passerar varje kant i grafen exakt en gång
  • Def: En Eulercykle (Eulerkrets/Eulertour/Eulrtslinga) är en sluten Eulerväg
  • Def: En graf som innerhåller en Eulercykle kallas för en Eulergraf
  • Theorem (Euler, 1736): En sammanhängade graf G med minst en kant har en eulerkrets om och endast om alla dessa hörn har jämnt gradtal. G har en öppen Eulerväg om och endast om precis två hörn har udda gradtal
• Hamiltongraf
  • Def: En Hamiltoncykel i en graf med minst tre hörn en cykel som passerar varje hörn exakt en gång
  • Def: En graf som innehåller en Hamiltoncykel kallas för en Hamiltongraf
  • Def: En Hamiltonväg i en graf är en enkel väg som innerhåller varje hörn
• Träd
  • Def: (träd): En sammanhängande graf som saknar cykler
  • Therem Låt G(V,E) vara med minst två hörn. Då är följande påståenden ekvivalenta:
    • Grafen G är ett träd.
    • Det finns en unik enkel väg mellan varje par av noder u,v\in{V(G)}.
    • Grafen G saknar cykler, samt om man lägger en ny kant uppstår precis en cykel.
    • Grafen G är sammanhängande, samt om man tar bort en godtycklig kant, då fås en osammanhängande graf.
    • Grafen G är sammanhängande, samt $\mid{V}\mid-\mid{E}\mid=1$
    • Grafen G saknar cykler, samt $\mid{V}\mid-\mid{E}\mid=1$
• Planära grafer
  • Def: En planär grad är en graf som kan ritas på planet så att kanterna inte slär varandra utom i noderna. En sådan ritning är en Plan inbäddning av grafen
  • Ex: K_3, K_{3,2}, K_4
    • Varje plan graf delar planet i regioner(inklusive det oändliga yttre regioner) begränsar regionen.
    • Gradtalet för en region är antalet kanter som begränsar regionen.
    • För enkel, planär graf G = (V,E) med minst tre hörn \mid{E}\mid\leq{3}\mid{V}\mid-6.
    • För enkel, planär, sammanhängande, bipartit graf G=(V,E) med mist tre hörn, \mid{E}\mid\leq2\mid{V}\mid-4.
• Eulers sats om planära grafer
  • Theorem: Låt G=(V,E) vara en sammanhängande, plan graf med mängd av regioner R=\{r_1,r_2,\dots,r_n\}. Då gäller följande för gradtalen d_r av regioner: $\sum_{r\in{R}}d_r=2\mid{E}\mid$
  • Theorem (Eulers formel för planära grafer): Låt G=(V,E) vara en sammanhängande, plan graf med mängd av regioner R=\{r_1,r_2,\dots,r_n\}. Då gäller följande $\mid{V}\mid-\mid{E}\mid+\mid{R}\mid=2$
  • Ex: En plan sommanhängende graf G delar planet i 6 regioner. Dess 6 hörn har antingen grad 3 eller 4. Hur många av dessa är av grad 3, och hur många av grad 4