or

or

taken

why

Make sure to remember your password. If you forget it there is no way for StudyStack to send you a reset link. You would need to create a new account.

Enter the associated with your account, and we'll email you a link to reset your password.
Don't know
Know
remaining cards
Save
0:01
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

# D1 Definitions

### All the definitions you could be asked for in the D1 exam

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