Cel kształcenia i wykaz literatury

Główny cel kształcenia: Celem kursu jest 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 CAS Maxima.

Ogólne informacje o zajęciach:

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	A. Włoch, I. Włoch	Matematyka dyskretna- podstawowe metody i algorytmy teorii grafów	Oficyna Wydawnicza Politechniki Rzeszowskiej, Rzeszów.	2004.
2	K. Ross, Ch. Wright	Matematyka dyskretna	PWN, Warszawa.	1996.
3	V. Bryant	Aspekty kombinatoryki	WNT, Warszawa.	2005.
4	P.N. de Souza, R.J. Fateman, J. Moses, C. Yapp	The Maxima Book	http://maxima.sourceforge.net.
5	R.J. Wilson	Wprowadzenie do teorii grafów	PWN, Warszawa.	2000.

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

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

Wymagania wstępne w kategorii Wiedzy: Znajomość podstaw logiki i algebry liniowej.

Wymagania wstępne w kategorii Umiejętności:

Wymagania wstępne w kategorii Kompetencji społecznych:

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 i sieci. Posługuje się pojęciem grafu i sieci.	wykład, ćwiczenia, laboratorium	zaliczenie pisemne, praca przy komputerze	K_W01+ K_W03+ K_U02+ K_U03+ K_K01+ K_K02+ K_K05+	P6S_KK P6S_KO P6S_UW P6S_WG
02	Potrafi zbudować model problemu i rozwiązać problem dyskretny	wykład, ćwiczenia, laboratorium	zaliczenie pisemne,	K_W01+ K_W03+ K_U02+ K_U03+ K_K01+ K_K02+ K_K05+	P6S_KK P6S_KO P6S_UW P6S_WG
03	Potrafi w CAS Maxima generować grafy, wyznaczać ich własności i dokonywać wizualizacji	laboratorium	zaliczenie praktyczne przy komputerze	K_W01+ K_W03+ K_U02+ K_U03+ K_K01+ K_K02+ K_K05+	P6S_KK P6S_KO P6S_UW P6S_WG

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
2	TK01	Pojęcie grafu, interpretacja geometryczna. Podstawowe pojęcia teorii grafów. Rodzaje grafów, potęga grafu, dopełnienia grafu, grafy ważone, produkty grafów. Izomorfizm grafów. Macierzowa reprezentacja grafu, macierz sąsiedztw, macierz incydencji.	W1-W3, C1-C3, L1-L3	MEK01 MEK02 MEK03
2	TK02	Drogi i cykle w grafach. Spójność grafu. Grafy Eulera i grafy Hamiltona. Problem komiwojażera.	W4-W5, C4-C5, L4-L5	MEK01 MEK02 MEK03
2	TK03	Drzewa- definicja i podstawowe własności. Drzewa binarne, Drzewa rozpinające Metody kodowania drzew. Zliczanie drzew. Twierdzenie Cayleya. Drzewa jako systemy struktur danych. Zastosowania.	W6-W7, C6-C7, L6-L7	MEK01 MEK02 MEK03
2	TK04	Topologiczna teoria grafów. Grafy planarne. Grafy na powierzchniach. Parametry grafów planarnych.	W8, C8, L8	MEK01 MEK02 MEK03
2	TK05	Niezależność w grafie. Zbiory niezależne, liczba niezależności. Związki z liczbami Fibonacciego. Skojarzenia, twierdzenie Halla. Zastosowania - zagadnienia przydziału. Dominowanie w grafie. Zbiory dominujące, liczba dominowania. Pokrycia w grafie.	W9-W10, C9-C10, L9-L10	MEK01 MEK02 MEK03
2	TK06	Kolorowanie grafów. Kolorowanie wierzchołków, kolorowanie krawędzi. Liczba chromatyczna, indeks chromatyczny. Wielomian chromatyczny. Twierdzenie o 4 barwach.	W11, C11, L11	MEK01 MEK02 MEK03
2	TK07	Grafy skierowane-(digrafy) podstawowe pojęcia. Digrafy Eulera. Turnieje.	W12, C12, L12	MEK01 MEK02 MEK03
2	TK08	Sieci. Przepustowość i przepływ. Twierdzenia minimaksowe.	W13-W14, C13-C14, L13-L14	MEK01 MEK02 MEK03
2	TK09	Zastosowania teorii grafów i sieci w analizie danych.	W15, C-15, L15	MEK01 MEK02 MEK03

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 2)	Przygotowanie do kolokwium: 3.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.
Ćwiczenia/Lektorat (sem. 2)	Przygotowanie do ćwiczeń: 5.00 godz./sem. Przygotowanie do kolokwium: 2.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.
Laboratorium (sem. 2)	Przygotowanie do laboratorium: 3.00 godz./sem. Przygotowanie do kolokwium: 2.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.
Konsultacje (sem. 2)		Udział w konsultacjach: 2.00 godz./sem.
Zaliczenie (sem. 2)	Przygotowanie do zaliczenia: 10.00 godz./sem.	Zaliczenie pisemne: 3.00 godz./sem. Inne: 2.00 godz./sem.

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

Forma zajęć	Sposób wystawiania oceny podsumowującej
Wykład
Ćwiczenia/Lektorat
Laboratorium
Ocena końcowa	Warunkiem zaliczenia przedmiotu jest uzyskanie pozytywnej oceny z kolokwium z ćwiczeń, praktycznego zaliczenia przy komputerze na laboratorium. Ocena końcowa jest średnią arytmetyczną poszczególnych ocen.

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