Ajude a dar forma ao GoConqr. O que a gente deve adicionar?

Mapa mental

D1 Revision

shnoz Inglês

Mind map about D1 revision: graphs and networks, algorithms and linear programming

Mind map: D1 revision: graphs, algorithms and linear programming

Conteúdo do mapa

D1 Revision

  1. Graphs and Networks

    • The order of a node is the number of arcs that meet at that point
    • Eulerian graphs: each node be of even order; uses every vertex in the graph
      • a connected graph with a closed trail containing every arc exactly once
      • these can be drawn without taking your pen off of the paper, with your pen ending at the same node it started at
    • Semi-Eulerian Graphs: exactly two nodes of odd order; uses every vertex in the graph
      • a connected graph which has a trail (crucially not closed) that contains every arc exactly once
    • Connected graph: is one where a path (not necessarily direct) can be found from any two nodes
    • Simple graph: A graph with no loops, no multiple edges and every vertex is connected
    • In any graph there must be an even number of odd nodes
    • The total of the orders of all the nodes in a graph = 2 x the number of acrs, and therefore is even
    • A planar graph is a graph that can be redrawn so that no arcs cross-over
    • Kruskal's algorithm
      • 1) List the arcs in order of weight, smallest first
      • 2) Choose the arc with the smallest weight
      • 3) Choose the next arc of smallest weight which does not form a cycle
      • 4) Repeat step 3 until all vertices have been included
    • Prim's Algorithm
      • 1) Select any node
      • 2) Select the shortest arc connecting the tree to a new node
      • 3) Incorporate that arc and the node into the tree
      • 4) Repeat steps 2 & 3 until all nodes are connected
      • Can also be done from a matrix
    • Dijkstra's algorithm (the one with the boxes)
      • 1) Give the start node a permanent label of 0
      • 2) Give each node connected to start node a temporary label
      • 3) Find the smallest temporary label and make it permanent
      • 4) Update temporary labels for any node that can be directly reached from new node in tree
      • 5) Repeat 3 & 4 until destination is reached
    • Route Inspection (chinese postman)
      • 1) Find all the nodes of odd order
      • 2) For each pair of odd nodes find the shortest path that joins them
      • 3) Pair up all the odd nodes to find the pairing with the shortest total distance connecting them
      • 4) In the original network, duplicate the minimum weight paths from step 3
      • Lower Bound
        • 1) Choose a node as the special node
        • 2) Find a minimum connector for the remaining network
        • 3) Add in the weights of the two least weighted arcs from the deleted node
      • Upper Bound
        • The upper bound is any cycle
    • Nearest Neighbour
      • 1) Choose any node as a starting point
      • 2) Find the next nearest node the the previously selected one
      • 3) Repeat step 2 until all nodes have been selected
      • 4) Join the last vertex to the first vertex via the shortest route
  2. Algorithms

    • Bin packing
      • First fit decreasing
        • Sort the items into decreasing order and then perform first fit algorithm
      • First fit
        • First fit; place the next item in the first available bin that can take it
    • Shuttle sort
      • 1) Compare 1st & 2nd numbers in the list, swap if necessary
      • 2) Compare 3rd & 2nd numbers, swap if necessary. If a swap is made compare the 2nd & 1st
      • 3) Compare 4th & 3rd number, swap if necessary. If sway made, compare 3rd & 2nd etc
      • Repeat until there are no swaps or you reach the beginning of the list
      • Number of passes = length of original list - 1
      • Number of swaps = number of comparisons - 1, unless number moves to the front of the list
    • Bubble sort
      • 1) If there is only 1 number in list, stop
      • 2) Work your way from right to left,comparing adjacent numbers, swapping if necessary. (after first pass the number furthest right is in its correct position)
      • 3) If swaps were necessary then repeat step 2, comparing one less number in each pass
      • 4) Algorithm is complete when no swaps are necessary
      • Can finish early if no swaps are required
  3. Linear Programming

Informações

Descrição
Mapa Mental sobre D1 Revision, criado por shnoz em 28-02-2015.
Criado por
shnoz
Visualizações
4
Avaliação

Mais sobre Graph and Network Algorithms

Fale Conosco

Sobre o que é sua mensagem?

O que a gente deve adicionar?