Exam Information
(Graph Theory)
The Exam (Fri Mar 14, in class, PHSC 116)
This exam will cover material discussed in lecture, lab
and homework through Wed Mar 12, primarily Chapter 1.
Expect some True/False
questions, short answer questions, calculations, Python
questions and simple proof problems. In particular, you
should be able to do the following
- Go between graph drawings and adjacency matrices
- Write code in Python to accomplish simple tasks
- Determine what simple Python code does
- Analyze the runtime of basic algorithms
- Determine if two graphs are isomorphic
- Draw some or all graphs with certain properties
(e.g., all trees on 4 vertices, up to isomorphism)
- Determine if a graph with certain properties
exists or not (e.g., suppose G has 10 nodes and
20 edges---can G be 2-connected? 5-connected? disconnected?)
- Determine connected components and strongly connected
components.
- Compute distances and diameters
- Compute vertex/edge connectivities; find vertex/edge
cuts.
- Reproduce Euler's Konigsberg bridge solution
- Know what a Hamiltonian cycle is and solve simple TSPs
- Do simple proofs
- Determine planarity/chromatic number
- Know what the four-color theorem says
Advice: I recommend you study for this exam by,
reviewing the defintions, lemmas, propositions and
theorems in the notes. Then
make sure you can do all the exercises in the notes
(including those not assigned) and the lab problems, with
the exception of the more complicated/computational
computer problems.
Course Home