## S-72.2420 / T-79.5203 Graph Theory (5 cr) P## Spring 2007
[Current]
[General Information]
[Lectures]
[Tutorials]
[TOPI]
[Spring 2006]
Graph theory is arguably one of the most studied topics in contemporary discrete mathematics, and its theoretical and applied importance is constantly growing. Graph-theoretic problems are encountered in diverse applications such as bioinformatics and decoding algorithms in telecommunications --- not to mention the more traditional applications such as routing, flow problems, and project scheduling. Although sporadic graph-theoretic concepts and results are encountered also in other courses taught here at TKK, the aim of this course is to provide a more in-depth introduction to graph theory. The course is divided into two parts, theory and algorithms. The theory part covers basic types of graphs and central graph theoretic concepts such as distance, symmetry, coloring, connectivity, planarity, and so forth. A further goal is to learn logical reasoning together with tools and proof techniques commonly applied in discrete mathematics. The algorithm part reviews some of the central graph algorithms/problems such as depth- and breadth-first search together with their numerous applications, shortest path, minimum spanning tree, maximum matching, maximum flow, and so forth. Here one central aim is to understand the connection between a mathematical result and the algorithm that exploits it. Associated with the algorithm part is a programming project. The course is organized jointly by the Communications Laboratory at the Department of Electrical and Communications Engineering and the Laboratory for Theoretical Computer Science at the Department of Computer Science and Engineering. The course is also recommended to mathematically oriented students from other departments. Please note that although all the course material is in English, the lecturing language is Finnish. ## Current**June 6**- Results of the May 15 exam are available.
**May 16**- Deadline for feedback.
**May 15**- Exam (13-16, hall T1).
Please register via Topi
(course T-79.5203).
Please note that this is an OPEN BOOK exam---you are allowed to bring with you to the exam printed and/or handwritten material at your digression. In addition, a simple function calculator is permitted; however, any equipment with potential communications capabilities (e.g. a laptop computer or a mobile phone) remains strictly probihited. The next opportunity to take the exam will be in December. **May 7**- Deadline for peer review.
**April 27**- Project review for the programming project.
**March 19**- The first tutorial session. Extra exam points will be awarded for solving home assignments; see the tutorials page for details.
**March 16**- Registration deadline for the programming project.
**March 14**- The first lecture.
**January 3**- The lectures start on March 14. Registration is via Topi (course T-79.5203).
## General Information-
**Prerequisites:**Basic courses in mathematics and computer science. -
**Literature:**D. B. West,*Introduction to Graph Theory*, 2nd ed., Prentice Hall, Upper Saddle River NJ, 2001. D. Jungnickel,*Graphs, Networks and Algorithms*, 2nd ed., Springer, Berlin, 2005. -
**Electronic literature:**R. Diestel,*Graph Theory*, 3rd ed., Springer, Heidelberg, 2005. -
**Lectures:**Wednesdays 9-12, hall T4 (Konemiehentie 2) and Fridays 9-12, hall T4 (Konemiehentie 2). First lecture:**March 14**. -
**Teachers:**D.Sc.(Tech.) Petteri Kaski (contact information), Prof. Patric Östergård (contact information). -
**Tutorials:**Mondays 10-12, hall T4 (Konemiehentie 2) and Thursdays 10-12, hall T4 (Konemiehentie 2). First tutorial session:**March 19**. -
**Assistant:**M.Sc.(Tech.) Jori Dubrovin, room TB348 (Konemiehentie 2), tel. 451 6237, e-mail:`jdubrovi(at)tcs(dot)hut(dot)fi`. -
**Grading**: Exam (A) and programming project (B); A,B=0,1,2,3,4,5. Mark=0.6A+0.4B rounded to the nearest integer; both A and B must be nonzero to pass the course. Extra exam points will be awarded for solving home assignments. -
**Exams**: Dec 19, 2007, 16-19, halls M,L (Otakaari 1). May 15, 2007, 13-16, hall T1 (Konemiehentie 2). -
**Registration:**Registration is via Topi (course T-79.5203). -
**Newsgroup:**opinnot.tik.graafiteoria
## Lectures(Lecture slides are in PostScript format.)- March 14
- Practical arrangements, introduction
- March 16
- Basic concepts
- March 21
- Searching a graph, applications
- March 23
- Shortest paths and minimum spanning trees
- March 28
- Trees and distance; graph parameters
- March 30
- Matching in bipartite and general graphs
- April 4
- Flows and circulations
- April 6
*Easter holiday (no lecture)*- April 11
*Easter holiday (no lecture)*- April 13
- Connectivity; coloring
- April 18
- Matroids and the greedy algorithm
- April 20
- Planarity; edges and cycles; Ramsey theory; random graphs
- April 25
- Matroids (beyond the greedy algorithm)
- April 27
- Project review for the programming project
Also available are an English-Finnish-Swedish dictionary consisting of some central graph-theoretic terms, and a course brochure (in Finnish). ## TutorialsThe tutorial problems and solutions are available here.[TKT pääsivu] [Yhteystiedot] [Henkilöstö] [Tutkimus] [Julkaisut] [Ohjelmistot] [Opinnot] [Uutisarkisto] [Linkkejä] Päivitetty viimeksi 06.06.2007. |