What's in MT365? ( Although it's a level 3 course there aren't much hard pre-requisites, just a certain mathematical maturity whatever that is. )
The course is divided into three related areas: graphs, networks and design. The Introduction introduces two themes of the course, combinatorics and mathematical modelling, and illustrates them with examples from the three areas.
Graphs 1: Graphs and digraphs discusses graphs and digraphs in general, and describes the use of graph theory in genetics, ecology and music, and of digraphs in the social sciences. We discuss Eulerian and Hamiltonian graphs and related problems; one of these is the well-known Königsberg bridges problem.
Networks 1: Network flows is concerned with the problem of finding the maximum amount of a commodity (gas, water, passengers) that can pass between two points of a network in a given time. We give an algorithm for solving this problem, and discuss important variations that frequently arise in practice.
Design 1: Geometric design, concerned with geometric configurations, discusses two-dimensional patterns such as tiling patterns, and the construction and properties of regular and semi-regular tilings, and of polyominoes and polyhedra.
Graphs 2: Trees Trees are graphs occurring in areas such as branching processes, decision procedures and the representation of molecules. After discussing their mathematical properties we look at their applications, such as the minimum connector problem and the travelling salesman problem.
Networks 2: Optimal paths How does an engineering manager plan a complex project encompassing many activities? This application of graph theory is called ‘critical path planning’. It is one of the class of problems in which the shortest or longest paths in a graph or digraph must be found.
Design 2: Kinematic design The mechanical design of table lamps, robot manipulators, car suspension systems, space-frame structures and other artefacts depends on the interconnection of systems of rigid bodies. This unit discusses the contribution of combinatorial ideas to this area of engineering design.
Graphs 3: Planarity and colouring When can a graph be drawn in the plane without crossings? Is it possible to colour the countries of any map with just four colours so that neighbouring countries have different colours? These are two of several apparently unrelated problems considered in this unit.
Networks 3: Assignment and transportation If there are ten applicants for ten jobs and each is suitable for only a few jobs, is it possible to fill all the jobs? If a manufacturer supplies several warehouses with a product made in several factories, how can the warehouses be supplied at the least cost? These problems of the system-management type are answered in this unit.
Design 3: Design of codes Redundant information in a communication system can be used to overcome problems of imperfect reception. This section discusses the properties of certain codes that arise in practice, in particular cyclic codes and Hamming codes, and some codes used in space probes.
Graphs 4: Graphs and computing describes some important uses of graphs in computer science, such as depth-first and breadth-first search, quad trees, and the knapsack and travelling salesman problems.
Networks 4: Physical networks Graph theory provides a unifying method for studying the current through an electrical network or water flow through pipes. This unit describes the graphical representation of such networks.
Design 4: Block designs If an agricultural research station wants to test different varieties of a crop, how can a field be designed to minimise bias due to variations in the soil? The answer lies in block designs. This unit explains the concepts of balanced and resolvable designs and gives methods for constructing block designs.
Conclusion In this unit, many of the ideas and problems encountered in the course are reviewed, showing how they can be generalised and extended, and the progress made in finding solutions is discussed.
No comments:
Post a Comment