Cel kształcenia i wykaz literatury

Główny cel kształcenia: Celem kursu jest zapoznanie studentów z podstawami teorii grafów i sieci.

Ogólne informacje o zajęciach: Zapoznanie studentów z metodami teorii grafów i sieci w aspekcie teoretycznym i algorytmicznym oraz wyznaczanie własności grafów przy pomocy oprogramowania.

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	A. Włoch, I. Włoch	Matematyka dyskretna	Oficyna Wydawnicza Politechniki Rzeszowskiej, Rzeszów .	2017
2	R. J. Wilson	Wprowadzenie do teorii grafów	PWN Warszawa.	2000

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

1

M. Sysło, N. Deo, J. Kowalik

Algorytmy optymalizacji dyskretnej

PWN Warszawa .

1999

Literatura do samodzielnego studiowania

1

R. Diestel

Graph Theory

Springer-Verlag, Heidelberg, New York.

2005

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 analizy matematycznej i rachunku macierzowego.

Wymagania wstępne w kategorii Umiejętności: Umiejętność posługiwania się aparatem matematycznym w zakresie analizy matematycznej i algebry.

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 PRK
01	Zna podstawowe pojęcia, twierdzenia i algorytmy teorii grafów.	wykład, laboratorium	zaliczenie pisemne, praca przy komputerze	K_W04+++ K_U29+ K_K01+	P6S_KK P6S_UK P6S_UW P6S_WG P6S_WK
02	Potrafi zbudować model problemu i rozwiązać problem dyskretny.	wykład, laboratorium	zaliczenie pisemne, praca przy komputerze	K_W02+ K_W03+ K_W05+ K_U29+++ K_K01+	P6S_KK P6S_UK P6S_UW P6S_WG P6S_WK
03	Potrafi w wybranym oprogramowaniu generować grafy, wyznaczać ich własności i dokonywać wizualizacji	laboratorium	zaliczenie pisemne, praca przy komputerze	K_W01+ K_W03+ K_U02+ K_K01+ K_K02+ K_K05+	P6S_KK P6S_KO P6S_KR P6S_UU P6S_UW P6S_WG P6S_WK

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	Pojecie grafu, interpretacja geometryczna. Podstawowe definicje i oznaczenia teorii grafów. Rodzaje grafu, potęga i dopełnienie grafu, grafy ważone, produkty dwóch grafów. Izomorfizm grafów. Macierzowa reprezentacja grafu: macierz sąsiedztw, macierz incydencji.	W01, L01	MEK01 MEK02 MEK03
3	TK02	Drogi i cykle w grafach. Spójność grafu. Grafy Eulera i grafy Hamiltona. Problem komiwojażera.	W02, L02	MEK01 MEK02 MEK03
3	TK03	Drzewa. Definicje i podstawowe własności. Drzewa binarne. Metody kodowania drzew, twierdzenie Cayley’a. Drzewa rozpinające, metody wyznaczania minimalnego drzewa rozpinającego.	W03, L03, L04	MEK01 MEK02 MEK03
3	TK04	Topologiczna teoria grafów. Grafy planarne. Grafy na powierzchniach.	W04, L04	MEK01 MEK02 MEK03
3	TK05	Niezależność w grafie. Zbiory niezależne. Skojarzenia.	W05, L05	MEK01 MEK02 MEK03
3	TK06	Kolorowanie grafów. Kolorowanie wierzchołków. Kolorowanie krawędzi.	W06, L06	MEK01 MEK02 MEK03
3	TK07	Grafy skierowane-(digrafy) podstawowe pojęcia. Digrafy Eulera. Turnieje. Sieci. Przepustowość i przepływ. Twierdzenia minimaksowe.	W07, L07	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)		Godziny kontaktowe: 15.00 godz./sem.
Laboratorium (sem. 3)	Przygotowanie do laboratorium: 5.00 godz./sem. Przygotowanie do kolokwium: 5.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.
Konsultacje (sem. 3)		Udział w konsultacjach: 2.00 godz./sem.
Zaliczenie (sem. 3)	Przygotowanie do zaliczenia: 5.00 godz./sem.	Zaliczenie pisemne: 2.00 godz./sem. Inne: 1.00 godz./sem.

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.
Laboratorium	Zaliczenie przy komputerze.
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; A. Szynal-Liana	Bihyperbolic Numbers of the Fibonacci Type and Triangular Matrices (Tables)	2024
2	P. Bednarz; M. Pirga	On Proper 2-Dominating Sets in Graphs	2024
3	P. Bednarz	Relations between the existence of a (2 − d)-kernel and parameters γ2(G), α(G)	2022
4	P. Bednarz	On (2-d)-Kernels in the Tensor Product of Graphs	2021
5	P. Bednarz; A. Michalski	On Independent Secondary Dominating Sets in Generalized Graph Products	2021
6	P. Bednarz; N. Paja	On (2-d)-Kernels in Two Generalizations of the Petersen Graph	2021