Ayúdanos a dar forma a GoConqr. ¿Qué deberíamos añadir?

Fichas

Decision 1

Alice Butterworth Maths AS - Level Inglés 44 fichas

What is a planar graph?

Fichas del conjunto (44)

  1. 1What is the bubble sort algorithm?-Start at the benign of the list.
    -Pass through the list and compare adjacent values, For each pair If they are in the right order leave them, if not swap them.
    -When you reach the end of the list repeat steps 1 and 2.
    -When a pass is completed without any swaps, the list is in order.
  2. 2What is the quick sort algorithm?-Choose the item at the midpoint of the list to be the first pivot.
    -Write down all the items that are less than the pivot, keeping their order
    -Write down the pivot
    -Write down the remaining items, keeping their order
    -Apply steps 1 to 4 to the knew list
    -When all items have been chosen as pivots stop.
  3. 3What is the Binary search algorithm?To search an ORDERED list of ,n, items for target, T
    -Select the middle item in the list, m, use ((n +1) over 2) and round up
    -If T=m then target is found and search is complete, If T < m discarded any >m, if T > m discard any
  4. 4How do you find a lower bound in a bin packing algorithm?Total duration of the boxes divided by the bin capacity.
    E.g there is a total volume of 8.5 activities but each bin can hold a volume of up to 2 activities. 8.5/2=4.25= at least 5 bins
  5. 5What is the full bin algorithm?-Putting jobs in by eye
    -use observations to find combinations of items that will fit in a bin
  6. 6What is the first fit algorithm?-Taking jobs in the order they are given.
    -Placing them in first available bin.
  7. 7What is the first fit decreasing algorithm?-Rearrange jobs so they're in decreasing order.
    -Place in the first available slot.
  8. 8What is a planar graph?A graph that can be drawn without any edges overlapping.
    E.g.
    What is a planar graph?
  9. 9What are isomorphic graphs?-Two graphs with the same number of vertices and corresponding vertices have the same degree of edges
    E.g.
    What are isomorphic graphs?
  10. 10What is a complete graph?-A graph with every vertex connected to each other by an edge. A graph with n vertices is denoted kn.What is a complete graph?
  11. 11What is a Bipartite graph?-Two sets of vertices of x and y
    -Edges only join vertices in x to y and vice versa
    What is a Bipartite graph?
  12. 12What is a loop?-An edge that starts and ends at the same vertexWhat is a loop?
  13. 13What is a vertex set?All the vertices.
  14. 14What is an edge set?All the edges
  15. 15What is a tree?-A connected graph with no cycleWhat is a tree?
  16. 16What is a spanning tree?- A tree that includes all the verticesWhat is a spanning tree?
  17. 17What is the degree of a vertex?-The number of edges incident to it
  18. 18What is a simple graph?-There are no loops or more than one edge connecting a pair of verticesWhat is a simple graph?
  19. 19What is a walk?-A path that passes through vertices more than once.What is a walk?
  20. 20What is a directed edge?-An edge with a given directionWhat is a directed edge?
  21. 21What is a Digraph?-A graph with directed edges on themWhat is a Digraph?
  22. 22What is a eulerian cycle?-A cycle that passes through every edge.
  23. 23What is a hamiltonian cycle?-A cycle that passes through every vertex
  24. 24What is a cycle?-A closed path, the end vertex of the last edge are the same is the start of the first edge.
  25. 25What is a path?-A finite sequence of edges.
  26. 26What is an adjacency matrix?-An adjacency matrix is a table that represents a graph.What is an adjacency matrix?
  27. 27What is a distance matrix?-A matrix where the numbers represent the distance between vertices.
  28. 28What is Kruskals algorithm?-List all edges in ascending order
    - Choose the edge with the smallest weight
    -From the remaining edges choose the edge with the smallest weight, as long as it doesn't form a cycle with the edges already chosen
    -Repeat step 3 until all the vertices have been included.
  29. 29What is Prim's algorithm? (On a graph)-Choose a start vertex
    -Connect the start vertex to the nearest new vertex by adding the shortest edge
    -From any vertex on the tree so far, add the shortest edge that connects a new vertex
    -Repeat step 3 until all the vertices have been included
  30. 30What is Prim's algorithm on a matrix?-Choose a start vertex. Label the column corresponding to that vertex with a 1 and delete that row.
    -Look in all the columns that have been numbered so far. Circle the smallest undeleted entry and read off the vertex for the row.
    -Label the column corresponding the this vertex with the next available label then delete that row.
    -Repeat steps 2 and 3 until all the rows have been deleted.
  31. 31What is Dijkstra's algorithm?To find the shortest path from S to T through a network
    -Label the start vertex, S, with the final label 0
    -Record a working value at every vertex, Y, that is directly connected to the vertex, X, that has just received its final label
    *Working value at Y= final value at X + weight of arc XY
    *If there is already a working value at Y, it is only replaced if the new value is smaller
    *Once a vertex has a final label it is not revisited and its working values are no longer considered.
    -Look at the working values at all vertices without final labels. Select the smallest working value. This now becomes the final label at that vertex. (If two vertices have the same smallest working value either may be given its label first)
    -Repeat steps 2 and 3 until the destination vertex, T , receives its final label.
    -To find the shortest path, trace back from T to S.
  32. 32What are eulerian and semi eulerian networks?--All the vertices have an even number of degrees
    -Only two have an odd number.
  33. 33What is the route inspection algorithm?-Identify the odd vertices
    -Write down all the possible pairings of the odd vertices
    -For each pairing write down the shortest path between the vertices. Add up the weights on the shortest paths and choose the pairing with the smallest total.
    -Write down a trail using the shortest paths from the chosen pairing twice, and all the other edges once.
    -Add up the weights from the original graph and the total from step 3
  34. 34What is a matching?-A one to one pairing of some or all of the elements
  35. 35What is a complete matching?When every member of x is connected to a vertex of y
  36. 36What is the matching algorithm?-An alternating path starts at an unmatched node one side of the bipartite graph and finishes at an unmatched node on the other side. It uses edges that are alternately in or not in the initial matching.
    -You change the status of the edges (from matched to unmatched and vice versa)
    -Repeat until all vertices are matched.
  37. 37What is the slack?-The difference between the numbers in the boxes in critical path analysis. It represents an allowable delay that won't affect the project time
  38. 38What is the float?-The difference between the latest finish time and the earliest start time and the duration of the activity.
  39. 39What is a critical event?-An event is critical if the slack is 0
  40. 40What is a critical activity?-An activity is critical if the float is 0
  41. 41What is a critical path?-A path from the source node to the sink node through critical activities.
  42. 42Which is the earliest start time and which is the latest finish time? __ l__l l__l-Top box is the earliest start time, this has to be the largest length of time you have leading into it.
    -Bottom box is the latest finish time, this has to be the smallest number you have.
  43. 43What is a dummy? Why is it used?A dummy is a dotted line in an activity network. Its used when one activity is dependent on two others that are independent to each other.
  44. 44How do you figure out the lower bound of an activity network?The sum of the duration of the activities over the latest finish time.

Información

Descripción
AS - Level Maths Fichas sobre Decision 1, creado por Alice Butterworth el 12/01/2016.
Visitas
0
Valoración

Más sobre Graph and Network Algorithms

Escríbenos

¿Sobre qué es tu mensaje?

¿Qué deberíamos añadir?