Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Teoria grafów
Tok studiów:
2019/2020
Kod:
AMAT-2-201-MI-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka w informatyce
Kierunek:
Matematyka
Semestr:
2
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
dr hab, prof. AGH Kalinowski Rafał (kalinows@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Podstawowe pojęcia i twierdzenia teorii grafów (spójność, problemy hamiltonowskie, planarność, kolorowania, rozkłady grafów). Przykłady modelowania matematycznego wykorzystującego teorię grafów.

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 zna najważniejsze fakty z historii teorii grafów oraz wybrane nierozstrzygnięte hipotezy MAT2A_W06, MAT2A_W03, MAT2A_K05 Egzamin
M_W002 zna podstawowe pojęcia i twierdzenia teorii grafów (spójność, problemy hamiltonowskie, planarność, kolorowania, rozkłady grafów) MAT2A_W02, MAT2A_W04, MAT2A_U13, MAT2A_U02, MAT2A_W05 Odpowiedź ustna,
Kolokwium,
Egzamin,
Aktywność na zajęciach
M_W003 zna przykłady modelowania matematycznego wykorzystującego teorię grafów MAT2A_U14, MAT2A_U04, MAT2A_K05, MAT2A_W07 Odpowiedź ustna,
Kolokwium,
Egzamin,
Aktywność na zajęciach
Umiejętności: potrafi
M_U001 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę z teorii grafów MAT2A_U21, MAT2A_U14, MAT2A_U01, MAT2A_W02, MAT2A_K02, MAT2A_U13, MAT2A_U02, MAT2A_U03, MAT2A_K01 Odpowiedź ustna,
Kolokwium,
Egzamin,
Aktywność na zajęciach
M_U002 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń MAT2A_W02, MAT2A_W04, MAT2A_U13, MAT2A_U02, MAT2A_U03, MAT2A_W05 Odpowiedź ustna,
Kolokwium,
Egzamin,
Aktywność na zajęciach
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (algebra, topologia, matematyka dyskretna) w teorii grafów MAT2A_U21, MAT2A_U14, MAT2A_U04, MAT2A_W07, MAT2A_U16, MAT2A_U08 Odpowiedź ustna,
Kolokwium,
Egzamin,
Aktywność na zajęciach
Kompetencje społeczne: jest gotów do
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania MAT2A_K07, MAT2A_K02, MAT2A_K01 Odpowiedź ustna,
Kolokwium,
Egzamin,
Aktywność na zajęciach
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
M_W001 zna najważniejsze fakty z historii teorii grafów oraz wybrane nierozstrzygnięte hipotezy + + - - - - - - - - -
M_W002 zna podstawowe pojęcia i twierdzenia teorii grafów (spójność, problemy hamiltonowskie, planarność, kolorowania, rozkłady grafów) + + - - - - - - - - -
M_W003 zna przykłady modelowania matematycznego wykorzystującego teorię grafów + + - - - - - - - - -
Umiejętności
M_U001 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę z teorii grafów + + - - - - - - - - -
M_U002 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń + + - - - - - - - - -
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (algebra, topologia, matematyka dyskretna) w teorii grafów + + - - - - - - - - -
Kompetencje społeczne
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania + + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 152 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 40 godz
Samodzielne studiowanie tematyki zajęć 50 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (30h):

1.Usystematyzowanie i poszerzenie podstawowych pojęć i notacji teorii grafów, w tym grafy zwykłe, digrafy, multigrafy; podgrafy; spacery, ścieżki, cykle. Izomorfizm grafów; grupa automorfizmów grafu.

2. Hipoteza rekonstrukcyjna Ulama. Spójność grafu. Twierdzenie Mengera (szczególne).

3. Ogólne twierdzenie Mengera. Spójność krawędziowa grafu. Graf krawędziowy.

4. Obchód Eulera i droga Eulera. Charakteryzacja multigrafów eulerowskich i jednobieżnych. Algorytm Fleury’ego. Problem chińskiego listonosza.

5. Cykl i ścieżka Hamiltona. Domknięcie Bondy’ego-Chvátala grafu. Stabilność własności grafów.

6. Warunki wystarczające istnienia cyklu Hamiltona: Bondy’ego-Chvátala, Orego, Diraca, Chvátala-Erdősa i Fana.

7. Inne własności typu hamiltonowskiego: trasowalność, pancykliczność. Problem komiwojażera.

8. Rozkład grafu na izomorficzne podgrafy. Rozkład grafu pełnego na cykle Hamiltona i na skojarzenia.

9. Liczba chromatyczna grafu. Wielomian chromatyczny grafu. Rozkład wielomianu chromatycznego.

10. Twierdzenie Brooksa.

11.Indeks chromatyczny grafu. Twierdzenie Wizinga.

12. Twierdzenie Kőniga o indeksie chromatycznym grafu dwudzielnego. Graf topologiczny. Graf płaski i graf planarny.

13. Wzór Eulera dla grafów płaskich. Minor i minor topologiczny grafu. Twierdzenie Kuratowskiego (bd.) Zanurzanie grafów w powierzchnie dodatniego rodzaju. Twierdzenie Ringla-Youngsa (bd.).

14. Historia twierdzenia o czterech kolorach. Kolorowanie wierzchołków grafu z list. Twierdzenie Thomassena o wybieranej liczbie chromatycznej grafów planarnych.

15. Drzewa. Twierdzenie Jordana-Sylvestra. Twierdzenie Cayleya o liczbie drzew oznaczonych.

Ćwiczenia audytoryjne (30h):
Program ćwiczeń laboratoriów pokrywa się z programem wykładów

Rozwiązywanie problemów (głównie teoretycznych) dotyczących treści przekazywanych na kolejnych wykładach.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Treści prezentowane na wykładzie są przekazywane w formie klasycznego wykładu tablicowego.
  • Ćwiczenia audytoryjne: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Warunkiem koniecznym dopuszczenia do egzaminu jest zaliczenie ćwiczeń. Przewidziane są dwa pisemne kolokwia poprawkowe.

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Nie
    – Zasady udziału w zajęciach: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci mogą na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie treści przekazanych na wykładzie i zadań podanych przez prowadzącego. Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
Sposób obliczania oceny końcowej:

Ocena końcowa (OK) jest średnią ważoną ocen z egzaminu (E) i zaliczenia ćwiczeń audytoryjnych (A):

OK = 2/3 x E + 1/3 x A.

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Student powinien zgłosić się do prowadzącego w celu ustalenia indywidualnego sposobu nadrobienia zaległości.

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

Warunkiem koniecznym zaliczenia ćwiczeń (w jakimkolwiek terminie) jest co najwyżej jedna nieusprawiedliwiona nieobecność na ćwiczeniach.

Zalecana literatura i pomoce naukowe:

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

2. R. Diestel, Graph Theory, Springer-Verlag, New York, 2010.

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. M.Pilśniak, Improving Upper Bounds for the Distinguishing Index, Ars Math. Contemp. 13 (2017) 259—274.

2. R.Kalinowski, Dense on-line arbitrarily partitionable graphs, Discrete Appl. Math. 226 (2017), 71–77.

3. R.Kalinowski, M. Pilśniak, M.Woźniak, A Note on Breaking Small Automorphisms in Graphs, Discrete Appl. Math. 232 (2017) 221–225.

4. E. Estaji, W. Imrich, R.Kalinowski, M. Pilśniak, T.Tucker, Distinguishing Cartesian products of countable graphs, Discuss. Math. Graph Theory 37 (2017), 155–164.

5. M.Pilśniak, Edge-Motion and the Distinguishing Index, Teoret. Comput. Science 678 (2017) 56—62.

6. W. Imrich, R.Kalinowski, M. Pilśniak, M. Shekarriz, Bounds for Distinguishing Invariants of Infinite Graphs, Electron. J. Combin. 24(3) (2017), #P3.6 [14 pp.].

7. A.Gorzkowska, R.Kalinowski, M. Pilśniak, The distinguishing index of the Cartesian product of finite graphs, Ars Math. Contemp. 12(1) (2017), 77–87.

8. Kalinowski, Rafał; Pilśniak, Monika; Schiermeyer, Ingo; Woźniak, Mariusz; Dense arbitrarily partitionable graphs, Discuss. Math. Graph Theory 36 (2016) 5-22.

9. Kalinowski, Rafał; Pilśniak, Monika; Woźniak, Mariusz; Distinguishing graphs by total colourings, Ars Math. Contemp. 11 (2016), 79-89.

10. Kalinowski, Rafał; Pilśniak, Monika; Distinguishing graphs by edge-colourings.; European J. Combin. 45, 124-131 (2015).

Informacje dodatkowe:

Brak