Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
D1 Definitions
All the definitions you could be asked for in the D1 exam
| Question | Answer |
|---|---|
| Algorithm | Precise set of instructions so clear that anyone can use them to achieve a particular goal in a specified number of steps |
| Graph | Vertices (or nodes) connected by edges (or arcs) |
| Subgraph | Part of a graph |
| Weighted Graph | Graph with numbers on each edge |
| Vertex Degree/Valency/Order | The number of edges incident to (coming out of) a vertex |
| Path | A finite sequence of edges such that the end vertex of one edge is the start vertex of the next edge and no vertex appears more than once |
| Walk | A path in which vertices can appear more than once |
| Cycle/Circuit | A closed path (the end vertex of the final edge is the same as the start vertex of the first edge) |
| Connected Vertices | Vertices with a path between them |
| Connected Graph | A graph in which all the vertices are connected |
| Loop | An edge which starts and finishes at the same vertex |
| Simple Graph | A graph with no loops and not more than one edge connecting any pair of vertices |
| Digraph | A graph in which some of the edges are directed (have a specified direction) |
| Tree | A connected graph with no cycles |
| Spanning Tree | A subgraph which includes all vertices of the original graph and is a tree |
| Minimum Spanning Tree | A spanning tree such that the total length of the arcs is as small as possible |
| Bipartite Graph | A graph consisting of two sets of vertices and edges which joins members of one set to members of the other set and has no edges joining members of a set to members of the same set. |
| Complete Graph | A graph in which every vertex is directly connected by an edge to every other vertex. |
| K_n | A complete graph with n vertices |
| K_(r,s) | A complete bipartite graph with r vertices in the first set and s vertices in the second set. |
| Isomorphic Graphs | Graphs which show the same information but are drawn differently |
| Adjacency Matrix | A matrix recording the number of direct links between vertices |
| Distance Matrix | A matrix recording the weights on the edges of a weighted graph. |
| Traversible (Eulerian) Graph | A graph in which every vertex is even, making it possible to traverse every arc once and return to the start vertex. |
| Semi-Traversible (Semi-Eulerian) Graph | A graph with precisely two odd vertices, making it possible to traverse every arc once provided you start and finish at the odd vertices. |
| Non-Traversible Graph | A graph with more than two odd vertices |
| Critical Activity | An activity for which an increase in its duration results in a corresponding increase in the duration of the project. Critical activities have no float. |
| Critical Path | A path from source to sink node which only follows critical activities. The longest path in the network, it represents the shortest possible time for the job to be completed. |
| Float | The difference between the amount of time available for an activity and its duration. It represents the amount of time an activity can be delayed without affecting the duration of the whole project. |
| Dummy Activity (Dependence) | An activity with no weight needed because activity C depends only on activity A but activity D depends on both A and B |
| Dummy Activity (Uniqueness) | An activity with no weight needed to enable the unique representation of activities in terms of their start and end events |
| Alternating Path | A path starting at an unmatched node of a bipartite graph and finishing at an unmatched node from the alternate set of the bipartite graph which uses arcs alternately in and not in the initial matching. |
| Matching | A one to one pairing of some or all of the nodes of one set in a bipartite graph with nodes of the alternate set. One to one means each node from one set is matched with only one node from the alternate set. |
| Maximal Matching | A matching in which the number of arcs is as big as possible. |
| Complete Matching | A matching in of two sets, each containing n nodes, which has n arcs. |
| Bubble Sort | An algorithm to put a list into order using direct comparisons of adjacent elements. It stops when you complete a full pass with no swaps. |
| Quick Sort | An algorithm to put a list in order using pivots. It stops when all elements are fixed. |
| Bin Packing (First Fit) | Place the items in the first bin that will take them using the order in which they are given. It is quick but not likely to lead to a good solution |
| Bin Packing (First Fit Decreasing) | Place the items in the first bin that will take them starting with the largest. It is easy and leads to a good solution but it may not be the optimal solution. |
| Bin Packing (Full Bin) | Place the items into the bins by eye in order to fill as many bins as possible. It leads to a good solution but is difficult. |
| Binary Search | An algorithm to locate a name in an ordered list. Finishes when the name is located or the list becomes empty. |
| Kruskal | An algorithm for constructing a minimum spanning tree in a weighted network, it finds the fastest/cheapest way to link nodes in a system. Starts with the smallest arc and adds/rejects arcs in increasing order of size. |
| Prim | An algorithm for constructing a minimum spanning tree in a weighted network, it finds the fastest/cheapest way to link nodes in a system. Can starts with any node and has no need to check for cycles. Can be applied to a distance matrix. |
| Dijkstra | An algorithm for finding the shortest/fastest/cheapest route from a start node to any other node in a weighted network. |
| Matching Algorithm | An algorithm for improving a one to one pairing of elements of one set with elements of another set represented by a bipartite graph. |
| Route Inspection | An algorithm for finding the length of the shortest traverse through a non-Eulerian graph, identifying which arcs should be repeated and at which nodes to start/finish. |
| Linear Programming | A method of optimising a function given various constraints. Starts by formulating constraints and sketching the feasible region and can be completed using either the ruler or vertex method. |
| Critical Path Analysis | An algorithm to identify the shortest time to complete a sequence of dependent activities and the minimum number of workers needed. |
Created by:
100001246054504
Popular Math sets