Uniwersytet im. Adama Mickiewicza w Poznaniu - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Teoria grafów

Informacje ogólne

Kod przedmiotu: 06-DTGRLM0 Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Teoria grafów
Jednostka: Wydział Matematyki i Informatyki
Grupy: Moodle - przedmioty Szkoły Nauk Ścisłych
Punkty ECTS i inne: 6.00 LUB 7.00 (w zależności od programu)
zobacz reguły punktacji
Język prowadzenia: (brak danych)
Pełny opis:

Wiele sytuacji z życia codziennego można przedstawić za pomocą tak zwanych grafów – zbioru punktów (wierzchołków) na płaszczyźnie, których pewne pary są połączone liniami (krawędziami). W takim kontekście grafy pojawiają się coraz częściej, w szczególności używane są już na wczesnych etapach edukacji dzieci. Teoria grafów jest stosunkowo młodą dyscypliną matematyczną, za początek której przyjmuje się opublikowanie przez Eulera, tak zwanego problemu mostów Królewieckich w XVIII wieku. Ze względu na wiele naturalnych zastosowań oraz na związki z przeżywającą bardzo burzliwy rozwój w ostatnich dziesięcioleciach informatyką, podstawy teorii grafów powinny należeć do elementarnego kanonu wiedzy matematyka i informatyka. W czasie reklamowanego kursu będziemy budować teorię grafów wychodząc od oczywistych i prostych intuicji, narzucających się zastosowań i skojarzeń. Pozwala to na łatwe zapamiętanie i zrozumienie podstawowych pojęć i formalnej terminologii. Przykładowo będziemy wymazywać krawędzie i wierzchołki grafu by zrozumieć pojęcie jego podgrafu, czy też by badać jego siłę spójności. Będziemy spacerować po grafach by zdefiniować pojęcia spaceru, szlaku, ścieżki i cyklu. Zdefiniujemy las i drzewa tak by nie było wątpliwości, że las jest zbiorem drzew, a drzewo miało strukturę „drzewiastą”. Pokażemy jakie warunki muszą być spełnione by w czasie naszego spaceru po grafie możliwe było odwiedzenie każdego jego wierzchołka lub przejście przez każdą jego krawędź. Będziemy kojarzyć w pary wierzchołki grafu by móc w sposób optymalny przydzielać stanowiska pracy kompetentnym pracownikom. Kolorowanie wierzchołków i kolorowanie krawędzi grafu posłużą nam do rozwiązywania problemu rozłożenia dostawy środków chemicznych w pomieszczeniach magazynu i problemu układania planu zajęć. Poznamy warunki, przy których będziemy w stanie narysować graf na płaszczyźnie tak by jego krawędzie przecinały się tylko w wierzchołkach. Pokażemy własności takich grafów, z których między innymi dowiemy się jaki jest związek między liczbami wierzchołków, krawędzi i ścian wielościanu i ile kolorów potrzebujemy do pokolorowania mapy.

Mimo, że na wykładzie budujemy teorię grafów od podstaw, nie zabraknie ciekawych i czasami zaskakujących zastosowań innych działów matematyki, a kilka dowodów to „perełki” matematycznego rozumowania.

Zajęcia w cyklu "Semestr letni 2019/2020" (zakończony)

Okres: 2020-02-24 - 2020-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 25 miejsc więcej informacji
Wykład, 30 godzin, 25 miejsc więcej informacji
Koordynatorzy: (brak danych)
Prowadzący grup: Jerzy Jaworski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie z notą
Wykład - Egzamin

Zajęcia w cyklu "Semestr letni 2020/2021" (zakończony)

Okres: 2021-03-01 - 2021-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 25 miejsc więcej informacji
Wykład, 30 godzin, 25 miejsc więcej informacji
Koordynatorzy: Jerzy Jaworski
Prowadzący grup: Jerzy Jaworski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie z notą
Wykład - Egzamin

Zajęcia w cyklu "Semestr letni 2021/2022" (jeszcze nie rozpoczęty)

Okres: 2022-02-24 - 2022-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: (brak danych)
Koordynatorzy: (brak danych)
Prowadzący grup: (brak danych)
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet im. Adama Mickiewicza w Poznaniu.