Announcements
Final exam solutions
Here are my final exam solutions
- In pdf: final_exam_answers.pdf
- For latex and pictures, see the directory final
Also, you'll probably want to see the notebooks that accompany my solutions FinalSolution1.nb and FinalSolution3.nb
Have a great Summer and best wishes for your future success!
Class notes and Final Exam
Here are the class notes from May 12. I revised them yesterday:
Also, to provide some clarity on the Final Exam, I collected the problems into one document. The first problem is the problem I already distributed. I added a second problem consisting of short true/false statements about matrices associated to graphs. I added a third problem, a bonus problem, asking you to generalize the discussion in class on Thursday May 12 to include variable conductance. I offered some options here, depending on your skills / appetite for programming. Be advised, I simplified the weighted graph when I revised the class notes. The final exam is due in my mailbox on Tuesday, May 24.
- In pdf: final_exam.pdf
- In latex: final_exam.tex and the pictures Electrical_Circuit.pdf and WeightedGraph.pdf
Work on this over the weekend and bring any questions to class on Tuesday. Class will be in the regular classroom, Kiely 334.
As for final course grades, the baseline is a C. Solve problems 1 and 2 for a B. The bonus problem, midterm, and participation (online and in class) will be used to raise grades further.
Final exam problem 1
Here's the first Final Exam problem
- In pdf: final_problem1.pdf
- In latex: final_problem1.tex and the picture Electrical_Circuit.pdf
Also, for homework this weekend read section IX.1 in the book.
Notes and notebooks from last class
Last Thursday, we looked at the adjacency matrices for a few simple graphs, and then at Google's page rank algorithm. You will find the Mathematica notebooks that I used here:
Queens college has a site license for Mathematica. There's a good post on the forum about how to do download and install it. I encourage you do install Mathematica and play around with it's graph theory functions this week. You can start by working through the notebooks I used on Thursday. I also I recommend the first few screencasts in Hands-on Start to Mathematica and the following screencasts from Wolfram's learning center:
See if you can list the 32 Euler circuits in the graph on the midterm exam, or write a program to list the spanning trees directed toward a particular vertex.
More about the adjacency matrix and its eigenvectors
Check out Google's pagerank:
Also, analyze the eigenvalues of the adjacency matrices for K3 and K3 minus an edge.
Remember, Thursday's class will meet in Kiely 061.
Midterm exam and homework problems
Here's the midterm exam
- In pdf: midterm.pdf
- In latex: midterm.tex
and my solutions
- In pdf: midterm_answers.pdf
- In latex: midterm_answers.tex
Over the weekend, study section VIII.2 in the book, through Theorem 6. This section is about Eigenvalues of the adjacency matrix. I'll discuss this in Tuesday's class. If you're interested, try to find the 32 Euler circuits in the graph on the exam.
Midterm exam material
We'll have a midterm exam in class on Thursday, April 7. It will cover:
- Fundamentals: Sections I.1, I.2, I.3, I.4 in the book.
- Links in spatial embeddings, graph minors: Lecture on March 22, 24 which provided background and covered the first few pages of Conway and Gordon's article Knots and links in spatial graphs,.
- Vector spaces and matrices associated to graphs: Section II.3 in the book, especially Theorem 9, 10, and Corollary 13.
Vector spaces and matrices associated with graphs
In class yesterday I discussed Theorem 9 in Section II.3 of the book and next class I'll begin with Theorem 10. Please read through section II.3 of the text studying the definitions in II.3, up to including the Theorems 9 and 10 (pages 52, 53, 54). If you have time, skim through section II.1 on electrical networks also.
- Throughout your studying, keep the following problems in mind: exercises 37, 38, 39, 41 on page 64
Midterm exam and homework problems
We'll have a midterm exam in class on Thursday, April 7. Also, I wrote some homework problems
Links and knots in graphs
Today, I'll prove the BEST Theorem counting Euler circuits in a directed multi-graph. Next week, we'll take up some topological questions about graphs. First, we'll prove Kuratowski's theorem characterizing planar graphs. Then, I'd like to discuss knots and links in graphs. To prepare, read section I.4 in the text and begin to study the article by that title by John Conway and Cameron McA. Gordon. Here's the reference:
Knots and links in spatial graphs, J. H. Conway and C. McA. Gordon, Journal of Graph Theory Volume 7, Issue 4, pages 445–453, Winter 1983.
Homework
Read section I.2 in the book. To guide your studied reading of these sections, solve the following problems from the exercises (section I.6)
- 5, 6, 7, 9, 17, 20, 22, 31, 34, 38, 44
This week, write up complete solutions to problems 6, 9, 17, 31.
Thursday's class
As a reminder, there will be no class on Tuesday, February 9. The next class is Thursday, February 11.
On Thursday, I'll prove theorem 2. Then, I'll ask for student volunteers to come to the board and
- Solve exercise 2i and 2ii
- Define a connected graph
- Solve exercise 1
- Define a bipartite graph
- Solve exercise 3
- Solve exercise 4
Homework for the first day of class
Before the first day of class, I encourage you to read section I.1 in the book and do exercise 1, 3, and 4 on page 28.
I will invite you to put solutions to these problems on the board on the first day of class, that's Tuesday, February 2 (Groundhog day!)
Information about Piazza
The math 634 discussion forum is hosted on Piazza. I encourage you to post questions and answers about the course on the Q&A page of the forum. The link to the forum is piazza.com/qc.cuny/spring2016/math634/home.
Welcome to Graph Theory
This page will contain announcements about the course. For now, take a look at the syllabus, which has practical information such as references, office hours, and a calendar.