Uniwersytet w Białymstoku - Centralny System Uwierzytelniania
Strona główna

Wprowadzenie do teorii grafów 360-MS1-2ZTG
Ćwiczenia (CW) Rok akademicki 2021/22

Informacje o zajęciach (wspólne dla wszystkich grup)

Liczba godzin: 30
Limit miejsc: (brak limitu)
Zaliczenie: Zaliczenie na ocenę
Literatura:

Literatura obowiązkowa:

1) R. J. Wilson, Wprowadzenie do teorii grafów, PWN Warszawa 1998,

2) N. Deo, Teoria grafów i jej zastosowania w technice i informatyce, PWN Warszawa 1980

Literatura uzupełniająca:

1) R. Diestel, Graph Theory, Springer Verlag, 2000

2) Ch. Godsil, Algebraic Graph Theory, Springer 2001

Efekty uczenia się:

Efekty kształcenia w ramach realizacji przedmiotu:

Zna podstawowe pojęcia teorii grafów; umie podać konkretne przykłady różnych poznanych typów grafów i wyznaczać ich parametry. - kolokwium zaliczeniowe; domowe prace rachunkowe/problemowe; prezentacje rozwiązań zadań na zajęciach.

Zna pojęcia drogi, cyklu, grafu eulerowskiego i hamiltonowskiego oraz podstawowe twierdzenia dotyczące tych zagadnień, potrafi te twierdzenia zastosować do konkretnych przykładów i klas grafów. - kolokwium zaliczeniowe; domowe prace rachunkowe/problemowe; prezentacje rozwiązań zadań na zajęciach; obserwacja ciągła aktywności studenta.

Uzyskuje podstawy metodologiczne do stosowania teorii grafów w zagadnieniach praktycznych i rozwiązywania jej elementarnych zagadnień - obserwacja ciągła aktywności studenta.

Metody i kryteria oceniania:

Zaliczenie na ocenę na podstawie zadań rozwiązywanych samodzielnie oraz aktywności za zajęciach.

Zakres tematów:

Treść zajęć:

Definicja i przykłady grafów: grafy proste, regularne, skierowane, nieskończone. Reprezentacja macierzowa i spójność. Drogi i cykle. Grafy eulerowskie i hamiltonowskie: algorytm Fleury'ego, warunki konieczne i wystarczające. Grafy z wagami: problem najkrótszych połączeń, problem chińskiego listonosza i komiwojażera. Drzewa - własności, zliczanie drzew i ich zastosowania. Grafy planarne i twierdzenie Eulera. Kolorowanie grafów, map i zagadnienie czterech barw. Grafy dualne. Twierdzenie Halla o kojarzeniu małżeństw.

Metody dydaktyczne:

Metody dydaktyczne: dowodzenie prost(sz)ych zależności numerycznych i własności grafów i drzew, konsultacje, praca nad literaturą, rozwiązywanie zadań domowych, dyskusje w grupach problemowych.

Grupy zajęciowe

zobacz na planie zajęć

Grupa Termin(y) Prowadzący Miejsca Liczba osób w grupie / limit miejsc Akcje
1 każdy wtorek, 8:15 - 9:45, sala 3004
Krzysztof Petelczyc 5/ szczegóły
Wszystkie zajęcia odbywają się w budynku:
Budynek Wydziału Matematyki i Wydziału Informatyki - Kampus
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet w Białymstoku.
ul. Świerkowa 20B, 15-328 Białystok tel: +48 85 745 70 00 (Centrala) https://uwb.edu.pl kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)