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;
27 Cards in this Set
- Front
- Back
|
What is a Connected graph? |
When all pairs of vertices are connected |
|
|
What is a Eulerian graph? |
The degree of every vertex is of even order |
|
|
What is a Hamiltonian Cycle? |
Visits every vertex og a graph by only using the edges once. Dosent have to use all edges |
|
|
For a network of n vertices how many edges in the min spanning tree? |
n-1 edges in a minimum spanning tree |
|
|
A complete graph with n vertices has how many edges? |
A complete graph with n vertices is called Kn and has n(n-1)/2 edges |
|
|
The number of Hamiltonian cycles in a complete graph with n vertices? |
in a complete graph with n vertices (Kn) is 1/2(n-1)! |
|
|
Bubble sort? |
-Compare first two numbers -Move one step forwards in the list and compare the two numbers -Repeat Step 2 until the two numbers on the extreme right havebeen compared, this completes the FIRST PASS. -SECOND PASS repeat Step 1 – 3 but no need to compare last 2 inthe list |
|
|
Shuttle sort |
-Compare first two numbers swap if necessary rewrite theremainder of the list -Compare second and third number swap if necessary rewrite theremainder of the list. Now compare the first two numbers swap ifnecessary and re-write the list |
|
|
facts about BUBBLE AND SHUTTLE |
For a list of n numbers the list will definitely be sorted after the (n-1)th pass Maximum number of comparisons/swaps = n(n-1)/2 Shuttle can be more efficient than bubble as ‘pass’ stops when no swap needed. |
|
|
Shell sort |
divide list into n/2 sub-lists and shuttle sort each group divide each sub-list into n/2 and shuttle sort. continue until group size =1 |
|
|
Quick sort |
-underline PIVOT value in list, box in pivot value in resorted list once boxed the value stays boxed until the end. -Continue until none of the sublists have more than 2numbers (eg. No more than 1 unused value between pivots) |
|
|
Chinese postman |
Travels along every edge at least once before returning to the start in the minimum distance. - list all of the odd nodes in the network - List the different ways in which the odd nodes could be paired - find the shortest distance for each of the pairs - add to min spanning tree |
|
|
travelling salesman (Lower bound) |
- delete one of the vertices -find a minimum spanning tree for the remaining vertices -add to the spanning tree to weights of the two smallest edges from the deleted vertex -the biggest answer is the best LOWER BOUND |
|
|
travelling salesman ( Upper bound) |
- choose a starting node - join this node to the nearest node - join your new node to the nearest node – when youhave included all nodes – join the last node you picked back to the start basically prims smallest upper bound is the best |
|
|
travelling salesman (optimum solution) |
You have found the optimum solution if Upper bound = Lower Bound |
|
|
Finding the optimal solution in linear programing |
- if maximising look for point further away from origin and objective line moves out of feasible region -if minimising look for point closest to origin |
|
|
minimum num of edges on a connected graph? |
n-1 |
|
|
max number of edges on a connected graph? |
n(n-1)/2 |
|
|
simple graph has 6 vertices with degree d state possible values of d stated d if eulerian and d if connected |
0,1,2,3,4,5 2,3,4,5 2,4 |
|
|
for a graph of k(n) can only be Eulerian |
n is odd |
|
|
the total number of edges of k(n) |
n(n-1)/2 |
|
|
if 40 of of x y and z have to be y whats the eqution |
y>>(40/100)(x+y+z) |
|
|
How to do a Minimum spanning tree on a tablr |
If start at A find shortest distance from A and add. Find next shortest distance from already visited places and add |
|
|
Explain why something can be described as a upper bound |
Because the tour can be improved |
|
|
If you need to use dijkstra with multiple start points what do you do? |
End point is 0 and work from there |
|
|
A simple graph with 10 vertices. What oder can the vertices be? |
0 <<x <<9 |
|
|
For k (n) to be eulerian |
N must be odd |
