Graph Theory

tree

A graph is a set of nodes (often denoted E) and a set of links (connecting them). The points are often also called vertices and nodes, and the lines edges.

Examples

Roads and Maps
Social Networks
Internet
Flowcharts

Vocabulary

Adjacent edges are connected by a vertex.
A graph is empty if the set of lines is empty.
A graph is complete if all nodes are neighbors.
A pseudograph has a point that links to itself.
The complementary graph of another graph G has identical nodes, but only edges G has not.
The set of links in a directional graph contains tuples instead of sets.
Graphs $G$ and $H$ are isomorphic ($G \cong H$) if their sets of nodes and links are identical

Node degree (grad)

The amount of connections extending from a node is called it’s degree. Nodes with degree 0 are called isolated nodes.

Theorems

$\sumdeg(v) = 2 \cdot |E|$
The number of nodes with odd degrees is even for any graph

Adjacency List is a list is a list where for every node you keep track of the adjacent nodes. This can also be put into matrices.

Terms

A traversal is a sequence of nodes A path is a traversal without repeating nodes A closed traversal is a traversal where first and last nodes are identical A circuit is a closed traversal without repeating edges A cycle is a closed traversal without repeating nodes A component graph is a graph where all nodes can be reached from any starting point with $n \in \mathbb{N}$ steps A tree is a acyclical component graph (often has one designated root node) A hamilton path is a path that visits all nodes once in a graph An euler path is a path that visits all edges once in a graph

Requirements for Euler Paths

Only odd degree on beginning and end (unless you begin and end in same node). The rest needs to be even for this to be possible.