Karta przedmiotu

Przedmiot wybieralny II - Teoria grafów

Podstawowe informacje o zajęciach

Cykl kształcenia:

2018/2019

Nazwa jednostki prowadzącej studia:

Wydział Matematyki i Fizyki Stosowanej

Nazwa kierunku studiów:

Matematyka

Obszar kształcenia:

nauki ścisłe

Profil studiów:

ogólnoakademicki

Poziom studiów:

drugiego stopnia

Forma studiów:

stacjonarne

Specjalności na kierunku:

zastosowania matematyki w ekonomii, Zastosowania matematyki w informatyce

Tytuł otrzymywany po ukończeniu studiów:

magister

Nazwa jednostki prowadzącej zajęcia:

Zakład Matematyki Dyskretnej

Kod zajęć:

4059

Status zajęć:

obowiazkowy dla programu z możliwością wyboru zastosowania matematyki w ekonomii

Układ zajęć w planie studiów:

sem: 3 / W30 C30 / 4 ECTS / Z

Język wykładowy:

polski

Imię i nazwisko koordynatora:

dr Dorota Bród

Terminy konsultacji koordynatora:

terminy konsultacji na stronie domowej

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
MEK01	Student zna podstawowe pojęcia i twierdzenia teorii grafów	wykład, ćwiczenia problemowe	kolokwium	K-W01+ K-W05+ K-U02+ K-U04+	W01 W02 U03 U05
MEK02	Student zna podstawowe i zaawansowane metody teorii grafów	wykład, ćwiczenia problemowe	kolokwium	K-W04+ K-U02+ K-U03+ K-K02+ K-K07+	U01 U02 U03 U05 K01 K02 K06
MEK03	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+	W02 U03 U07 K01 K03 K04

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

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