Instructor: Dr. Kathryn Fraughnaugh (rhymes with "fauna" as in "flora and fauna")
Office: 603 CU Denver Bldg (at the corner of 14th and Lawrence - main entrance on 14th)
Telephone: 556-8461
Email: kfraughn@math.cudenver.edu
Office Hours: Tues 11:30 - 12:15; Thurs 2:00 - 3:00
Other times by appointment.
Prerequisites: Math 3000 - Introduction to Abstract Mathematics or CSC 3614 - Discrete Math II or some experience in expressing mathematics in an abstract setting (theorem proving).
Text: Applied Combinatorics by Fred S. Roberts
Course content:
Chapter 1 (all but Example 1.1)Chapter 2 (Sections 2.1 thru 2.8, 2.18)
Chapter 3 (all but Section 3.6)
Chapters 11 thru 13 (all sections)
* Some topics not covered in the text will be discussed. The student is responsible for all material covered.
What is "Applied Graph Theory"?
Graphs are a basic model used in the solution of many real-world problems. They are particularly appropriate for solving problems involving communication or transportation networks, planning and scheduling, as well as many other optimization problems. They are an underlying model for computer implementations of these and many other problems. The study of applied graph theory does NOT mean the study of actual real-world applications. In general, a real-world problem contains many data points and requires a combination of techniques, techniques from several disciplines perhaps. Our study of graph theory will focus on those aspects of the model that can be applied, whether to components of real-world problems or to other mathematics theories. Thus our study will be primarily theoretical, with emphasis on discussing the areas to which it may be applied.
What will I get out of this course?/ What are our goals?
1) To familiarize you with the basic concepts of graph theory, some of the main areas in the field that have been studied extensively, some of the most powerful theoretical results, and the wide range of applications of the field.2) To improve your ability to express your mathematical ideas clearly and precisely. Included in this is the ability to construct and write a logical mathematical proof and to express yourself clearly when analyzing a problem or an algorithm.
Why are the objectives above important?
1) Graph theory is a basic model in mathematics and computer science. In mathematics, it underlies many problems in operations research, artificial intelligence, and other areas. In computer science, it is essential in the development of algorithms or the understanding of data structures. It has myriad applications in business and industry. It is part of the education of all well-rounded mathematicians and computer scientis ts, as well as professionals in other areas.
2) The ability to express oneself clearly, precisely, and logically is an essential skill in our society in general and especially in the mathematical sciences. Whether developing a technique for solving a problem or communicating to others the advantages of your solution, you need to be able to justify your reasoning, the correctness of your analysis, and the applicability of the techniques you are using.
Grading:
Exam 1 (Feb 24)* 100 pointsExam 2 (Apr 7)* 100 points
Exam 3 (May 12)* 100 points
Quizzes 100 points
*The dates for all exams are tentative.
The course grade will be determined from the average of the four components using the scale: A (90 - 100), B (80 - 89), etc. The final grades will be scaled when appropriate; plus/minus grades will be used. Exam 3 is the final exam and will be comprehensive.
The quiz grade will be based on weekly quizzes. These 10-minute quizzes will generally be given in class on Tuesday. A typical quiz will ask for definitions, statements of theorems, short answers to questions that test understanding, or short proofs. Each quiz will be worth 100 points. No make-up quizzes will be given. There will be 12 quizzes throughout the semester. The average of the highest ten grades is the quiz average.
Homework is a necessary part of any mathematics course. The homework exercises will not be graded (though they may appear on weekly quizzes). It is strongly encouraged that you form study groups for doing homework and discussing the material. Doing the exercises suggested in the text should be considered a minimal effort. In addition, you should read the text giving careful attention to all definitions, proofs and examples. Supplementary exercises will be provided for material not in the text.
How can I be assured of a good grade?
1) Attend and participate actively in all classes.
2) Take all quizzes if possible. Never skip a quiz because you think you would not do well on it. (You may surprise yourself! Later you may have to miss a quiz and a few points now are better than no points. The quizzes are good reviews of the material.)
3) Do as many homework exercises as you can, even the ones that I have not assigned. Pay special attention to those involving proofs.
4) Read the textbook carefully.
5) Read the textbook carefully.
6) Keep up with the pace of the class.
7) EMAIL ME OR COME SEE ME FOR HELP OUTSIDE OF CLASS.
Note: You should expect to spend 6-9 hours per week outside of class.
Note: As in most college courses, some memorization is necessary. For our class, this will be particularly intense at the beginning of the semester when you are learning new terms and definitions. However, memorization alone will NOT earn a good grade. If you are not confident about your "theorem proving" skills, make this semester an opportunity to change that. Keep trying. You WILL improve. The ability to express oneself precisely is an essential skill for an educated person, especially a person in the mathematical sciences. This semester you will have the opportunity to sharpen these skills.
Suggested exercises from the text.
Chapt 1: 5-10,11-13 (do only for table 1.10)
Chapt 2: (2.1) 1,3,5,7 (2.2) 1,3,5,7 (2.3) 1,3,5,7 (2.4) 1,2,3,6,7
(2.5) 1,3,5 (2.6) 1,3,5 (2.7) 1,3,7,9,11,13,15 (2.8) 1,2,4
Chapt 3: (3.1) 1,3,7,10,11,12,15-21 (3.2) 1-11,13,15,16,31
(3.3) 1-4,7,9,10,12,13,16,17-21,26,33 (3.4) 1-5,8,9,11,13,15,17-19 (3.5) 1-8,10,11,12,15,17,19-21,26,27 (3.7) 1-15,28
Chapt 11: (11.1) all (11.2) 1-4,8-11,13,14 (11.3) 1-10,17-20
(11.4) 1-3,7-10 (11.5) 1-17 (11.6) 1-5,8,9,17-19,22
Chapt 12: (12.1) 1-6 (12.2) 1-3,9-11,13-15 (12.3) 1-4
(12.4) 1-3,6-10 (12.5) 1,3,5,6 (12.6) 1,3
Chapt 13: (13.1) 1,2,5,7,8,14,15 (13.2) 3,5,9,10 (13.3) 1-4,6,8-11,16,17,20,22 (13.4) 1,3,4,6