Cel kształcenia i wykaz literatury

Główny cel kształcenia: Zapoznanie studentów z zaawansowanymi metodami teorii grafów

Ogólne informacje o zajęciach: Moduł obejmuje zagadnienia z zakresu niezależności, dominowania i kolorowania w grafach na poziomie rozszerzonym

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	R. Diestel	Graph theory	Springer-Verlag, Heidelberg, New York.	2005
2	Z. Palka, A. Ruciński	Niekonstruktywne metody matematyki dyskretnej	WNT, Warszawa.	1996

Literatura wykorzystywana podczas zajęć ćwiczeniowych/laboratoryjnych/innych

1	Z. Palka, A. Ruciński	Niekonstruktywne metody matematyki dyskretnej	WNT, Warszawa.	1996
2	R. Diestel	Graph theory	Springer-Verlag, Heidelberg, New York.	2005

Literatura do samodzielnego studiowania

1

C. Berge

Graphs and hypergraphs

North-Holland Publishing Company.

1976

Wymagania wstępne w kategorii wiedzy/umiejętności/kompetencji społecznych

Wymagania formalne: Student spełnia wymagania formalne określone w regulaminie studiów

Wymagania wstępne w kategorii Wiedzy: opanowanie podstaw teorii grafów

Wymagania wstępne w kategorii Umiejętności: umiejętność zastosowania metod matematyki dyskretnej

Wymagania wstępne w kategorii Kompetencji społecznych: umiejętność pracy w grupie

Efekty kształcenia dla zajęć

MEK	Student, który zaliczył zajęcia	Formy zajęć/metody dydaktyczne prowadzące do osiągnięcia danego efektu kształcenia	Metody weryfikacji każdego z wymienionych efektów kształcenia	Związki z KEK	Związki z OEK
01	Student zna podstawowe pojęcia i twierdzenia teorii grafów	wykład, ćwiczenia problemowe	kolokwium	K_W01+ K_W05+ K_U02+ K_U04+	X2A_W01 X2A_W02 X2A_U03 X2A_U05
02	Student zna podstawowe i zaawansowane metody teorii grafów	wykład, ćwiczenia problemowe	kolokwium	K_W04+ K_U02+ K_U03+ K_K02+ K_K07+	X2A_U01 X2A_U02 X2A_U03 X2A_U05 X2A_K01 X2A_K02 X2A_K06
03	Student potrafi użyć metod teorii grafów do rozwiązywania problemów dyskretnych	wykład, ćwiczenia problemowe	kolokwium	K_W07+ K_U04+ K_K01+ K_K04+	X2A_W02 X2A_U03 X2A_U07 X2A_K01 X2A_K03 X2A_K04

Uwaga: W zależności od sytuacji epidemicznej, jeżeli nie będzie możliwości weryfikacji osiągniętych efektów uczenia się określonych w programie studiów w sposób stacjonarny w szczególności zaliczenia i egzaminy kończące określone zajęcia będą mogły się odbywać przy użyciu środków komunikacji elektronicznej (w sposób zdalny).

Treści kształcenia dla zajęć

Sem.	TK	Treści kształcenia	Realizowane na	MEK
3	TK01	Przypomnienie podstawowych definicji, twierdzeń i oznaczeń z teorii grafów.	W01, W02, C01, C02	MEK01
3	TK02	Produkty grafowe i ich zastosowania. Uogólnione produkty grafowe.	W03, C03	MEK01 MEK02
3	TK03	Niezależność w grafie. Zbiory niezależnie, zbiory k-niezależne. Liczba niezależności grafu i jej oszacowania. Zliczanie zbiorów niezależnych w pewnych klasach grafów.	W04, W05, C04, C05, C06	MEK01 MEK02
3	TK04	Indeks Merrifielda-Simmonsa, indeks Hosoya. Inne parametry grafowe i ich związek z liczbą niezależności w grafach (np. indeksy Zagreb grafu).	W06, W07, W08, C07, C09	MEK01 MEK03
3	TK05	Dominowanie w grafach i jego różne warianty. Liczba dominowania i jej oszacowania. Zliczanie zbiorów dominujących w pewnych klasach grafów. Jądra grafów, (k,l)- jądra.	W09, W10, W11, C10, C11, C12	MEK01 MEK03
3	TK06	Kolorowanie grafów. Kolorowanie wierzchołków, krawędzi, kolorowanie mieszane. Wielomian chromatyczny i jego własności. Inne warianty kolorowania.	W12, W13, W14, W15, C13, C14	MEK01 MEK03
3	TK07	Kolokwia	C8, C15	MEK01 MEK02 MEK03

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 3)	Przygotowanie do kolokwium: 10.00 godz./sem.	Godziny kontaktowe: 30.00 godz./sem.	Uzupełnienie/studiowanie notatek: 5.00 godz./sem. Studiowanie zalecanej literatury: 5.00 godz./sem.
Ćwiczenia/Lektorat (sem. 3)	Przygotowanie do ćwiczeń: 5.00 godz./sem. Przygotowanie do kolokwium: 10.00 godz./sem.	Godziny kontaktowe: 30.00 godz./sem.	Dokończenia/studiowanie zadań: 5.00 godz./sem.
Konsultacje (sem. 3)
Zaliczenie (sem. 3)

Sposób wystawiania ocen składowych zajęć i oceny końcowej

Forma zajęć	Sposób wystawiania oceny podsumowującej
Wykład	Zaliczenia wykładu dokonuje się na podstawie obecności na wykładach.
Ćwiczenia/Lektorat	Warunkiem zaliczenia ćwiczeń jest uzyskanie jest uzyskanie co najmniej 50% punktów z każdego kolokwium. Ocenę końcową z ćwiczeń można podwyższyć przez wygłoszenie referatu na ćwiczeniach.
Ocena końcowa	Ocena końcowa jest oceną z ćwiczeń.

Przykładowe zadania

Wymagane podczas egzaminu/zaliczenia
(-)

Realizowane podczas zajęć ćwiczeniowych/laboratoryjnych/projektowych
(-)

Inne
(-)

Czy podczas egzaminu/zaliczenia student ma możliwość korzystania z materiałów pomocniczych : nie

Treści zajęć powiazane są z prowadzonymi badaniami naukowymi: nie