|
|
|
Here is what someone (not me) wrote when asked to summarize Graph Theory in the context of an undergraduate module:
Graph theory is one of the primary subjects in discrete mathematics. It arises wherever networks (such as computer networks and transportation networks) are found,
and it has applications to fields diverse as chemistry, computing, linguistics, navigation, and more.
More generally, combinatorics concerns finding patterns in discrete mathematical structures, often with the goal of counting the occurrences of such patterns.
This module provides a foundation in graph theory and combinatorics.
Graph theory can be thought of as a part of the field of discrete mathematics.
(Discrete maths is the part of maths that aims to empower the scholar without relying on a deep understanding of the real line.
Or to put it another way, it is the study of systems that, as sets,
can be assigned a first element and such that any element can be reached by counting - unlike the real line, but like the natural numbers.)
Graph theory is the part of discrete maths where systems can be studied by studying not just their elements, but relationships between elements in groupings - typically pairs
(and relationships in larger groupings by extension from pair-relationships).
Graph theory arises wherever networks (such as synapses, crystal lattices, social networks, computer networks and transportation networks) are found.
It has applications to fields such as social science, chemistry, physics, biology, computing, linguistics, navigation, engineering, and many more.
Combinatorics
more generally
concerns finding patterns in,
and hence understanding,
systems that are well-modelled by
discrete mathematical structures.
This is often with the goal of counting the occurrences of such patterns.
On successful completion of the module students will have demonstrated the following learning outcomes relevant to the subject:
1. understand the concepts of graph, tree, and partial order;
2. describe the basic properties of a given graph;
3. find spanning trees, matchings, covers, special cycles and trails, homogeneous sets, etc. in a given graph;
4. understand the statements of some representative key theorems in graph theory and combinatorics (such as the theorems sometimes known as Hall's theorem, Menger's theorem, Ramsey's theorem, and Dilworth's theorem);
5. understand basic proof techniques in graph theory and combinatorics;
6. make basic graph-theoretic and combinatorial arguments;
7. articulate the relations among the theorems discussed;
8. derive simple consequences of the theorems discussed.