Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
29 Cards in this Set
- Front
- Back
|
What is a graph? |
Consists of points (vertices/nodes) which are connected by lines (edges/arcs) |
|
|
What is a weighted graph or network? |
A graph with numbers associated with each edge |
|
|
What are vertices in a graph? |
Points |
|
|
What are the lines in a graph called? |
Edges or arcs |
|
|
What is a subgraph? |
Part of another graph ( not all parts need to be connected) |
|
|
What is degree, valency or order of a vertex/node? |
The number of edges incident in it |
|
|
What is a path? |
A finite sequence of edges where no vertex/node appears more then once -doesn't need to include all vertices/nodes |
|
|
What is a walk? |
A path in which you can return to a vertex more then once |
|
|
What is a cycle? |
A closed path. The end vertex/node of the last edge/arc is the start vertex/node of the first edge/arc -doesn't need to include all vertices/nodes and can include each vertices/node more then once |
|
|
What is a loop? |
An edge/arc that finishes and starts at the same vertex/node |
|
|
What is a simple graph? |
One in which there are no loops and didn't have more then one edge/arc connecting any two vertex/nodes |
|
|
What is a digraph? |
A graph where the edges have a direction associated with them |
|
|
What is the handshaking lemma? |
The sum of the degrees is equal to twice the number of edges |
|
|
What is the handshaking lemma? |
The sum of the degrees is equal to twice the number of edges |
|
|
What is a tree? |
A graph with no complete cycle |
|
|
What is a tree? |
A connected graph with no complete cycle |
|
|
What is the minimum spanning tree? |
A tree where the total number of all arcs is a minimum Includes all the vertices and is a tree |
|
|
What is a bipartite graph? |
Consists of two sets of vertices. The edges/arcs only join the vertices of each set not the vertices/nodes within the set |
|
What is a complete bipartite graph? |
|
|
|
What are ismorphic graphs? |
Graphs which show the same information but are drawn differently They must have the same number of vertices of the same degree which must be connected together in the same way |
|
|
What does the adjacency matrix do? |
Record the number of direct line between vertices |
|
|
What does the distance matrix do? |
Record the weights on the edges Where there is no edge write - |
|
|
State briefly Prims algorithm |
Select any vertex to start tree Select the shortest arc that joins a vertex already in the tree to a vertex not yet in the tree Add it to the tree Continue selecting shortest arcs until all vertices are in tree |
|
|
Select Kruskals algorithm |
Select arc of least weight to start tree Take arcs in order of weight Reject any arc of would form cycle Add to tree if will not form cycle Continue until all vertices connected |
|
|
What are the advantages of Prims algorithm |
It is easily converted into matrix form It is difficult to Kruskals algorithm as it is difficult to check for cycles in large network's |
|
|
Describe the differences between Prime's and Kruskals algorithms |
In prims the tree grows in a connected fashion, there is no need to check for cycles, can be adapted to matrix form, starts with any vertex Kruskals starts with an edge, the least edge. |
|
|
Why are dummies used? |
1. To show dependency Or 2. So each activity can be uniquely represented in terms of events |
|
|
What is a critical path? |
A path with zero float/no delay from start to end |
|
|
What is a critical path? |
A path with zero float/no delay from start to end |
