Graph Theory
serapgurer@gmail.com
Content
Objective
-This course aims to introduce the basic concepts, topics and results of Modern Graph Theory with a target of techniques that are applicable in especially social sciences.
Course Content
Basic graph theoretical concepts: paths and cycles, connectivity, trees, spanning subgraphs, bipartite graphs, Hamiltonian and Euler cycles.
Algorithms for shortest path and spanning trees.
Matching theory.
Planar graphs.
Colouring.
Flows in networks, the max-flow min-cut theorem.
Erdös-Rényi random graphs.
Szemerédi´s regularity lemma.
Infinite graphs.
Applications in computer science and social sciences.
Course Learning Outcomes
On completion of the course, the student should be able to:
1)know some important classes of graph theoretic problems;
2) formulate and prove central theorems about trees, matching, connectivity, colouring and planar graphs;
3) describe and apply some basic algorithms for graphs;
4) use graph theory as a modelling tool.
References
Graph theory, Diestel, Reinhard., 4th ed.: Heidelberg: Springer, 2010.
Graph Theory with Applications, Bondy.and Murty, North-Holland, 1979
Graph Based Natural Language Processing and Information Retrieval / Rada Mihalcea, Dragomir Radev, Cambridge University Press, 2011.
Discrete Mathematics, An Open Introduction, Oscar Levin, at
http://discretetext.oscarlevin.com/
Proof Techniques in Graph Theory, Harary, F. , Academic Press, New York, 1969.
New Directions in the Theory of Graphs, Harary, F., Academic Press, New York, 1973.
Weekly Contents
| Week | Weekly Contents |
|---|---|
| 1 | Fundamental Concepts of Graph Theory |
| 2 | Paths and cycles |
| 3 | Trees |
| 4 | Basics of matching theory |
| 5 | Algorithms for the shortest path |
| 6 | Algorithms for spanning trees |
| 7 | Midterm Exam |
| 8 | Planar Graphs and Coloring |
| 9 | Planar Graphs and Coloring |
| 10 | Large Graphs and Clustering |
| 11 | Large Graphs and Clustering |
| 12 | Presentations of projets |
| 13 | Applied Graph Theory and Modeling |
| 14 | Applied Graph Theory and Modeling |
Assessment System
| Activities | Number | Contribution |
|---|---|---|
| Contribution of in-term studies to overall grade | 3 | 60 |
| Contribution of final exam to overall grade | 1 | 40 |
| Total | 4 | 100 |
| Activities | Number | Contribution |
|---|---|---|
| Assignments | 0 | 0 |
| Presentation | 1 | 10 |
| Midterm Examinations (including preparation) | 1 | 30 |
| Project | 1 | 20 |
| Laboratory | 0 | 0 |
| Other Applications | 0 | 0 |
| Quiz | 0 | 0 |
| Term Paper/ Project | 0 | 0 |
| Portfolio Study | 0 | 0 |
| Reports | 0 | 0 |
| Learning Diary | 0 | 0 |
| Thesis/ Project | 0 | 0 |
| Seminar | 0 | 0 |
| Other | 0 | 0 |
| Total | 3 | 60 |
Relation of Proficiency
| No | Program Learning Outcomes | Contribution | ||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | understands principles of deductive reasoning; has experience to verify well-foundedness and exactness of mathematical statements in systematic ways; | X | ||||
| 2 | can properly state and use concepts and results of major mathematical interest; | X | ||||
| 3 | masters current computational techniques and algorithms; has a good ability in their use; can identify relevant tools, among those one has learned, suitable to solve a problem and is able to judge whether or not one is in possession of these tools; | X | ||||
| 4 | is able to express one’s mathematical ideas in an organised way both in written and oral forms; | X | ||||
| 5 | understands relations connecting substantial concepts and results; can switch from one viewpoint to another on mathematical objects (pictures, formulae, precise statements, heuristic trials, list of examples,...); | X | ||||
| 6 | has followed individually a guided learning strategy; has pursued steps toward the resolution of unfamiliar problems; | X | ||||
| 7 | has a theoretical and practical knowledge in computer science well adapted for learning a programming language; | X | ||||
| 8 | has investigated the relevance of modeling and using mathematical tools in natural sciences and in the professional life; is conscious about historical development of mathematical notions; | X | ||||
| 9 | has followed introduction to some mathematical or non-mathematical disciplines after one’s proper choice; had experience to learn selected subjects according to one’s proper arrangement; | X | ||||
| 10 | masters French language as well as other foreign languages, to a level sufficient to study or work abroad. | X | ||||
ECTS
| Activities | Number | Period | Total Workload |
|---|---|---|---|
| Class Hours | 14 | 3 | 42 |
| Working Hours out of Class | 14 | 2 | 28 |
| Assignments | 6 | 4 | 24 |
| Presentation | 1 | 1 | 1 |
| Midterm Examinations (including preparation) | 1 | 8 | 8 |
| Project | 1 | 8 | 8 |
| Laboratory | 0 | 0 | 0 |
| Other Applications | 0 | 0 | 0 |
| Final Examinations (including preparation) | 1 | 12 | 12 |
| Quiz | 0 | 0 | 0 |
| Term Paper/ Project | 0 | 0 | 0 |
| Portfolio Study | 0 | 0 | 0 |
| Reports | 0 | 0 | 0 |
| Learning Diary | 0 | 0 | 0 |
| Thesis/ Project | 0 | 0 | 0 |
| Seminar | 0 | 0 | 0 |
| Other | 0 | 0 | 0 |
| Total Workload | 123 | ||
| Total Workload / 25 | 4.92 | ||
| Credits ECTS | 5 | ||