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...