Decision 1

• Graph Theory - Components

  Node - a point on the graph

  Edge - the line connecting two nodes together or a node to itself
• Graph Theory - Types of graph

  If a graph has a number associated with each edge - weighted graph, or network
• Graph Theory

  The number of edges connected to a node is the nodes... valency, or order
• Graph Theory

  • A walk is a route through a graph
  • A path is a finite sequence of edges where no node occurs more than once
  • A trail is a path where no edge appears more than once
  • A cycle is a walk in which the starting and ending node are the same and no node appears more than once
  • A Hamiltonian Cycle is a cycle which visits every node
• Graph Theory - Types of graph

  • A connected graph is a graph where you can get from any node to any other node
  • A subgraph is a graph made entirely out of edges and nodes from another graph
  • A simple graph has only one or no edges between two nodes and includes no loops
  • A digraph (directed graph) includes directions on some or all of the edges
• Graph Theory - Euler's handshake lemma


  In an undirected graph, the sum of the valencies on a graph is equal to 2 times the number of nodes. Therefore the total valency is alway even
• Graph Theory - Special types of graph

  • A tree is a connected graph with no cycles
  • A spanning tree is a subgraph with all the nodes and edges of the graph and is a tree
  • A bipartite graph has two sets of nodes, x and y. Edges join x to y but not x/y to itself
  • A complete bipartite graph has all nodes on one side connected to all nodes on the other side
  • Isomorphic graphs are the same as each other but drawn in a different arrangement
• Graph Theory - n

  • a tree with n nodes has n-1 edges
  • a complete bipartite graph with n nodes on the left and m on the right (K_n,m) has nm edges
  • a complete graph with n nodes (K_n) has n(n-1)/2 edges (triangle numbers)
• Algorithm to check if a graph is planar:


  Planarity algorithm
• Planarity algorithm:

  1. Find a Hamiltonian cycle
  2. Make this the edge of a polygon
  3. Choose an edge and redraw all edges that cross it on the outside of the polygon
  4. Repeat until planar if the graph is planar

  Create a table of "in" or "out" as you go along
• What is an adjacency matrix?


  It tells you how many edges join a pair of vertices
• What algorithms find a minimum spanning tree?


  • Kruskal's
  • Prim's
• Kruskal's algorithm:

  • consider edges in ascending order of weight
  • if the edge does not create a cycle, tick it and then add it
  • if it creates a cycle, reject it
• Prim's algorithm:


  • Start at the point indicated
  • add the shortest edge
  • consider all connected edges:
  • add the shortest edge (which does not create a cycle)
  • repeat until all vertices connected
• Which algorithms help find shortest paths?


  • Dijkstra's
  • Floyd's
• Dijkstra's algorithm:

  • Starting at the vertex indicated, label this 1
  • add the distance to any directly connected edges in their working values box
  • repeat on the vertex with the lowest value in the working values box - label this 2 and so on
  • repeat until all vertices have been given a number
  • the final value is the minimum distance from the starting vertex to that vertex and is the smallest value from the working values
  • the final value in the target vertex is the distance from the starting to the target vertex
• Floyd's algorithm:

  • uses distance and route tables
  • create a distance table, writing infinity if not directly connected
  • copy the table but only add in the row and column for (eg. A)
  • if it would be quicker to go from one vertex to another via A then replace the value with this new value via A
  • indicate the change with []. Edit the route table to indicate the route is via A
  • repeat for all other edges
• Comparing Floyd's and Dijkstra's

  • Floyd's finds the minimum distance between any pair of vertices whereas Dijkstra's just finds the minimum distance between one pair of vertices
• Finding the minimum distance and route using a distance and route table completed from Floyd's algorithm

  • eg. use the table to find the min distance between A and C
  • check the distance table, the distance listed A to C is the minimum distance
  • check the route table, check what the letter in row 1 (A) column 3 (C) is. If it is C then the route is direct, eg. if it was B then the quickest route from A to C goes via B
  • now A to B and B to C must also be checked if they are direct or not
• Eulerian graphs

  • if the valency of every vertex is even then the graph is traversable from any vertex to any other
  • if the valency of all but two vertices is even then the graph is only traversable from one odd to another
• Route inspection algorithm (Chinese Postman Algorithm):

  • List all odd vertices
  • list all pairings of these nodes
  • find the minimum distance and route between the pairs
  • pick out the pairings which give the minimum length
  • the final result is that the new weight of the graph shall be the weight of the original graph plus the weight of the minimum distance of the pairs
  • the minimum route between these pairings must be listed as edges to repeat
• A tour is a walk which starts and finishes at the same vertex and visits every vertex