# D1 Decision Maths OCR - Everything you need sortened - with pictures to demonstrate

Teacher recommended

- Created by: Alex
- Created on: 25-05-11 20:18

**Simple Graph**: Graph with no loops and at most one edge connecting any pair of verticies

**Connected Graph:** If allthe verticies are connected

**Tree**: A connected graph with no cycles

**Complete Graph:** One where every pair of verticies is connected by a single edge

**Planar Graph:** One that can me drawn so that no arcs cross

**Hamiltonian cycle:** One that visits every arc once and returns to the starting arc

**Eularian Trail/Cycle:** Covers every edge of the graph once and finished at the start vertex - This graph is Eularian

**Semi-Eularian:** If it is possible to cover every arc on the graph and finish at another vertex

**Tracersable:** If the graphs can be drawn without taking the pen of the paper or repeating any edges

**Direct Graph/Diegraph:** Graph with at least one arc with a direction associated with it - opposite in undirected

**Biparte Graph:** A graph whos verticies can be divided into two coloums such that every arc in U connects to an arc in V

**Algorithms & such**

**Bubble Sort**:

Compares numbers in a series of passes and swaps if necessary

**Shuttle Sort**

Compares the first two then adds third number and compares, then add the 4th and compares etc

**First-Fit Algorithm**

Taking items in the order listed and placing them in the first space available

**First-Fit decreasing Algorithm**

Rearrange items into descending order of size

Place each item in turn into the first bin space available

**Kruskals Algorithm:**

1. List edges in order with smallest first -(Put it in a table)

2. Choose are of least weight

3. Choose are of least weight (not already chosen one) which doesn't form a cycle from already chosen arcs

4. Repeat 3 untill all verticies have been included.

**Prim's Algorithm**

1. Choose start vertex

2. Connect start vertex to nearest vertex by adding shortest edge

3. From and vertex on tree so far add shortest edge that connects a new vertex

4. Repeat 3 untill all veritcies included

**Prim's Algorithm - From a matrix**1. Choose a start Vertex & label the corresponding column aith 1. and delete the row

2. Look in all coloumns numbered so far & circle the smallest undeleted entry and read off vertex for this row

3. Label column corresponding to this vertex with the next…

## Comments