1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2021/2022
4. Data Engineering - First-cycle studies leading to Engineer's degree
5. Introduction to Graph Theory

Generate PDF for this page

Introduction to Graph Theory - course description

Aim of the course

Poznanie podstawowych pojęć teorii grafów w aspekcie teoretycznym i algorytmicznym.

Prerequisites

Save changes

Podstawy logiki i algebry liniowej.

Scope

Wykład/ćwiczenia:

1. Definicja grafu. Podstawowe pojęcia i klasy grafów. Izomorfizm grafów.
2. Reprezentacje grafów.
3. Drogi, marszruty i cykle w grafach. Spójność grafów.
4. Grafy eulerowskie i hamiltonowskie.
5. Drzewa i ich własności. Drzewa binarne. Drzewa rozpinające. Algorytmy przeszukiwania grafów. Zliczanie drzew.
6. k-spójność grafów.
7. Digrafy, definicja i podstawowe pojęcia. Digrafy eulerowskie. Turnieje.
8. Grafy planarne. Twierdzenie Eulera o grafach płaskich. Twierdzenie Kuratowskiego. Dualność.
9. Pokrycia, niezależność i dominowanie.
10. Kolorowanie grafów. Liczba chromatyczna i indeks chromatyczny. Kolorowanie map.
11. Systemy różnych reprezentantów i twierdzenie Halla. Zastosowania twierdzenia Halla.

Teaching methods

Tradycyjny wykład; ćwiczenia audytoryjne, podczas których studenci rozwiązują zadania.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Na ocenę z ćwiczeń składają się wyniki osiągnięte na kolokwiach (z zadaniami o zróżnicowanym stopniu trudności). Ocena z wykładu – na podstawie egzaminu pisemnego. Na ocenę z przedmiotu składa się ocena z ćwiczeń (50%) oraz ocena z wykładu (50%). Warunkiem przystąpienia do egzaminu jest uzyskanie pozytywnej oceny z ćwiczeń. Warunkiem zaliczenia przedmiotu jest pozytywna ocena z ćwiczeń i egzaminu.

Recommended reading

1.      R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa, 1998.

2.      V. Bryant, Aspekty kombinatoryki, WNT, Warszawa, 1997.

3.      W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.

4.      K.A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.

Further reading

1.      D.B. West, Introduction to Graph Theory, Prentice Hall, 2001.

2.      N. Deo,  Teoria grafów i jej zastosowania w technice i informatyce, PWN, Warszawa, 1980.

3.      J.M. Aldous, R.J. Wilson, Graphs and Applications, Springer, 2000.

Notes

Modified by dr Alina Szelecka (last modification: 05-05-2021 13:03)