SylabUZ

Wygeneruj PDF dla tej strony

Wprowadzenie do teorii grafów - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Wprowadzenie do teorii grafów
Kod przedmiotu 11.1-WK-IDP-WTG-W-S14_pNadGenV8WPI
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Inżynieria danych
Profil ogólnoakademicki
Rodzaj studiów pierwszego stopnia z tyt. inżyniera
Semestr rozpoczęcia semestr zimowy 2017/2018
Informacje o przedmiocie
Semestr 2
Liczba punktów ECTS do zdobycia 6
Typ przedmiotu obowiązkowy
Język nauczania polski
Sylabus opracował
  • dr hab. Ewa Drgas-Burchardt, prof. UZ
  • dr Anna Fiedorowicz
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Wykład 30 2 - - Egzamin
Ćwiczenia 30 2 - - Zaliczenie na ocenę

Cel przedmiotu

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

Wymagania wstępne

Podstawy logiki i algebry liniowej.

Zakres tematyczny

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.

Metody kształcenia

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

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu Symbole efektów Metody weryfikacji Forma zajęć

Warunki zaliczenia

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.

Literatura podstawowa

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.

Literatura uzupełniająca

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.

Uwagi


Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 09-04-2017 16:30)