2024-09-30

Grafteori

Maximalt sammanhängande delgraf

En sammanhängande delgraf $\tilde{G} = (\tilde{V}, \tilde{E})$ till $G = (V, E)$ , så den att för alla $\hat{V} \subseteq V : \tilde{V} \subseteq \hat{V} \subseteq V$ gäller att den inducerade delgrafen för $\hat{V}$ ej är sammanhängande.

"Kan jag lägga till en nod i den inducerade delgrafen utan att den slutar vara sammanhängande? Om jag inte kan det är den maximalt sammanhängande."

Gradtal

För en nod $v \in V$ är $v$ 's gradtal:

$d_{v} = antal kanter i G vars ena ände är i v$
$= antal noder i G länkade till v via en kant$
$= | {u \in V : {u, v} \in E} |$

Fullständig

En graf $G$ är fullständig om det finns en kant mellan varje par av noder.

Notation: $K_{n} : fullständig graf på n noder$

Bipartit

$G = (V, E)$ kallas bipartit om det finns delmängder $A \subseteq V, B \subseteq V$ så att $A \cup B = V, A \cap B = \emptyset$ och så att $\forall x, y \in E : (x \in A \land y \in B) \lor (x \in B \land y \in A)$

Tänk

Om en graf är bipartit kan alla noder färgläggas med två färger så att alla kanter går från en färg till en annan.

Fullständigt bipartit

En #bipartit graf $G = (V, E)$ är fullständigt bipartit om $\forall a \in A, \forall b \in B : {a, b} \in E$ .

Notation: $K_{m, n} :$ fullständigt bipartit graf med $| A | = m, | B | = n, n \geq m$

Träd

En graf $G = (V, E)$ är kallas ett träd om $G$ är sammanhängande och inte innehåller cykler.

Sats

$G = (V, E)$ är ett träd $⟺$ varje par $(v, w) \in V$ finns en unik enkel väg mellan $v, w$ .

Om det finns två vägar, då kan vi bilda en cykel.

Sats

$G = (V, E)$ är ett träd $⟺$ $G$ är sammanhängande och $| E | = | V | - 1$