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

Problemy i rodzaje kolorowania 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 wybrane zaawansowane pojęcia i twierdzenia teorii grafów (rozróżnianie wszystkich lub sąsiednich wierzchołków grafu przy pomocy różnych kolorowań czy znaczeń krawędzi i wierzchołów) MAT2A_W02, MAT2A_W04, MAT2A_U13, MAT2A_U02, MAT2A_W05 Odpowiedź ustna,
Kolokwium,
Esej,
Egzamin,
Aktywność na zajęciach
M_W002 rozumie potrzebę wprowadzenia różnych sposobów kolorowań oraz zna przykłady zastosowań rozważanych kolorowań w informatyce MAT2A_U14, MAT2A_U04, MAT2A_K05 Odpowiedź ustna,
Kolokwium,
Esej,
Egzamin,
Aktywność na zajęciach
M_W003 zna najważniejsze fakty z historii teorii grafów oraz wybrane nierozstrzygnięte hipotezy MAT2A_W06, MAT2A_W03, MAT2A_K05 Egzamin,
Aktywność na zajęciach
Umiejętności: potrafi
M_U001 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,
Esej,
Egzamin,
Aktywność na zajęciach
M_U002 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę MAT2A_U14, MAT2A_U01, MAT2A_W02, MAT2A_K02, MAT2A_U13, MAT2A_U02, MAT2A_U03, MAT2A_K01 Odpowiedź ustna,
Kolokwium,
Esej,
Egzamin,
Aktywność na zajęciach
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (algebra, topologia, matematyka dyskretna) w teorii grafów MAT2A_U19, MAT2A_U14, MAT2A_U04, MAT2A_W07, MAT2A_U08 Odpowiedź ustna,
Kolokwium,
Esej,
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_K01 Odpowiedź ustna,
Kolokwium,
Esej,
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 wybrane zaawansowane pojęcia i twierdzenia teorii grafów (rozróżnianie wszystkich lub sąsiednich wierzchołków grafu przy pomocy różnych kolorowań czy znaczeń krawędzi i wierzchołów) + + - - - - - - - - -
M_W002 rozumie potrzebę wprowadzenia różnych sposobów kolorowań oraz zna przykłady zastosowań rozważanych kolorowań w informatyce + + - - - - - - - - -
M_W003 zna najważniejsze fakty z historii teorii grafów oraz wybrane nierozstrzygnięte hipotezy + + - - - - - - - - -
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ę + + - - - - - - - - -
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 161 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 50 godz
Samodzielne studiowanie tematyki zajęć 50 godz
Egzamin lub kolokwium zaliczeniowe 1 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. Liczba chromatyczna grafu. Twierdzenie Brooksa (bd.). Kolorowanie właściwe krawędzi grafu. Twierdzenie Wizinga (bd.). Twierdzenie Kőniga (bd.) o indeksie chromatycznym grafu dwudzielnego. Totalne kolorowanie grafu i hipoteza Behzada-Wiznga.

2. Kolorowania właściwe totalne i rozróżnianie sąsiednich wierzchołków sumami (jako uogólnienie rozróżniania zbiorami). Dowód hipotezy Pilśnak-Woźniaka dla subkubicznych i dwudzielnych. Ogólne ograniczenie (bd.)

3. Rozróżnianie sąsiednich wierzchołków sumami – cd.: grafy z małym średnim stopniem, dowód metodą rozładunku.

4. Kolorowania z list, tw. Galvina – dowód hipotezy ch’=χ’ dla grafów dwudzielnych.

5. Kolorowania niewłaściwe totalne i hipoteza 1-2. Dowód Kalkowskiego z żetonami. Hipoteza 1-2 dla digrafów ze stopniem zbalansowanym.

6. Rozróżnianie wierzchołków paletami (drogami długości jeden) według Burris-Schelpa. Rozróżnianie wierzchołków kolorowymi drogami; ograniczenie typu Wizinga.

7. Automorfizmy grafów i ich przełamywanie kolorowaniami – zastosowanie kolorowań rozróżniających w informatyce. Rozróżniające kolorowanie właściwe krawędziowe i totalne – górne ograniczenia chromatycznych indeksów rozróżniających.

8. Indeks i liczba rozróżniająca – górne ograniczenia dla drzew i ogólne.

9. Grafy nieskończone. Lemat Kőniga. Twierdzenie typu Brooksa dla grafów nieskończonych.

10. Twierdzenie Wizinga dla grafów nieskończonych.

11. Wartość indeksu rozróżniającego dla grafów spójnych dowolnie dużych, dla grafu z minimalnym stopniem nieskończonym, dla drzew bez liści.

12. Graf Rada i hiperkostka nieskończenie wymiarowa.

13. Ograniczenie górne indeksów rozróżniających dla grafów subkubicznych.

14. Hipoteza Tuckera o nieskończonym ruchu i jej częściowe rozwiązania.

15. Chromatyczna liczba rozróżniająca dla grafów nieskończonych – górne ograniczenia.

Ćwiczenia audytoryjne (30h):

ĆWICZENIA AUDYTORYJNE

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

Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.
Dwa terminy zaliczeń poprawkowych są skorelowane czasowo z egzaminami poprawkowymi.

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 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 ,
gdzie E jest średnią arytmetyczną ocen uzyskanych na egzaminie w kolejnych terminach, A jest średnią arytmetyczną ocen uzyskanych z ćwiczeń w kolejnych terminach. Uzyskanie pozytywnej oceny końcowej następuje po uzyskaniu pozytywnego wyniku z egzaminu poprzedzonego pozytywnym zaliczeniem ćwiczeń.
Warunkiem przystąpienia do egzaminu jest wcześniejsze uzyskanie zaliczenia z ćwiczeń. Warunkiem ubiegania się o zaliczenie ćwiczeń jest 80% obecności na ćwiczeniach.

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 :

Egzamin z Teorii Grafów.

Zalecana literatura i pomoce naukowe:

1. M.Borowiecki, J.Grytczuk, M.Pilśniak, Coloring chip configurations on graphs and digraphs, Information Processing Letters 112 (2012) 1-4.

2. R. Kalinowski, M. Pilśniak, J. Przybyło, M. Woźniak, How to personalize the vertices of graphs?, European Journal of Combinatorics 40 (2014) 116–123

3. O.Baudon, J. Bensmail, E.Sopena, An oriented version of the 1-2-3 Conjecture, Discuss. Math. Graph Theory 35 (2015), 141–-156.

4. R. Kalinowski, M. Pilśniak, Distinguishing graphs by edge-colourings, European Journal of Combinatorics 45 (2015) 124–131

5. I. Broere, M. Pilśniak, The distinguishing index of infinite graphs, Electronic Journal of Combinatorics 23(1) (2015), P1.78

6. M.Pilśniak, M.Woźniak, On the total neighbor distinguishing index by sums, Graphs and Combinatorics (2015) 31:771–782

7. R. Kalinowski, M. Pilśniak, M. Woźniak, Distinguishing graphs by total colourings, Arc Math. Contemporanea, (2016) 11:79–89

8. E. Estaji, W. Imrich, R. Kalinowski, M. Pilśniak, T. Tucker, Distinguishing number for the Cartesian product of countable graphs, Discussiones Mathematicae Graph Theory 37 (2017) 155–164

9. M. Pilśniak, Improvig upper Bounds for the Distinguishing Index, Ars Math. Contemporanea 13 (2017) 259-274.

10. W. Imrich, R. Kalinowski, M. Pilśniak, M. Shekarriz, Bounds for Distinguishing Invariants of Infinite Graphs; Electronic J. Comb. 24(3) (2017) P3.6.

11. A.C.Burris, R.H.Schelp, Vertex-distinguishing proper edge-colorings, J. Graph Theory 26(2) (1997), 73—82.

12. R.Diestel, Graph Theory, 5th Edition, Springer-Verlag, 2016

13. L.Ding, G.Wang, J.Wu, J.Yu, Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, Theoret. Computer Sci. 609 (2016), 162—170.

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

1. M.Borowiecki, J.Grytczuk, M.Pilśniak, Coloring chip configurations on graphs and digraphs, Information Processing Letters 112 (2012) 1-4.
2. R. Kalinowski, M. Pilśniak, J. Przybyło, M. Woźniak, Can colour-blind distinguish colour palettes? Electronic Journal of Combinatorics 20(3) (2013), 23
3. R. Kalinowski, M. Pilśniak, J. Przybyło, M. Woźniak, How to personalize the vertices of graphs?, European Journal of Combinatorics 40 (2014) 116–123
4. R. Kalinowski, M. Pilśniak, Distinguishing graphs by edge-colourings, European Journal of Combinatorics 45 (2015) 124–131
5. I. Broere, M. Pilśniak, The distinguishing index of infinite graphs, Electronic Journal of Combinatorics 23(1) (2015), P1.78
6. M.Pilśniak, M.Woźniak, On the total neighbor distinguishing index by sums, Graphs and Combinatorics (2015) 31:771–782
7. R. Kalinowski, M. Pilśniak, M. Woźniak, Distinguishing graphs by total colourings, Arc Math. Contemporanea, (2016) 11:79–89
8. A. Gorzkowska, R. Kalinowski, M. Pilśniak, The distinguishing index of Cartesian product of graphs, Ars Math. Contemp. 12 (2017) 77–-87.
9. E. Estaji, W. Imrich, R. Kalinowski, M. Pilśniak, T. Tucker, Distinguishing number for the Cartesian product of countable graphs, Discussiones Mathematicae Graph Theory 37 (2017) 155–164
10. I. Broere, M. Pilśniak, The distinguishing index of the Cartesian product of countable graphs, Ars Math. Contemp. 13 (2017) 15—21
11. M. Pilśniak, Improvig upper Bounds for the Distinguishing Index, Ars Math. Contemporanea 13 (2017) 259-274.
12. M. Pilśniak, Edge motion and the distinguishing index, Theoret. Comput. Sci. 678 (2017) 56–62;
13. O. Baudon, M. Shenhaji, M. Pilsniak, J. Przybyło, E. Sopena, M. Woźniak, Equitable neighbour-sum-distinguishing edge and total colourings, Discrete Apllied Math.,222, (2017), 40–53;
14. A. Gorzkowska, M. Pilśniak, Precise Bounds for the Distinguishing Index of the Cartesian Product, Theoret. Comput. Sci. 687 (2017) 62–69.
15. W. Imrich, R. Kalinowski, M. Pilśniak, M. Shekarriz, Bounds for Distinguishing Invariants of Infinite Graphs; Electronic J. Comb. 24(3) (2017) P3.6.
16. R. Kalinowski, M. Pilśniak, M. Woźniak, A note on Breaking Small Automorphisms in Graphs, Discrete Appl. Math. 232 (2017) 221–225

Informacje dodatkowe:

Brak