1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2017/2018
4. Matematyka - doktoranckie
5. Gry na grafach

Wygeneruj PDF dla tej strony

Gry na grafach - opis przedmiotu

Cel przedmiotu

Omówienie znanych gier na grafach oraz parametrów grafowym związanymi z tymi grami. Przedstawienie metod dowodzenia twierdzeń podających ograniczenia na parametry grafowe związane z grami. Zapoznanie doktorantów z otwartymi problemami związanymi z omawianymi zagadnieniami.

Wymagania wstępne

Zapisz zmiany

Zaliczona na poziomie studiów I stopnia: matematyka dyskretna.

Zakres tematyczny

Rozgrywane kolorowanie wierzchołków grafu, złożoność problemu rozgrywana liczba chromatyczna drzew, grafów zewnętrznie planarnych, planarnych. Podstawowe problemy otwarte związane z ta grą.

Rozrywana liczba kolorowalności a rozgrywana liczba chromatyczna grafu. Liczba kolorowalności częściowych k-drzew.

Uogólnienia i różne modyfikacje rozgrywanego kolorowania wierzchołków grafów. Defekt rozgrywanego kolorowania grafu.

Rozgrywane kolorowanie krawędzi drzew i grafów k-zdegenerowanych. Rozgrywane kolorowanie incydencji grafu.

Rozgrywana wybieralność i barwność grafu oraz wiązek między tymi parametrami.

Rozgrywana liczba i indeks Grundy.

Gry dominujące.

Gry typu Cops-Robbers.

Gry na digrafach, gry typu Nim.

Metody kształcenia

Wykład: konwencjonalny.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu	Symbole efektów	Metody weryfikacji	Forma zajęć

Warunki zaliczenia

Forma zaliczenia przedmiotu – egzamin.

Ocena końcowa przedmiotu: ocena z egzaminu

Warunkiem zaliczenia egzaminu jest uzyskanie pozytywnej oceny ostatecznej z egzaminu.

Literatura podstawowa

1. C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
2. H. L. Bodlaender, On the complexity of some colouring games, Internat. J. Found. Comput. Sci. 2 (1991) 133-148.
3. A. Bonato, R. J. Nowakowski, The Game of Cops and Robbers on Graphs, American Mathematical Society, 2011.
4. J.A. Bondy U.S.R. Murty, Graph Theory, Springer, 2008.
5. U. Faigle, U. Kern, H.A. Kierstead, W.T. Trotter, On the game chromatic number of some classes of graphs, Ars Combin. 35 (1993) 143-150.
6. H. A. Kierstead, A simple competitive graph colouring algorithm, J. Combin. Theory Ser. B 78 (2000) 57-68.

Literatura uzupełniająca

1.  Wybrane artykuły z podanej tematyki.

Uwagi

Zmodyfikowane przez mgr Natalia Gawłowicz (ostatnia modyfikacja: 01-09-2017 08:23)