Trees

• Connected
• Acyclic
• Exactly 1 Path between any two nodes

$$ \text{edges}\geq\text{nodes}-1\\\text{if edges}=\text{nodes}-1\rightarrow \text{graph is a tree } $$

Minimum Spanning Tree

• Spanning Tree (Tree that reaches all vertexes) of $G$ where the total weight is minimal

Kruskals Algorithm

• Start with weighted graph that has $n$ connected components

1. Take smallest edge that reduces components to $n-1$
2. Repeat 1. untill 1 component left / joined all components

Prims Algorithm

• Start from random vertex in a weighted graph

1. Select outgoing edge with smallest weight
2. Repeat 1.

Prims

• Only connected graphs
• Faster on a dense group

Kruskals

• Faster on sparse graphs
• Works on disconnected graphs

Metrics for Complex Networks