Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Matematyka Dyskretna
Koordynator przedmiotu:
dr Tomasz Traczyk
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Matematyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
2 / rok ak. 2011/2012
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia30h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Elementy logiki i teorii mnogości
Limit liczby studentów:
Cel przedmiotu:
do uzupełnienia
Treści kształcenia:
Pojęcie grafu. Wierzchołki i krawędzie. Stopień wierzchołka, droga, cykl, grafy spójne i niespójne, składowe grafu. Graf pełny. Dopełnienie grafu. Podgrafy. Podgraf indukowany. Podgraf rozpinający. Ściągnięcie elementarne. Pojęcie minora topologicznego i minora grafu. Zagadka mostów królewieckich. Cykl i droga Eulera. Twierdzenie Eulera. Drzewa. Korzeń, gałęzie i liście. Twierdzenie charakteryzacyjne dla drzew. Drzewa rozpinające. Grafy ważone. Algorytm Kruskala. Spójność grafu. Spójność wierzchołkowa i krawędziowa. Twierdzenie Mengera. Twierdzenie małżeńskie Halla. Cykle Hamiltona w grafach. Proste warunki konieczne i warunki dostateczne istnienia cyklu Hamiltona w grafie. Twierdzenia klasyczne - Diraca, Ore, Posa. Pojęcie k-domknięcia grafu. Twierdzenie Bondy'ego i Chvatala. Niezależne zbiory wierzchołków/krawędzi. Pokrycia wierzchołkowe/krawędziowe. Faktory i faktoryzacja. Twierdzenie Tutte'a o istnieniu 1-faktora. Kolorowanie grafów. Liczba chromatyczna i indeks chromatyczny. Twierdzenie Szekeresa-Wilfa. Twierdzenie Brooksa. Twierdzenie Vizinga o indeksie chromatycznym. Grafy planarne. Wzór Eulera. Twierdzenie Kuratowskiego. Twierdzenie Ramsey'a. Turnieje. Twierdzenia Landaua. Twierdzenie Redei. Twierdzenie Mosera. Matroidy. Definicja i podstawowe pojęcia. Twierdzenie Rado-Edmondsa.
Metody oceny:
Obecność na ćwiczeniach jest obowiązkowa. W trakcie semestru odbędą się dwa kolokwia po 20 punktów. Za aktywność na zajęciach można otrzymać do 10 punktów. Egzamin końcowy jest wart 50 punktów. Na kolokwiach i na egzminie końcowym nie wolno korzystać z żadnych materiałów pomocniczych Ostateczna ocena będzie wystawiana na podstawie łącznej punktacji według skali: 51-60 3   61-70 3.5   71-80 4   81-90 4.5     91-100 5           W terminie poprawkowym ocena będzie wystawiana według tej samej skali (proporcjonalnie) lecz bez uwzględniania punktów z ćwiczeń
Egzamin:
Literatura:
brak danych
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się