|
|
Main menu for Browse IS/STAG
Course info
KMA / UTG
:
Course description
Department/Unit / Abbreviation
|
KMA
/
UTG
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Fundamentals of Graph Theory
|
Form of course completion
|
Exam
|
Form of course completion
|
Exam
|
Accredited / Credits
|
Yes,
5
Cred.
|
Type of completion
|
Combined
|
Type of completion
|
Combined
|
Time requirements
|
Lecture
3
[Hours/Week]
Tutorial
1
[Hours/Week]
|
Course credit prior to examination
|
Yes
|
Course credit prior to examination
|
Yes
|
Automatic acceptance of credit before examination
|
No
|
Included in study average
|
YES
|
Language of instruction
|
Czech
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
No
|
Summer semester
|
0 / -
|
0 / -
|
0 / -
|
Included in study average
|
YES
|
Winter semester
|
12 / -
|
0 / -
|
0 / -
|
Repeated registration
|
NO
|
Repeated registration
|
NO
|
Timetable
|
Yes
|
Semester taught
|
Winter semester
|
Semester taught
|
Winter semester
|
Minimum (B + C) students
|
1
|
Optional course |
Yes
|
Optional course
|
Yes
|
Language of instruction
|
Czech
|
Internship duration
|
0
|
No. of hours of on-premise lessons |
|
Evaluation scale |
1|2|3|4 |
Periodicity |
každý rok
|
Evaluation scale for credit before examination |
S|N |
Periodicita upřesnění |
|
Fundamental theoretical course |
No
|
Fundamental course |
No
|
Fundamental theoretical course |
No
|
Evaluation scale |
1|2|3|4 |
Evaluation scale for credit before examination |
S|N |
Substituted course
|
None
|
Preclusive courses
|
N/A
|
Prerequisite courses
|
N/A
|
Informally recommended courses
|
N/A
|
Courses depending on this Course
|
N/A
|
Histogram of students' grades over the years:
Graphic PNG
,
XLS
|
Course objectives:
|
The course aims at introducing the students to some parts of graph theory and their applications. The key topics will be cyclic properties of graphs, k-connectivity of graphs, vector spaces of cycles and edge cuts, introduction to Ramsey theory and spectral theory of graphs.
|
Requirements on student
|
Evaluation of exam:
The exam has a written part an oral part and is focused on verification and understanding of knowledge of refered topics including the ideas of proofs.
|
Content
|
1st week - basic definitions and notations of graph theory, bridges and cut vertices
2nd week - k-connectivity of graphs (Menger's theorem), cyclic properties of graphs and applications,
3rd-4th week - hamiltonian graphs - necessary and satisfactory conditions,
5th week - hamiltonian properties in powers of graphs,
6th week - vector spaces of cycles and edge cuts,
7th week - eigenvalues of graphs and spectrum of graphs,
8th week - vertex colouring of graphs, Brook's theorem,
9th week - edge colouring of graphs, Vizing's theorem,
10th week - introduction to Ramsey theory,
11th-12th - introduction to the theory of flows and linear optimization, basic simplex algorithm
|
Activities
|
|
Fields of study
|
|
Guarantors and lecturers
|
|
Literature
|
-
Recommended:
Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 80-7082-939-7.
-
Recommended:
Demel, Jiří. Grafy a jejich aplikace. 1. vyd. Praha : Academia, 2002. ISBN 80-200-0990-6.
-
Recommended:
Diestel, Reinhard. Graph theory. 3rd ed. Berlin : Springer, 2006. ISBN 3-540-26183-4.
-
Recommended:
Gross, Jonathan; Yellen, Jay. Graph theory and its applications. Boca Raton : CRC Press, 1999. ISBN 0-8493-3982-0.
-
On-line library catalogues
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Contact hours
|
52
|
Preparation for an examination (30-60)
|
52
|
Preparation for comprehensive test (10-40)
|
26
|
Total
|
130
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
Knowledge of basic definitions and notations of graph theory in a range of the course KMA/DMA is assumed. |
formulate basic notions and knowledge of the graph theory, mainly undirected
|
formulate basic algorithms from the filed of unweighted and weighted graphs |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
define basic notions of the graph theory, mainly undirected |
apply basic proof techniques in the graph theory |
use basic matrix calculus in the graph theory |
Competences - students are expected to possess the following competences before the course commences to finish it successfully: |
N/A |
N/A |
N/A |
|
Learning outcomes
|
Knowledge - knowledge resulting from the course: |
knowledge of basic notions and theorems of hamiltonian properties of graphs |
basic knowledge from the field of vertex and edge colouring - Brook's theorem and Heawood's theorem (vertex), Konig's theorem and Vizing's theorem (edge) |
basic knowledge of the Ramsey theory - formulate problem, Ramsey theorem |
spectral theory of graphs - basic definitions and knowledge, spectra of basic graph classes |
formulate linear programming problem, formulate basic variant of the Simplex algorithm |
Skills - skills resulting from the course: |
formulate hamiltonian properties |
formulate basic knowledge from the field of vertex and edge colourings of graphs |
knowledge of the basics of the Ramsey theory and spectral theory of graphs |
use of simplex algorithm in the linear programming |
Competences - competences resulting from the course: |
N/A |
N/A |
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Combined exam |
Written exam |
Oral exam |
definitions of notions in a range of the subject KMA/UTG, namely hamiltonian properties of graphs, vertex and edge colourings, Ramsey theory, spectral graph theory and basics of linear programming |
Skills - skills achieved by taking this course are verified by the following means: |
Oral exam |
Written exam |
Combined exam |
definitions of notions in a range of the subject KMA/UTG
ability to formulate mathematical theorems including sketches of proofs
ability to solve simple types of problems using simplex algorithm |
Competences - competence achieved by taking this course are verified by the following means: |
Oral exam |
Written exam |
Combined exam |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Interactive lecture |
Task-based study method |
Self-study of literature |
Skills - the following training methods are used to achieve the required skills: |
Interactive lecture |
Individual study |
Task-based study method |
Competences - the following training methods are used to achieve the required competences: |
Interactive lecture |
Task-based study method |
Self-study of literature |
Individual study |
|
|
|
|