Register  
 
About Us | Help | Sign in
 
   

Revision:Graphs and Networks

From The Student Room

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > Graphs and Networks



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

Contents

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.
  • A trail is a sequence of arcs such that the end node of one arc is the start node of the next.
  • A 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.
  • A 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.
  • A 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.
  • A planar graph is one which can be drawn so that arcs do not cross each other.
  • A 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.

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. Image:Simple graph.jpg

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

Also See

See the other D1 notes:

  1. Algorithms
  2. Sorting algorithms
  3. Packing algorithms
  4. Graphs and networks
  5. Minimum connector problems
  6. The shortest path
  7. Route inspection
  8. The travelling salesman problem
  9. Linear programming
  10. The simplex algorithm

Comments

collapse
Recent Threads
 
collapse Colleges
started by: im so academic
replies: 1
last post: 1 Minute Ago
collapse Night Sweats
started by: Anonymous
replies: 6
last post: 1 Minute Ago
collapse Need help setting up a webpage
started by: leonardo857
replies: 5
last post: 1 Minute Ago
collapse Living in Halls at 21
started by: andrew2008
replies: 4
last post: 1 Minute Ago
collapse Im pregnant
started by: Anonymous
replies: 45
last post: 1 Minute Ago