Lecture :
Mondays, 08:15-10:00, SR AE06, Steyrergasse 30, ground floor
Wednesdays, 10:15-12:00, SR Analysis und Zahlentheorie, Kopernikusgasse 24, second floor (every second week)
Practical:
Wednesdays, 10:15-12:00, SR Analysis und Zahlentheorie, Kopernikusgasse 24, second floor (every second week)
This course deals with concepts from graph theory such as connectivity, trees and decompositions,
Hamiltonian cycles, planar graphs, graph coloring, perfect graphs, covering problems and random graphs.
Most of the topics will be discussed both from a theoretical and from an algorithmical point of view.
Chapters:
- Connectivity, trees and decompositions
- Hamiltonian cycles
- Planar graphs and plane duality
- Colouring problems
- Perfect graphs
- Covering problems
- Random graphs and randomized algorithms
The main sources of literature
- Bella Bollobas, Modern Graph Theory (Graduate Texts in Mathematics), corrected and extended edition, Springer, 2013.
- G. Chartrand, L. Lesniak, P. Zhang, Graphs & Digraphs (Textbooks in Mathematics), Taylor & Francis Inc, 6th revised edition, 2015.
- R. Diestel, Graph Theory (Graduate Texts in Mathematics), fourth edition, (second, corrected printing) Springer, 2012
- M.Ch.Golumbic, Algorithmic graph theory and perfect graphs, second edition, Elsevier Ltd, 2004
The practical assessment will be permanent and based on a score of points collected as follows
- by solving exercise examples independently; at most 3 points;
At the beginning of every practical class the participants have to declare which exercise examples they have solved and prepared for presentation.
At the end of the course they will be credited with the percentage of the exercise examples they have declared to have solved during the course multiplied by three -
by presenting the solution of exercise examples in the class;
The presentatation of an exercise example in the class will be credited with at most 4 points corresponding to the correctness and completeness of the solution as well as the quality of the presentation. - by participating at a written exam at the end of the course; at most 15 points. For a positive grade at the practical you should reach a minimum of 6 points (out of 15) at the written exam.
The written exam: The first possibility to take the writen exam will be at the end of the course, most probably on June 28, 15:00-17:00, in SR AE06 (TUGonline-Name STEG050).
Another possibility will be around the beginning of the next winter term.
The registration for the exam has to be done via TUGonline.
The points collected during the most recent try will count for the assessment .
The overall score is computed as follows
P= 3 * ((k)/(k_a)) + 12*(t) + 15 (p),
where
k is the number of exercise examples prepared all along the course,
k_a is the overall number of exercise examples which have been available during the course,
t is the overall sum of points obtained by presenting exercise examples in the class (scaled between 0 and 1)
p is the score of the written exam (scaled between 0 und 1),
Grade obtained for the practical according to the overall score:
5 0 <= P < 15
4 15 <= P <= 18
3 18 < P <= 22
2 22 < P <=26
1 26< P
The lecture will be assessed by an oral examination.
The dates for the oral exams will be specified in agreements with the students.
- General definitions and notations
- Recall some very basic results on maximum flows and minimum cuts in networks (slides)
For proofs and further results in these topics I refer to Chapter 8 in
Bernhard Korte and Jens Vygen, Combinatorial Optimization : Theory and algorithms, Springer, 2012,
eltronically available in TUG campus. - General results on connectivity, 2-connectivity and 3-connectivity
- Computing the connectivity-number, the edge connectivity number, checking for 2-connectivity and 3-connectivity
- Hamitonicity of graphs, sufficient conditions, necessary conditions
- Hamitonicity of graphs, sufficient conditions, longs cycles in graphs, degree sequences
(The current work sheet will be published here at least one week before the next practical unit.)
- First worksheet (to be discussed on Wednesday, March 20)
cela@opt.math.tu-graz.ac.at.
Last update: March 2024