Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Strukturalna teoria grafów
Tok studiów:
2016/2017
Kod:
AMA-3-204-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia III stopnia
Specjalność:
-
Kierunek:
Matematyka
Semestr:
2
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski i Angielski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
prof. dr hab. Woźniak Mariusz (mwozniak@agh.edu.pl)
Osoby prowadzące:
prof. dr hab. Woźniak Mariusz (mwozniak@agh.edu.pl)
Krótka charakterystyka modułu

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
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. MA3A_W01 Egzamin,
Aktywność na zajęciach
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. MA3A_U01 Egzamin,
Aktywność na zajęciach
M_U002 Wie jakimi kryteriami kierować się przy wyborze metody dowodu; potrafi przy tym korzystać z właściwej literatury. MA3A_U01 Egzamin,
Aktywność na zajęciach
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ć MA3A_K01 Egzamin,
Aktywność na zajęciach
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
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ć + + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

PL

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

Program ćwiczeń zgodny z programem wykładu.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 100 godz
Punkty ECTS za moduł 4 ECTS
Udział w wykładach 28 godz
Udział w ćwiczeniach audytoryjnych 28 godz
Samodzielne studiowanie tematyki zajęć 43 godz
Egzamin lub kolokwium zaliczeniowe 1 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Ocena z egzaminu.

Grade from examination.

Wymagania wstępne i dodatkowe:

Podstawa wiedza w zakresie teorii grafów

Basic knowledge of graph theory.

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 edge-colorings 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), # 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