Decision Maths Key Words 2.5 / 5 based on 2 ratings ? MathematicsNetworks, algorithms and problem solvingA2/A-levelEdexcel Created by: bethany cracknellCreated on: 02-05-13 09:56 Algorithm precise instructions that can solve a problem 1 of 41 Eulerian Cycle cycle passing through every edge once, returns to start vertex 2 of 41 Semi-Eulerian Cycle cycle passing through every edge once, starts and finishing at different vertices 3 of 41 Node vertex; point 4 of 41 Arc edge 5 of 41 Digraph has directed arcs 6 of 41 Complete Graph every vertex is connected by an edge to each of the other vertices 7 of 41 Connected Graph vertices all connected by a path 8 of 41 Degree valency/order; number of edges connected to a vertex 9 of 41 Tree connected graph with no cycles 10 of 41 Spanning Tree sub graph including all vertices containing no cycles 11 of 41 Minimum Spanning Tree Spanning tree where the total length of arcs is as small as possible 12 of 41 Bipartite Graph two sets of vertices where the nodes cannot join to a node on the same side 13 of 41 Complete Bipartite Graph every vertex in set X joing to vertex on set Y 14 of 41 Eulerian all vertices from a node are even 15 of 41 Semi-Eulerian two vertices frim a node are odd; all other vertices are even 16 of 41 Traversable semi-eulerian or eulerian; otherwise non-traversable 17 of 41 Matching bipartite graph; no two edges have a common vertex 18 of 41 Complete Matching number of edges in matching is also the same amount as one set of nodes 19 of 41 Network weight on each arc represents the capacity of the arc 20 of 41 Source arcs directed away from node; usually starting node 21 of 41 Sink arcs directed towards node; usually finishing node 22 of 41 Dummy Activity critical path analysis; two chaings have a common event but are independent of each other 23 of 41 Alternating Path start at one unmatched node on one side and finish at one unmatched node on the other side; alternating route from unmatched to matched node 24 of 41 Critical Activities have a total float of O 25 of 41 Critical Path starts at source node, finishes at sink node and contains critical activities 26 of 41 Path sequence of edges; end vertex of one edge is the start vertex of another edge and contains no cycles 27 of 41 Bubble Sort swap until in order; end of pass; no change between passes=sorted 28 of 41 Kruscal's Algorithm check for cycles; put arcs in ascending order; starts with smallest arc edge and add shortest arcs first; check for cycles 29 of 41 Prim's Algorithm no need to check for cycles; start at any vertex and nearest vertex; can be used on a distance matrix 30 of 41 Distance matrix given point, delete row of point, smallest number in column? delete row of point, smallest number of 2 columns? 31 of 41 Dijkstra vertex|order|final value; remember to add working values; find shortest route 32 of 41 Describe how you found the shortest route? no need for words- show equations used 33 of 41 Chinese Postman Vertices|Degree; match odd nodes and traverse twice 34 of 41 Critical Path Analysis Activity|Depends on; 2 arcs from node cannot go to the same node- dummy needed 35 of 41 Gannt Chart Critical Activities at top; non criticial activities on individual lines 36 of 41 Linear Programming define variable, state objective, constraints and non-negativity 37 of 41 Vertex Testing Method Vertex|Co-ordinate|Value of C 38 of 41 First-fit bin packing with each object start from bin 1 39 of 41 First-fit decreasing bin packing put in descending order; with each object start from bin 1 40 of 41 full bin packing observation 41 of 41
Comments
No comments have yet been made