2024-10-07

Grafteori

Riktad graf

En riktad graf är en graf $G = (V, E)$ där:

$V : mängd av noder$
$E \subseteq V \times V : mängden av riktade kanter$

En kant $(v, w) \in E$ tolkas som en riktad kant från $v$ (startnod) till $w$ (slutnod).

Exempel

$V = {1, 2, 3}$
$E = {(1, 2), (2, 3), (3, 2)}$

-d
1,2,3
(1,2),(2,3),(3,2)

Note

Det kan inte finnas riktade och oriktade kanter i samma graf. En oriktad graf kan representeras som en riktad graf där alla kanter är riktade åt båda håll. D.v.s:

\exists (c, d) \in E : (c, d) = (b, a) \forall (a, b) \in E

Riktad väg

En väg $v_{0}, v_{1}, v_{2}, \dots, v_{n} \in V$ (från $v_{0}$ till $v_{n}$ ) där $(v_{0}, v_{1}), \dots, (v_{n - 1}, v_{n}) \in E$ .

Riktad cykel

En #riktad väg med $v_{0} = v_{n}$ utan upprepade kanter.

Starkt sammanhängande graf

Se även: 2024-09-26#Sammanhängande graf

En #riktad graf $G = (V, E)$ är starkt sammanhängande om det finns en #riktad väg mellan alla möjliga par av noder $u, v \in V$ .

Eulerväg

Låt $G = (V, E)$ vara en (oriktad) graf.
En Eulerväg i $G$ är en väg som innehåller varje kant exakt en gång.

Bakgrund — #Köningsbergs sju broar

Euler på 1700-talet frågade: Kan man passera samtliga broar i Köningsberg exakt en gång och avsluta där man börjar?

Eulercyklel

En #eulerväg där $v_{0} = v_{n}$ och utan upprepade kanter.

Alternativ definition

En Eulercykel är en cykel som innehåller varje kant i $G$ exakt en gång.

Hitta Eulercykler

Sats 7.11

En sammanhängande graf $G$ innehåller en Eulercykel om och endast om alla gradtal i $G$ är jämna.

Sats 7.12

Låt $u, v \in V, u \neq v$ i en sammanhängande graf $G = (V, E)$ . $G$ innehåller minst en Eulerväg från $u$ till $v$ om och endast om $d_{u}$ och $d_{v}$ är udda och alla andra noder $w \in V$ har $d_{w}$ jämnt.

Givet att det finns en Eulercykel i $G$ :

Flera metoder:

Hitta kortare cykler och "bygg på dem"

Givet grafen G:

1,2,3,4,5,6
(1,2),(1,3),(1,4),(1,6)
(2,3)
(3,6),(3,4)
(4,5),(4,6)
(5,6)

Börja med triangeln 1-2-3-1:

1,2,3,_,_,_
1-2-3-1

Ta bort kanterna från $G$ :

1,_,3,4,5,6
(1,4),(1,6)
(3,6),(3,4)
(4,5),(4,6)
(5,6)

Välj en till cykel, t.ex. 1-4-6-1:

1,_,_,4,_,6
1-4-6-1

Ta bort kanterna:

_,_,3,4,5,6
(3,6),(3,4)
(4,5)
(5,6)

Även detta är en cykel: T.ex. 4-3-6-5-4.

De sammansatta cyklerna från steg 1-3 blir en Eulercykel:

1-2-3-1
1-4-6-1
4-3-6-5-4

TODO: Hur?

Note

Algoritmen är idén till beviset av 7.11

Multigraf

En multigraf är en oriktad graf som tillåter flera oriktade kanter mellan två noder.

Relationsgrafer

En relation kan beskrivas med en riktad graf:

Låt $A$ vara en mängd och $R$ en relation på $A$ . Det implicerar $R \subseteq A \times A$

Låt $G_{R} = (A, R)$ vara den riktade grafen med nodmängd $A$ och kantmängd $R$ .

$G_{R}$ kallas relationsgrafen till $R$ .

Note

Ekvivalensklassser motsvarar sammanhängande komponenter/delgrafer i relationsgrafen.

Matriser

Vad är en matris?

Från Matrismatte för labb 2

En matris är en tabell av element som har ett antal rader och kolumner.

En matris $A = [\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix}]$ har 2 rader och 3 kolumner. Man kan även säga att $A$ är av typen $2 \times 3$ eller att $A$ har dimensionen $(2, 3)$ .

Ett element på rad $i$ och kolumn $j$ i matrisen $A$ betecknas $A_{i j}$
I matrisen ovan är t.ex. $A_{21} = 4$

Generell formulering

$A$ är en matris av typen $m \times n$ :

A = [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & a_{m n} \end{matrix}]

Ett element i $A$ på raden $i$ och kolonnen $j$ noteras $A_{i j}$ .

Hela raden $i$ betecknas $A_{i .}$ och hela kolonnen $j$ betecknas $A_{. j}$

Specialfall

En kolonnvektor är en matris av typen $m \times 1$ , d.v.s. bara en kolonn.
En radvektor är en matris av typen $1 \times n$ , d.v.s. bara en rad.

Note

I radvektorer och kolonnvektorer noteras $i$ :te elementet, d.v.s. element $A_{1 i}$ i en radvektor och $A_{i 1}$ i en kolonnvektor, som $A_{i}$

En matris av typen $m \times n$ där $m = n$ kallas en kvadratisk matris.

Räkneregler

Addition

Givet att $A, B$ är av typen $m \times n$ gäller:

A + B = [\begin{matrix} a_{11} + b_{11} & a_{12} + b_{12} & \dots & a_{1 n} + b_{1 n} \\ a_{21} + b_{21} & a_{22} + b_{22} & \dots & a_{2 n} + b_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{m 1} + b_{m 1} & a_{m 2} + b_{m 2} & \dots & a_{m n} + b_{m n} \end{matrix}]

eller $(A + B)_{i j} = A_{i j} + B_{i j}$

Note

Anledningen till att matriserna måste vara av samma typ och inte kan "expanderas" med $0$ är att matrisernas egenskaper ändras för mycket om man ändrar matrisens typ.

Subtraktion

$A, B$ är $m \times n$ -matriser.

$(A - B)_{i j} = A_{i j} - B_{i j}$

Multiplikation

Överkurs — Hadamard-produkten

Det kanske känns intuitivt att multiplicera matriser med samma princip som addition och subtraktion ovan, d.v.s. varje element i matris $A$ multipliceras med elementet på samma position i matris $B$ . Det kallas Hadamard-produkten och noteras: $A ⊙ B$ . Denna definitionen av multiplikation används dock sällan.

Skalärprodukten

Givet en radvektor $\underset{―}{a} = (a_{1}, \dots, a_{n})$ och en kolonnvektor $\underset{―}{b} = (\begin{array}{cc} b_{1} \\ ⋮ \\ b n \end{array})$ . Definieras skalärprodukten som:

\underset{―}{a} \cdot \underset{―}{b} = \sum_{i = 1}^{n} a_{i} \cdot b_{i}

Definition

Matrismultiplikation definieras som:

(A \cdot B)_{i j} = A_{i .} \cdot B_{. j}

Där $A_{i .} \cdot B_{. j}$ är #skalärprodukten mellan $i$ :te raden i $A$ och $j$ :te kolonnen i $B$ .

Utvecklat kan detta även skrivas som:

(A \cdot B)_{i j} = \sum_{k = 1}^{n} A_{i k} \cdot B_{k j}

Där $n$ är storleken av den gemensamma dimensionen i $A$ och $B$ . Om $A$ inte har lika många kolonner som $B$ har rader så är produkten odefinierad.