Teoria grafów i sieci


Informacje ogólne

Typ:specjalnościowy
Kierunek:Informatyka studia licencjackie
Specjalność:Algorytmy i struktury danych
Semestr:5
Wymiar zajęć:30 godz wykładu, 15 godz ćwicz, 15 godz laboratorium
Punkty ECTS:6

Program

  • Definicje podstawowe
  • Drogi i cykle
  • Algorytmy dla ścieżek
  • Grafy eulerowskie
  • Grafy hamiltonowskie
  • Drzewa
  • Minimalne drzewa spinające
  • Spójność grafów
  • Planarność grafów
  • Kolorowanie wierzchołków grafów
  • Kolorowanie krawędzi grafów
  • Skojarzenia
  • Przepływy w sieciach
  • Grafowe problemy ramseyowskie

Sposób zaliczenia

egzamin pisemny z tresci poruszanych na wykładzie i ćwiczeniach

Literatura

  • R.J. Wilson: Wprowadzenie do teorii grafów, PWN 1998
  • R. Diesel: Graph Theory, Springer 2000
  • M. Kubale i in.: Optymalizacja dyskretna. Modele i metody kolorowania grafów, WNT 2003.