# MTH447 Discrete Mathematical Structures

### Fall 2003

Instructor: Lubos Thoma
Office: Tyler Hall 214
Tel: 874.4451
Email: thoma@math.uri.edu

Class Schedule: TR 2pm--3.15pm, Wales 224

Office hours: TR 12.10 - 1.00 pm, W 2.00 - 3.00 pm, and by appointment

Printable syllabus:   postscript     pdf

Textbook:   F. Buckley, M. Lewinter, A friendly introduction to graph theory, Prentice Hall.

Description:   A graph G = (V,E) is a set of vertices V and edges E, each edge consisting of unordered pairs of vertices. We picture graphs with dots for vertices in any desired arrangement and lines for edges, connected pairs of vertices in that edge. Graph theory has many applications in Electrical Engineering and Computer Science. For example, the electrical engineer will be interested in planar graphs and the computer scientist in algorithms to properly color graphs. We will see some of these applications, but we must build up some background knowledge about graphs before we can make sense of such things as the rigidity of a graph or the crossing number of a graph.

In the course of our study of Graph Theory, we will learn about the following topics as well: set theory, proof techniques, enumeration, and recursive formulas. There is no official prerequisite for this course however, it is recommended that you have been exposed to a variety of math and science courses. All topics will be treated in an introductory manner.

Exams:   Exams will draw from material covered in class, that is, any theorems, proofs, example, or homework problem that we actually discuss in class is possible material for the tests. So, the best way to prepare for the exams will be to start with your class notes. There will be two in-class exams and a comprehensive final. The in-class exams will be given on Tuesday October 7 and Thursday November 13, and the final will be on December 16, 8.00 -- 11.00am.

Homework:   You learn more by doing, than by watching others give demonstrations. Therefore, homework is very important. When you sit down to do your homework is when you realize whether or not you understood the material from class. You also learn by practice, so do as many of the examples assigned as possible. I will assign homework on a regular basis. Your solutions should be written up with your best effort at explanation and should be neat. These problems will challenge your problem solving abilities. You may work in groups provided you follow the following guidelines: each person must write up each problem in their own words, no copying. Whenever you would like to discuss the class material, have any questions or are stuck on the homework, please visit me in my office either during my office hours or by appointment.

Project:   The purpose of the project is that you learn to work with literature and other sources of information. The possible topics will be posted shortly. You will be able to choose from describing a problem or result in graph theory, describing an application of graph theory in your field, or a program for a graph theoretical problem. Of course, if you have a topic in mind on your own that will be very welcome.
You can work alone or in small groups (up to three people). A goal will be to write a short survey paper or create a program concerning the chosen topic.
Draft version due: November 10; final version due December 4.