Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Strukturalna teoria grafów
Tok studiów:
2019/2020
Kod:
ZSDA-3-0190-s
Wydział:
Szkoła Doktorska AGH
Poziom studiów:
Studia III stopnia
Specjalność:
-
Kierunek:
Szkoła Doktorska AGH
Semestr:
0
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski i Angielski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
prof. dr hab. Woźniak Mariusz (mwozniak@agh.edu.pl)
Dyscypliny:
Moduł multidyscyplinarny
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Rozszerzona wiedza o aktualnych trendach 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 Ma rozszerzoną wiedzę o aktualnych trendach teorii grafów a także o klasycznych metodach tej teorii. Rozumie mechanizm uogólnień prowadzący do nowych problemów i hipotez. Zna konkretne przykłady dotyczące rozwoju pewnych obszarów teorii grafów. SDA3A_W02 Aktywność na zajęciach,
Egzamin
Umiejętności: potrafi
M_U001 Potrafi analizować problemy pojawiające się w teorii grafów pod kątem ich potencjalnych zastosowań, odkrywczości i elegancji. Potrafi zidentyfikować potencjalne trudności występujące przy rozwiązywaniu problemów. SDA3A_U02, SDA3A_U01 Aktywność na zajęciach,
Egzamin
M_U002 Wie jakimi kryteriami kierować się przy wyborze metody dowodu; potrafi przy tym korzystać z właściwej literatury. SDA3A_U04, SDA3A_U02 Aktywność na zajęciach,
Egzamin
Kompetencje społeczne: jest gotów do
M_K001 Zdaje sobie sprawę ze słabych punktów swojej wiedzy, zdaje sobie sprawę z potrzeby dalszego kształcenia i śledzenia na bieżąco rozwoju teorii grafów i wie jak to robić SDA3A_K01, SDA3A_K03 Aktywność na zajęciach,
Egzamin
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 Ma rozszerzoną wiedzę o aktualnych trendach teorii grafów a także o klasycznych metodach tej teorii. Rozumie mechanizm uogólnień prowadzący do nowych problemów i hipotez. Zna konkretne przykłady dotyczące rozwoju pewnych obszarów teorii grafów. + + - - - - - - - - -
Umiejętności
M_U001 Potrafi analizować problemy pojawiające się w teorii grafów pod kątem ich potencjalnych zastosowań, odkrywczości i elegancji. Potrafi zidentyfikować potencjalne trudności występujące przy rozwiązywaniu problemów. + + - - - - - - - - -
M_U002 Wie jakimi kryteriami kierować się przy wyborze metody dowodu; potrafi przy tym korzystać z właściwej literatury. + + - - - - - - - - -
Kompetencje społeczne
M_K001 Zdaje sobie sprawę ze słabych punktów swojej wiedzy, zdaje sobie sprawę z potrzeby dalszego kształcenia i śledzenia na bieżąco rozwoju teorii grafów i wie jak to robić + + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 104 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Samodzielne studiowanie tematyki zajęć 43 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):

PL

1. Wprowadzenie do teorii grafów. Zanurzanie grafów w swoje dopełnienie. Specjalne własności permutacji pakujących.
Grafy bez małych cykli. Zanurzenia w grafy płaskie.

2. Pakowanie grafów. Warunki na stopnie i rozmiary grafów. Hipoteza Erdosa-Sos.

3. Pakowanie trzech grafów. Hipoteza o pakowaniu drzew. Pakowanie w grafy dwudzielne.

4. Kolorowania rozróżniające wierzchołki grafu. Różne sposoby rozróżniania. Hipoteza Barris-Schelpa. Tw. Balistera o rozkładzie na drogi Eulera.

5. Kolorowania rozróżniające wierzchołki sąsiednie. Twierdzenie Gyoriego-Palmera.

6. Hipoteza 1-2-3 oraz hipoteza 1-2. Algorytm Kalkowskiego

7. Skierowane wersje hipotezy 1-2 i 1-2-3.

8. Wersje rozgrywane i zrównoważone.

9. Automorfizmy a kolorowania. Wersja wierzchołkowa i krawędziowa parametrów rozróżniających.

10. Grafy nieskończone i ich automorfizmy.

11. Grafy dowolnie podzielne. Twierdzenie Bartha-Fourniera.

12. Inne warianty dowolnej podzielności. Związek z zagadnieniami rozróżniania.

13. Cykle w grafach. Problemy hamiltonowskie i pancykliczność. Spektrum długości cykli.

14. Grafy nasycone ze względu na daną własność. Elementy teorii grafów krawędziowo
maksymalnych.

EN

1. Introduction to graph theory. Embeddings of graphs. Self-complementary permutations. Graphs without small cycles.
Embeddings into planar graphs.

2. Packing of graphs. Conditions on degrees and sizes. Erdos-Sos conjecture.

3. Some special problems. Packing of three graphs. Tree Packing Conjecture. Packing into bipartite graphs.

4. Edge colorings distinguishing vertices of a graph. Distinct ways of distinguishing.
Barris-Schelp Conjecture. Balister’s Theorem on decomposition into Euler trails.

5. Colorings distinguishing neighbor vertices. Gyori-Palmer Theorem.

6. 1-2-3 Conjecture and 1-2 Conjecture. Kalkowski’s algorithm.

7. Directed versions of 1-2-3 Conjecture and 1-2 Conjecture.

8. Neighbor distinguishing game and equable colorings.

9. Automorphisms and colorings. Vertex and edge versions of distinguishing parameters

10. Infinite graphs and their automorphisms.

11. Arbitrarily partitionable (AP) graphs. Barth-Fournier Theorem.

12. On-line and recursively AP graphs.

13. Cycles in graphs. Hamiltonian and pancyclic graphs. Spectrum of cycle lengths.

14. Graphs saturated with respect to a given property. Some elements of theory of
size maximal graphs.

Ćwiczenia audytoryjne (30h):

Program ćwiczeń zgodny z programem wykładu.

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

wg wytycznych prowadzących ćwiczenia

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. 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 jest równa ocenie z egzaminu.

Grade from examination.

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

wg wytycznych prowadzących ćwiczenia

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

Brak

No.

Zalecana literatura i pomoce naukowe:

1. B. Bollobas, Extremal Graph Theory, Academic Press, London, 1978.

2. A. Marczyk, Cycles in graphs and related problems, Dissertationes Math. 454
(2008), 1-98.

3. D.B. West, Introduction to graph theory, Prentice Hall, 2001.

4. M. Woźniak, Packing of graphs, Dissertationes Math. CCCLXII
(1997), 1-78.

5. Preprinty z serii „Matematyka Dyskretna”

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

1.M.Woźniak I A.P.Wojda, Triple placement of graphs, Graphs and
Combinatorics 9 (1993), 85-91.
2.M.Woźniak, Embedding graphs of small size, Discrete Applied Math.
51 (1994), 233–241.
3.M.Woźniak, On the Erdos–Sos conjecture, J. Graph Theory 21 (2)
(1996), 229–234.
4.M.Woźniak, Packing of Graphs, Dissertationes Mathematicae 362 (1997), pp.78
5.J-F.Sacle and M.Woźniak, The Erdos-Sos conjecture for graphs without
C4, J. Combin. Theory, Series B 70 (2) (1997), 367–372.
6.C.Bazgan, A.Harkat-Benhamdine, H.Li and M.Woźniak, On the vertexdistinguishing proper edgecolorings
of graphs, J. Combin. Theory, Series B 75 (1999), 288–301.
7.C.Bazgan, H.Li and M.Woźniak, On the Loebl-Komlos-Sos conjecture,
J. Graph Theory, 34 (2000), 269–276.
8.M.Hornak and M.Woźniak, Decomposition of complete bipartite even
graphs into closed trails, Czechoslovak Math. Journal 53 (1) (2003),
127–134.
9.A.Marczyk i M.Woźniak, Cycles in hamiltonian graphs of prescribed
maximum degree, Discrete Math. 266 (2003), 321–326.
10.M. Woźniak, Packing two copies of a tree into planar graph, Opuscula
Math. 23 (2003), 95–97.
11.E. Flandrin, H. Li, A. Marczyk i M. Woźniak, A note on a generalization
of Ore’s condition, Graphs and Combin., 21 (2005), 213–216.
12.S. Cichacz, A. Gorlich, A. Marczyk, J. Przybyło i M. Woźniak, Arbitrarily
vertex decomposable caterpilars with four or five leaves, Discussiones
Mathematicae-Graph Theory, 26 (2) (2006), 291–305.
13.M. Hornak, Zs. Tuza i M. Woźniak, On-line arbitrarily vertex decomposable trees, Discrete Applied
Math. 155 (11) (2007), 1420–1429.
14.J. Przybyło and M. Woźniak, On a 1,2 Conjecture, Discrete Math.
Theoretical Computer Science, 12 (1) (2010), 101–108.
15.J. Przybyło and M. Woźniak, Total weight choosability of graphs, Electronic
J. Combin., 18 (1) (2011), 1. 112.
16.M. Pilśniak, M. Woźniak, On packing of two copies of a hypergraph,
Discrete Math. Theoretical Computer Science, 13 (3) (2011), 67–74.
17.E. Flandrin, A. Marczyk, J. Przybyło, J-F.Sacle i M.Woźniak, Neighbor
Sum Distinguishing Index, Graphs and Combinatorics 29 (2013), 1329–
1336.
18.M. Hornak, R. Kalinowski, M. Meszka and M. Woźniak, Minimum
Number of Palettes in Edge Colorings, Graphs and Combinatorics 30
(2014), 619–626.
19.O. Baudon, J. Bensmail, J. Przybyło i M. Woźniak, On decomposing
regular graphs into locally irregular subgraphs, European Journal of
Combinatorics, 49 (2015), 90–104.
20.M. Pilśniak and M. Woźniak, On the Total-Neighbor-Distinguishing
Index by Sums, Graphs and Combinatorics 31 (3) (2015), 771-782.

Informacje dodatkowe:

Brak