Graphs & Networks + Route inspection

• Degree/ Valency/ Order of a vertex

  • the number of edges incident to it
• Path

  No vertex is visited more than once
• Trail

  no edge is visited more than once
• Cycle 


  starts and ends at the same vertex, no other vertex repeated (no need visit all vertices)
• Hamiltonian cycle

  starts and ends at same vertex, includes every vertex but not repeated
• Connected graph


  where all vertices are connected
• Handshake Lemma

  2 x no. of edges = sum of agrees of the vertices

  • no. of odd vertices must be even
• Simple graph

  where there are no loops and there is at most one edge connecting any pair of vertices
• Digraph (directed graph)


  where there are arrows (directed edges)
• Complete graph


  where every vertex is directly connected by a single edge to each of the other vertices

  • written as Kn
• Edges required to draw a complete graph (Kn)

  equation: [n= vertices]

  $(n-1)(n) 1/2$
• Isomorphic graphs


  same graph drawn differently
• Adjacent matrix


  chart showing no. of arcs between verticies (non-weighted)
• Distance matrix


  chart showing weight of each arc between vertices (weighted graphs)
• In directed and weighted graphs, weight is written as "-" when it is not in the direction of the arrow
• Eulerian Graph


  where:

  • vertices are all even
  • connected graph
• Semi-Eulerian


  where:

  • exactly two vertices are odd
  • connected graph
• CPA for Eulerian 


  total weight of the network
• CPA for Semi-Eulerian 


  total weight of network + length of the shortest path between the two odd vertices
• CPA for neither Semi-Eulerian/ Eulerian 


  Process:

  1. consider all pairings between all vertices with odd degree
  2. select the complete pairing with the least sum
  3. Add sum to total weight of each edge