MATH1210

Example topic (for 2 hour lecture)

Networks and Graphs

•  Examples of networks
  (e.g., tube, road and rail networks, neural networks, the internet, ecology, linguistics, etc etc).
  Discussion of what features of each might be `important’.
  Discussion of the relationship between the tube and a tube map.  

•  Mathematical model of a network:
  Definition of a mathematical graph (i.e., lists of nodes and edges – nothing more technical).
  Farringdon--Barbican
  Invite suggestions of other things that could be viewed/modelled as a network. 

•  Adding weights to edges (or nodes) – what this means for examples discussed. 

•  Why might a model be useful? Typical questions of interest: 

  • oo Find a path through a network 

  • oo Find the `best’ path through a network 

  • oo Maximise flow through network 

  • oo What does network structure say about behaviour? 

  • oo What happens when the network changes/grows? 

Perhaps a conversation about `pure’ vs `applied’ approaches to these?

•  Eulerian walks (visit every `edge' once); 7 bridges of Ko”nigsberg; Chinese postman (finds shortest path visiting every edge);
  Hamiltonian paths (visit every `vertex' once)  

•  Activity – eg, design a small non-Eulerian graph; solve Hamilton’s original game; optimise a simple Chinese postman problem;
  mathematicians to prove Eulerian criterion to others 

• Modern network analysis – philosophical discussion about why questions are different, or just some data about massive networks 

• 6 degrees of separation – Erdos numbers; Kevin Bacon game (could play this) 

• Small world property – Watts-Strogatz model (nice example of a `new’ idea combining graph theory, randomness, etc) 

• Final discussion...