Further Maths - Properties of graphs

Simple-connected graph

A graph that is both simple and connected.

Tree

A simple-connected graph with the minimum possible edges.

Traversable graph

A graph that can be drawn as a trail without going over the same edge twice.

Eularian graph

A connected graph with no vertices of an odd degree.

Semi-Eularian graph

A connected graph that has exactly 2 vertices of odd degree.

Hamiltonian graph

A graph that contains a cycle that passes through every vertex once apart from starting and finishing in the same vertex.

Kruskal's algorithm Step 1

Select the least weighted edge that will not form a cycle

Kruskal's algorithm Step 2

If all nodes are connected stop. Else go back to step 1.

Prim's algorithm Step 1

Begin by choosing any edge with the smallest weight, putting it into the spanning tree.

Prim's algorithm Step 2

Successively add to the tree edges of minimum weight that are connected to a vertex already in the tree.

Prim's algorithm Step 3

Stop once n - 1 edges have been added.

Trail

Route around the graph where no sides are repeated.

Walk

A route around the graph

Cycle

A trail which starts and ends in the same place.

Connected

There is a trail from any node to any other node.

Loop

An edge that is only connected to one point.

Simple graph

A graph with no multiple edges or roots.

Bipartite

Source

S - Where everything flows from

Sink

T - where everything flows to

Feasible flow

A combination of possible routes and flows through a network.

Minimum cut and maximum flow

Minimum cut is always the same as the maximum flow