MATH 2420 Introduction to Graph Theory and Optimization
Course Description
Students taking this course will be expected to know the basic principles of sets and number systems, linear algebra and analytical geometry. For this reason, MATH 1152 and MATH 1141 are listed as course prerequisites.
This course can be divided into two sections of (i) graphs and digraphs and (ii) linear programming. In (i), we begin with basic graph theoretic definitions that also involve graphical operations. Some simple theorems are proved including an extremal result. We express some of these concepts in the missionaries and cannibal problems as well as the instant insanity problem. Next we define a number of important matrices associated with these graphs via an examination of the general entry of products of these matrices. In so doing, digraphs are introduced and an application is demonstrated in the finding of determinants. Properties of relations are visualized with respect to structural features of digraphs. We formulate communication networks and kernels by the use of digraphs. This leads to the definitions of basis digraphs, progression sequences and canonical ordering of nodes. These graphical concepts are then incorporated into the solving of a system of linear equations. In (ii), we revise the linear relation in the Cartesian plane. The idea of a convex set is introduced in relation to maximization and minimization linear programming problems. Extreme points of bounded polyhedral regions are found by the simplex method and also by simple constructions in the xy plane. The principle of duality is given.
