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

?
  • 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
(http://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/600px-Simple-bipartite-graph.svg.png)

Algorithms & such

Bubble Sort:
Compares numbers in a series of passes and swaps if necessary
(http://2.bp.blogspot.com/-_75GwaiTNsQ/TbVv47YXuVI/AAAAAAAAACs/WDGoiVjXLDw/s1600/bubble-sort-2.png)

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
(http://img.tebyan.net/library/english/10128_fig593_01.jpg)

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

Renita

Report

I'm doing AQA so there's some stuff not here but this is actually really good! Thanks x

Beth KT

Report

Thanks, very helpful. Th only thing is please spell vertices right so when people try and listen to it, the voice does sound like gobbledy gook but THANKYOU anyway because i have my exam tomorrow and this saved me so much time :)

Hannah

Report

this was AMMAAZZINNNGGGG aha thanks so much, seems like a lot of time went into this!

daviesg

Report

A really well presented summary (with pictures) of the D1 content. suitable for all boards.

ElizabethH

Report

Very good except for the frequent spelling mistakes.