Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Grafy i Sieci
Tok studiów:
2019/2020
Kod:
AMAT-2-202-MZ-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka w zarządzaniu
Kierunek:
Matematyka
Semestr:
2
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
dr hab. Marczyk Antoni (marczyk@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Pojęcia i twierdzenia teorii grafów skierowanych (spójność, problemy hamiltonowskie, eulerowskie, przestrzenie liniowe związane z grafami). Zastosowania. Graf doskonały i problemy ekstremalne.

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 teorii grafów skierowanych (słabą i silną spójność, problemy hamiltonowskie, eulerowskie, istnienie jądra, przestrzenie liniowe związane z grafami). Zna pojęcia sieci (elektrycznej, gazowej, czynności w planowaniu) i przepływu w sieciach. Zna również pojęcie grafu doskonałego i problemy ekstremalne w grafach. MAT2A_W05, MAT2A_W11, MAT2A_W01, MAT2A_W02 Aktywność na zajęciach,
Kolokwium,
Egzamin
M_W002 zna przykłady modelowania matematycznego wykorzystującego teorię grafów, potrafi zaprojektować sieć elektryczną, sieć czynności metodą CPM, zastosować algorytm Forda-Fulkersona. MAT2A_W11, MAT2A_W07, MAT2A_W01, MAT2A_W02, MAT2A_W03 Aktywność na zajęciach,
Egzamin,
Kolokwium
Umiejętności: potrafi
M_U001 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń MAT2A_U04, MAT2A_U02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U002 potrafi wykorzystać wiedzę z innych działów matematyki (algebra, matematyka dyskretna) w teorii grafów MAT2A_U14, MAT2A_U13, MAT2A_U10, MAT2A_U02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Kompetencje społeczne: jest gotów do
M_K001 Potrafi samodzielnie wyszukiwać informacje w literaturze i formułować opinie na temat podstawowych zagadnień matematycznych MAT2A_K07, MAT2A_K06 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
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 teorii grafów skierowanych (słabą i silną spójność, problemy hamiltonowskie, eulerowskie, istnienie jądra, przestrzenie liniowe związane z grafami). Zna pojęcia sieci (elektrycznej, gazowej, czynności w planowaniu) i przepływu w sieciach. Zna również pojęcie grafu doskonałego i problemy ekstremalne w grafach. + + - - - - - - - - -
M_W002 zna przykłady modelowania matematycznego wykorzystującego teorię grafów, potrafi zaprojektować sieć elektryczną, sieć czynności metodą CPM, zastosować algorytm Forda-Fulkersona. + + - - - - - - - - -
Umiejętności
M_U001 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń + + - - - - - - - - -
M_U002 potrafi wykorzystać wiedzę z innych działów matematyki (algebra, matematyka dyskretna) w teorii grafów + + - - - - - - - - -
Kompetencje społeczne
M_K001 Potrafi samodzielnie wyszukiwać informacje w literaturze i formułować opinie na temat podstawowych zagadnień matematycznych + + - - - - - - - - -
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):
Grafy i sieci

Wykład.
1. Grafy skierowane. (10 godz. wykładu). Grafy skierowane. Droga, droga prosta, ścieżka, kontur, cykl w grafach skierowanych. Słaba i silna spójność. Cykl Eulera. Tw. Eulera.
Cykl hamiltonowski i ścieżka hamiltonowska.

2. Turnieje, turnieje tranzytywne. Tw. Redei. Tw. Moona. Tw. Meyniela bd. Tw. Ghouila-Houriego bd. Tw. Thomassena o cyklach parzystych bd. Tw. Nash-Williamsa.

3. Tw. Robbinsa o orientacji grafu nieskierowanego. Składowe silnie spójne grafu. Tw. Roya i Gallaia. Jądro grafu.

4. Tw. Richardsona. Jądro w grafach przechodnich i symetrycznych. Zastosowanie tw. Eulera: problem dalekopisu.

5. Klasyczne przestrzenie liniowe związane z grafami. Własności macierzy sąsiedztwa, incydencji i oczek.

6. Sieci. (7 godz wykładu). Sieć czynności w planowaniu przedsięwzięć. Metoda ścieżki krytycznej. Metoda PERT.

7. Przepływy w sieciach. Tw. Forda–Fulkersona.

8. Sieci elektryczne i gazowe.

9. Prawa Kirchhoffa. Grafy doskonałe. (5 godz. wykładu). Grafy „alfa”-doskonałe i „gamma”-doskonałe. Hipotezy Berge’a. Tw. Lovasza bd.

10. Grafy doskonałe. Grafy silnego porządku. Grafy z cięciwami.

11. Grafy przedziałów. Zastosowania. Tw. Chudnovsky’ej i innych.

12. Problemy ekstremalne w grafach. (6 godz. wykładu).
Problemy ekstremalne dla ścieżek i cykli. Tw. Posy.

13. Problemy ekstremalne dla grafów pełnych. Tw. Turana.

14. Problem Zarankiewicza. Tw. Erdosa-Stone’a bd

Ćwiczenia audytoryjne (30h):
Grafy i sieci

Rozwiązywanie zadań rachunkowych i teoretycznych dotyczących treści przekazywanych na wykładach.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Wykład jest klasycznym wykładem tablicowym. Mile widziana aktywność studentów podczas wykładu - np. zadawanie pytań wykładowcy.
  • Ć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:

Warunkiem dopuszczenia do egzaminu jest uzyskanie oceny pozytywnej z ćwiczeń (w przypadku braku zaliczenia z ćwiczeń w pierwszym terminie, student ma prawo do dwóch zaliczeń poprawkowych, których sposób przeprowadzenia ustala osoba prowadząca ćwiczenia).

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 ś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 :

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:

1 B. Bollobas, Modern Graph Theory, Springer-Verlag, New York 1998.
2 J. A. Bondy and U.S.R. Murty, Graphs Theory with Applications, Macmillan. London, 1976.
3 N. Deo, Teoria grafów i jej zastosowania w technice i informatyce, PWN, W-wa 1980.
4 R. J. Wilson, Wprowadzenie do teorii grafów, PWN, W-wa 1985.

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

1. Baudon, Olivier; Bensmail, Julien; Kalinowski, Rafał; Marczyk, Antoni; Przybyło, Jakub; Woźniak, Mariusz
On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph;
Discrete Math. Theor. Comput. Sci. 16, No. 1, 225-232, electronic only (2014).

2. Flandrin, Evelyne; Marczyk, Antoni; Przybyło, Jakub; Saclé, Jean-François; Woźniak, Mariusz
Neighbor sum distinguishing index;
Graphs Comb. 29, No. 5, 1329-1336 (2013).

3. Horňák, Mirko; Marczyk, Antoni; Schiermeyer, Ingo; Woźniak, Mariusz
Dense arbitrarily vertex decomposable graphs;
Graphs Comb. 28, No. 6, 807-821 (2012).

4. Marczyk, Antoni; An Ore-type condition for arbitrarily vertex decomposable graphs;
Discrete Math. 309, No. 11, 3588-3594 (2009).

5. Marczyk, Antoni; Cycles in graphs and related problems; Diss. Math. 454, 98 p. (2008).

6. Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz;
A Chvátal–Erdős type condition for pancyclability; Discrete Math. 307, No. 11-12, 1463-1466 (2007).

Informacje dodatkowe:

Brak