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

(back)