Revision:Graphs and networks

A graph consists of a finite number of points (nodes) connected by lines (arcs).

Definitions

  • In a complete graph every node is connected by an arc to each of the other nodes. There are \frac{1}{2} n(n-1) arcs in a complete graph with n nodes.
  • In a connected graph there are no isolated nodes.
  • trail is a sequence of arcs such that the end node of one arc is the start node of the next.
  • closed trail (or cycle) is a route through the nodes which starts and finishes in the same place. No arc is used more than once. Only the start node is used more than once.
  • path is a trail where no node is passed more than once.
  • The order of a node is the number of arcs meeting at that node.
  • An Eulerian graph is a connected graph which has a closed trail containing every arc precisely once. This can occur if and only if every node is even.
  • semi-Eulerian graph is a connected graph which has a trail (not closed) containing every arc precisely once. It occurs when a graph has 2 odd nodes: the trail starts at one odd node and ends at the other.
  • planar graph is one which can be drawn so that arcs do not cross each other.
  • tree is a connected graph with no cycles.
  • The spanning tree of a graph G is a subgraph which contains all the nodes of G, with no cycles.
Simple graph

Matrix formulation

Networks can be represented by matrices. If the network has only 2 way links (no arrows) the matrix is symmetrical about a diagonal drawn from top left to bottom right.

 

  A B C D
A   2 4  
B 2   3  
C 4 3   1
D     1