Discrete Structures - Math 447 - TR 2:00-3:15 
Fall 2000

A combinatorial 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.

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. Homework will be assigned each time we begin to cover a new section in class. You should complete it by the next class period. I will ask you to hand in selected problems every week or so. These 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.

Your grade will be based on your test scores, final exam score and homework grades. The scores are averaged and then weighted to compute your final grade according to the following percentages.

homework	25%
2 tests	40%
final	35%

Do the following homework from each section as we cover the section. Each week, I will select problems for you to hand in the following week.

* - Extra credit:  Is the graph in figure 2.2.2 on page 32 really a snark.  Back up you answer.
 

SECTION	HOMEWORK	HAND IN due date
1.1	1-5,8-11	3,11  Sept 14
1.2	1-5,7-10	1,4,9  Sept 28
1.3	1,2,4,7,8,9,13,15,19,20	7,15,19,20  Oct 5
2.1	1,2,4,5,6,7,9,10,11,23	9,10,23  (1 extra credit problem*) Oct 12
2.2	1-3,6,7,9-12	6,10  Oct 17
2.3	1,5-9,13,15,17-19,21,22	work on in class
2.4	2,3,10,11,15,24(as modified in class)	3,10,24 Oct 23
	EXAM 1	Oct 26
	Research Assignment	Nov 2  (latest Nov 21)
3.1	1,3,5,6,11,14,16	6,11,16 Nov 9
	Algorithm	Nov 9
3.2	1,2,3,6	1,2,3,6 Nov 21
3.3	3,4,6,10,13,14,17	work on in class
4.1	1-5	on board Nov 21
	EXAM 2	Nov 28
4.2	2,3,4,6	on board Nov 30
4.3	1,2,3,5	1,2,3,5 Nov 30
5.1	1-7	on board Dec 5
8.1	5,6,8,11	Hand in Dec 7
8.3	2,3	Hand in Dec 7
7.1
7.2
7.3

 

1. Read the Book carefully. I chose this book because I believe it gives nice explanations of things. It may be helpful to read sections before we talk about them in class.
2. Do all of the homework assigned. You should spend an average of 6 hours a week on homework for this class. If you don't gain experience in doing the problems yourself, it will be hard to remember how to do them on a test. It is helpful to start study groups and work together on homework. I do believe that how well you do in this course will depend on how well you study.
3. Attend class to keep current, ask questions, and learn knew topics. Also, attending class allows you to see what is emphasized. Remember the material for the tests will come from what was emphasized.
4. Be sure to keep current of all topics. You will need to study a little almost everyday. If you don't understand something, don't let it wait too long because the concepts in this class build, one upon the next. You don't want the ``snowball effect'' to take over.
5. You may not understand an idea at first. Give it time to sink in. Sometimes you must go over it several times before it begins to make sense. It is not unusual for someone to be stuck on a particular kind of problem and not understand it in class. You may need to have it explained again, later. Please feel free to ask me to do so outside of class.
6. Notecards - I suggest you buy a spiral bound set of notecards. I will explain how to use these in class, but basically, you record simple statements, one per card, giving key definitions and theorems. Then you can use these as a flashcard type of studying method.