72 lines
5.1 KiB
Markdown
72 lines
5.1 KiB
Markdown
- 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$
|
|
- |