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

Topologiczne metody w teorii 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 podstawowe pojęcia i twierdzenia topologicznej teorii grafów (zanurzenie grafu w powierzchnię, rodzaj grafu, nakrycie powierzchni i grafu, układ rotacyjny) oraz metody i narzędzia topologiczne stosowane w kombinatorycznej teorii grafów( kompleksy komórkowe i simplicjalne, działania skończonych grup na kompleksach, k-spójność przestrzeni, wersje twierdzenia Borsuka-Ulama). Zna podstawowe własności przestrzeni konfiguracyjnych stowarzyszonych z grafem MAT2A_W04, MAT2A_U13, MAT2A_U06, MAT2A_U02, MAT2A_W05 Aktywność na zajęciach,
Egzamin,
Esej,
Kolokwium,
Odpowiedź ustna
M_W002 zna przykłady zastosowania metod topologicznych w teorii grafów i - kombinatoryce( twierdzenie Lovasza- Knesera, twierdzenie Schrijvera,twierdzenie o Zp-indeksie) MAT2A_U17, MAT2A_U14, MAT2A_U04, MAT2A_K05 Aktywność na zajęciach,
Egzamin,
Esej,
Kolokwium,
Odpowiedź ustna
M_W003 zna najważniejsze podstawowe fakty z historii topologicznej teorii grafów oraz wybrane hipotezy teorii grafów i topologii kombinatorycznej MAT2A_W06, MAT2A_W04, MAT2A_W03, MAT2A_W05 Aktywność na zajęciach,
Egzamin,
Esej,
Kolokwium,
Odpowiedź ustna
Umiejętności: potrafi
M_U001 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń MAT2A_U01, MAT2A_W02, MAT2A_W04, MAT2A_W05 Aktywność na zajęciach,
Egzamin,
Esej,
Kolokwium,
Odpowiedź ustna
M_U002 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę z topologii i teorii grafów MAT2A_U14, MAT2A_U01, MAT2A_W02, MAT2A_W04, MAT2A_K02, MAT2A_U13, MAT2A_U02, MAT2A_U03, MAT2A_K01 Aktywność na zajęciach,
Egzamin,
Esej,
Kolokwium,
Odpowiedź ustna
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (algebra, topologia geometryczna) w teorii grafów i kombinatoryce MAT2A_U13, MAT2A_U04, MAT2A_W07, MAT2A_U08 Aktywność na zajęciach,
Egzamin,
Esej,
Kolokwium,
Odpowiedź ustna
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_K06, MAT2A_K01 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 podstawowe pojęcia i twierdzenia topologicznej teorii grafów (zanurzenie grafu w powierzchnię, rodzaj grafu, nakrycie powierzchni i grafu, układ rotacyjny) oraz metody i narzędzia topologiczne stosowane w kombinatorycznej teorii grafów( kompleksy komórkowe i simplicjalne, działania skończonych grup na kompleksach, k-spójność przestrzeni, wersje twierdzenia Borsuka-Ulama). Zna podstawowe własności przestrzeni konfiguracyjnych stowarzyszonych z grafem + + - - - - - - - - -
M_W002 zna przykłady zastosowania metod topologicznych w teorii grafów i - kombinatoryce( twierdzenie Lovasza- Knesera, twierdzenie Schrijvera,twierdzenie o Zp-indeksie) + + - - - - - - - - -
M_W003 zna najważniejsze podstawowe fakty z historii topologicznej teorii grafów oraz wybrane hipotezy teorii grafów i topologii kombinatorycznej + + - - - - - - - - -
Umiejętności
M_U001 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń + + - - - - - - - - -
M_U002 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę z topologii i teorii grafów + + - - - - - - - - -
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (algebra, topologia geometryczna) w teorii grafów i kombinatoryce + + - - - - - - - - -
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 150 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 42 godz
Samodzielne studiowanie tematyki zajęć 41 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Dodatkowe godziny kontaktowe 5 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):

WYKŁADY

1. Nakrycia grafów i powierzchni. Regularne nakrycia grafów

2. Powierzchnie orientowalne i nieorientowalne. Charakterystyka Eulera i genus
powierzchni domkniętej.

3. Zanurzenia komórkowe grafów w powierzchnie orientowalne. Genus grafu.

4. Grafy rotacyjne. Twierdzenie Edmondsa.

5. Oszacowania dolne liczby chromatycznej grafu.

6. Kompleksy simplicjalne i wielościany.

7. Działania grup skończonych G na kompleksach simplicjalnych i wielościanach
Działania wolne grup.Przykłady.

8. Różne wersje twierdzenia Borsuka-Ulama.

9. Grafy Knesera. Twierdzenie Lovasza-Knesera. Uogólnione grafy Knesera.
Twierdzenie Dolnikova.

10. k-spójne przestrzenie. Różne konstrukcje wielościanów i kompleksów
simplicjalnych: suspenzja, produkt kartezjański, join i produkt niepełny.

11. Z2-indeks kompleksów z inwolucją i jego własności. Relacje między Z2-indeksem a
k-spójnością wielościanu z inwolucją, sposoby ich wyznaczenia lub oszacowania.

12. Z2-kompleksy simplicjalne stowarzyszone z grafem G (boks-kompleksy B(G) i
B0 z inwolucją). Twierdzenie Sarkaria. Związek z topologicznym problemem
zanurzenia.

13. Ogólne oszacowania dolne liczby chromatycznej grafu G przez Z2-indeks
stowarzyszonych boks-kompleksów B(G) i B0.

14. Zp-indeks kompleksów z działaniem grupy Zp i liczba chromatyczna hipergrafów
KGr(F)

15.Przestrzeń konfiguracyjna stowarzyszona z grafem. Obliczanie grupy podstawowej.

Ćwiczenia audytoryjne (30h):
  1. Rozwiązywanie problemów (głównie teoretycznych ) dotyczących treści przekazywanych na kolejnych wykładach.

  2. Konstrukcja box-kompleksów stowarzyszonych z grafami. Obliczanie Z_p indeksu kompleksów komórkowych stowarzyszonych z grafami i hipergrafami. Konstrukcja pomocniczych grafów napięcia i prądu dla zanurzeń grafów w powierzchnie orientowalne domknięte. Oszacowanie dolne liczby chromatycznej grafu przez Z_p indeks stowarzyszonego box-kompleksu. Oszacowanie dolne silnej liczby chromatycznej hipergrafu H (w silnym kolorowaniu H) z wykorzystaniem Z_p indeksu kompleksu stowarzyszonego z H. Sposoby obliczenia grupy podstawowej przestrzeni konfiguracyjnych stowarzyszonych z grafem.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Ćwiczenia audytoryjne: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej 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:

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni 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 wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). 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 wagowa oceną z egzaminu i zaliczenia ćwiczeń audytoryjnych (A) w proporcji 2 do 1.

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 :

Znajomość podstawowych pojęć i twierdzeń topologii, algebry i teorii grafów

Zalecana literatura i pomoce naukowe:

1. J. A. Bondy, U. S. R. Murty, Graph theory, New York: Springer-Verlag, 2008.

2. J.Matoušek, Using the Borsuk-Ulam Theorem, Lectures on Topological Methods in
Combinatorics and Geometry, Springer, 2003.

3. G. Ringel, Map Color Theorem, Springel-Verlag, Berlin, 1974.

4. J.L.Gross , T.W.Tucker, The topological graph theory, Dover Publications Inc., New
York, 2012

5. Richard M. Wilson , Graph puzzles, homotopy, and alternating group, Journal of combinatorial theory (B), vol. 16, (1974), pp. 86-96.

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

1. Essential tori admitting standard tiling, Fundamenta Math., 189, 2006, pp.195-206.

2. Knots, satellite operations and invariants of finite order, J. Knot Theory Ramifications, 15, Nu.8, 2006, pp.1061-1077.

Informacje dodatkowe:

Brak