DM 2010
Discrete Mathematics
List of Theorems (with proofs) on the exam:
- Euler Theorem bout Euler tour
- Ore Theorem
- About quality of ATSP algorithm
- Characterization of bipartite graphs (without odd cycles)
- Euler formula
- 5-colour Theorem
- Hall Theorem
DM0 - Induction
DM1 - Counting
DM2 - More Counting, Partitions
DM3 - Inclusion-exclusion principle
DM4 - Generating functions
DM5 - Notation O()
DM6 - Codes
DM7 - Graphs
DM8 - Euler tours, Hamiltonian cycles
DM9 - Graph coloring
DM10 - Planar graphs
Previous tests
test 1: 2006|2006a|2007 | 2008|2010
test 3: 2005|2006|2007|2008|2009|
test 4: 2005|2006|2007|2008|2009|
2) W. Lipski, Kombinatoryka dla programistów, Warszawa, WNT 2004.3) W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, 1986.
4)F. Roberts, Applied Combinatorics, Prentice Hall, 1984.
5) K. A. Ross, C.R.B.Wright, Matematyka Dyskretna, PWN 1999.
6) R.J. Wilson, Introduction to Graph Theory, Addison Wesley, 1996.
7) R. Diestel, Graph Theory, Springer-Verlag 1997,2000,2005
http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.pdf 8) http://users.utu.fi/harju/graphtheory/graphtheory.html
Two midterm tests each for 16 points, 8 points for activity on exercises. Mark 3.0 for 20-23,5 points, 3.5 for 24-27,5 p, 4.0 for 28-31,5 p, 4.5 for 32-35,5 p, 5.0 for 36-40 p. Presence on exercises is obligatory, maximum two unexplained absences.