Cel kształcenia i wykaz literatury

Główny cel kształcenia: Zapoznanie studentów z wybranymi zagadnieniami dotyczącymi teorii digrafów i sieci

Ogólne informacje o zajęciach: Tematyka zajęć została wybrana przez studentów.

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	R.J. Wilson	Wprowadzenie do teorii grafów	PWN, Warszawa.	2000
2	R. Diestel	Graph Theory	Springer GTM 173, 5th edition.	2016
3	A. Włoch, I. Włoch	Matematyka dyskretna. Podstawowe metody i algorytmy teorii grafów	Oficyna Wydawnicza Politechniki Rzeszowskiej, Rzeszów .	2017

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

1	R.J. Wilson	Wprowadzenie do teorii grafów	PWN, Warszawa.	2000
2	R. Diestel	Graph Theory	Springer GTM 173, 5th edition.	2016
3	A. Włoch, I. Włoch	Matematyka dyskretna. Podstawowe metody i algorytmy teorii grafów	Oficyna Wydawnicza Politechniki Rzeszowskiej, Rzeszów .	2017

Literatura do samodzielnego studiowania

1

J. Bang-Jensen, G.Z. Gutin

Digraphs: theory, algorithms and applications

Springer Science & Business Media.

2008

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: Znajomość podstaw matematyki dyskretnej, kombinatoryki i teorii liczb

Wymagania wstępne w kategorii Umiejętności: Student zna, rozumie i potrafi stosować pojęcia z zakresu matematyki dyskretnej.

Wymagania wstępne w kategorii Kompetencji społecznych: Student posiada umiejętność samodzielnego i zespołowego uczenia się, ma świadomość poziomu własnej wiedzy oraz rozumie potrzebę samokształcenia.

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 skierowanych	wykład, ćwiczenia	zaliczenie cz. pisemna	K_W01+ K_W02++ K_W03+ K_W04+ K_W05+ K_W06+ K_U01+	X1A_W1+ X1A_W2+ X1A_W3+ X1A_U6+
02	Student zna wybrane algorytmy w digrafach związane z optymalizacją	wykład, ćwiczenia	zaliczenie cz. pisemna	K_W02+ K_W03+ K_W04+ K_W05+ K_W06+ K_U01+	X1A_W2+ X1A_W3+ X1A_U6+
03	Student potrafi użyć metod teorii digrafów do rozwiązywania problemów dyskretnych	wykład, ćwiczenia	zaliczenie cz. pisemna,	K_W01+ K_W04+ K_W05+	X1A_W1+ X1A_W3+

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
5	TK01	Przypomnienie podstawowych definicji i twierdzeń teorii grafów. Wprowadzenie do teorii digrafów. Spójność i silna spójność digrafów, drzewa skierowane, turnieje, cykle Eulera i Hamiltona w digrafach.	W01-W10, C01-C05	MEK01 MEK02 MEK03
5	TK02	Digrafy ważone. Algorytmy wyznaczające odległości w digrafach. Przeszukiwanie wszerz, algorytm Dijkstry, algorytm Bellman'a-Ford'a-Moore'a. Promień, średnica i królowie w digrafach. Problem komiwojażera, problem chińskiego listonosza.	W11-W20, C06-C10	MEK01 MEK02 MEK03
5	TK03	Sieci i przepływy. Sieć residualna. Maksymalny przepływ w sieci. Algorytm Forda-Fulkersona. Wyznaczanie najtańszego przepływu. Algorytm Busackera-Gowena. Problem chińskiego listonosza, wyznaczanie maksymalnego skojarzenia w grafie dwudzielnym.	W21-W30, C11-C13	MEK01 MEK02 MEK03

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 5)		Godziny kontaktowe: 30.00 godz./sem.	Uzupełnienie/studiowanie notatek: 6.00 godz./sem.
Ćwiczenia/Lektorat (sem. 5)	Przygotowanie do ćwiczeń: 15.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.
Konsultacje (sem. 5)	Przygotowanie do konsultacji: 6.00 godz./sem.	Udział w konsultacjach: 3.00 godz./sem.
Zaliczenie (sem. 5)

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 co najmniej 50% punktów z kolokwium. Ocenę końcową z ćwiczeń można podwyższyć przez aktywność 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: tak

1	P. Bednarz; M. Pirga	On Proper 2-Dominating Sets in Graphs	2024
2	P. Bednarz	Relations between the existence of a (2 − d)-kernel and parameters γ2(G), α(G)	2022
3	P. Bednarz	On (2-d)-Kernels in the Tensor Product of Graphs	2021
4	P. Bednarz; A. Michalski	On Independent Secondary Dominating Sets in Generalized Graph Products	2021
5	P. Bednarz; N. Paja	On (2-d)-Kernels in Two Generalizations of the Petersen Graph	2021