UTSA logo Applied Graph Theory
MAT 4323
Spring 2003
Instructor: J. Iovino
 

The course has been scheduled for M,W, between 12 noon and 1:15 pm, at HSS 3.04.22 (1604 campus).

Brief description

Graph Theory is the mathematical study of diagrams, or graphs.

The course is intended to serve as an introduction to finite mathematics, and is strongly recommended for computer science, electrical engineering, mathematics, and statistics majors. Graphs and combinatorics underlie the analysis of all computer systems, and play a fundamental role in probability, game theory, and discrete optimization.

We will follow the first four chapters of Alan Tucker's book Applied Combinatorics (see detailed bibliographic information below). This is a very established textbook. It has a wealth of examples and applications, and for about two decades, it has been used by many mathematics, engineering, computer science, and statistics departments around the world. The author emphasizes general reasoning skills over formalism.

Prerequisites

Essential prerequisite: love for mathematics and analytic problem solving.

Formal prerequisite: at least one the following courses,

Foundations of Mathematics (MAT 2243)
Discrete Mathematical Structures (CS 3233)
Calculus II (MAT 1223),
or instructor consent.

Content

  • Elements of Graph Theory. Graph models, isomorphism, planar graphs.
  • Covering Circuits and Graph Colorings. Euler circuits, Hamilton circuits, graph colorings.
  • Trees and Searching. Spanning trees, the Traveling Salesman Problem, tree analysis of sorting algorithms.
  • Network Algorithms. Shortest paths, network flows, algorithmic matching.

    • Textbook

    Alan Tucker, Applied Combinatorics, Fourth Edition, John Wiley & Sons, 2002.

    Resources

    Reinhard Diestel has made his excellent graph theory textbook freely available. You can download it in hyperlinked PDF format from this location. The book has been published by Springer-Verlag in its prestigious series Graduate Texts in Mathematics. See also this link.

    Evaluation

    There will be four problem sets. The students will have two weeks to work on each set. Each problem set will be worth 25% of the grade.

    Schedule

    For an outline of the material covered each day of the academic semester, click here.

    How to contact the instructor

    Office: SB 4.01.34 (Directions: Go to the fourth floor of the Science Building and as you get off the elevator follow the arrows to the Applied Mathematics Department. My office is right across the hall from the main office.)

    Telephone: (210) 458-5531

    Email: iovino@math.utsa.edu

    Office hours: M,W 10:11:30 am, or by appointment.

    Valid HTML 4.0!