2 Course Content
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.
4 Homework and Office Hours
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.
6 Sections covered and Homework
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|
|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|