Teoria grafów - TGR 2020L


Zagadnienia egzaminacyjne



  1. Definicje: grafu, grafu prostego, grafu pełnego, podgrafu, dopełnienia grafu, podgrafów indukowanych.
  2. Izomorfizm grafów.
  3. Macierze incydencji i przylegania.
  4. Podaj i udowodnij twierdzenie o sumie stopni wierzchołków grafu.
  5. Pojęcia spaceru, segmentu spaceru, szlaku, ścieżki, domkniętego szlaku, obchodu, cyklu.
  6. Składowe spójności grafu. Podaj i udowodnij twierdzenie o oszacowaniach liczby krawędzi.
  7. Podaj i udowodnij warunek konieczny i dostateczny na to by graf był grafem dwudzielnym.
  8. Definicje lasu i drzewa. Podaj i udowodnij twierdzenia o liczbie krawędzi drzewa i lasu.
  9. Krawędzie cięcia grafu. Podaj i udowodnij warunki konieczne i dostateczne.
  10. Podaj określenie drzewa (lasu) za pomocą pojęcia krawędzi cięcia i udowodnij odpowiednie twierdzenie.
  11. Jakie grafy zawierają rozpięte drzewo? Udowodnij odpowiednie twierdzenie.
  12. Związek między cyklami i drzewami rozpiętymi. Podaj i udowodnij odpowiedni fakt.
  13. Liczba rozpiętych drzew danego grafu. Dowód wzoru rekurencyjnego.
  14. Wzór Cayleya i kod Prüfera.
  15. Spójność wierzchołkowa i krawędziowa.
  16. Zależności między spójnością wierzchołkową, spójnością krawędziową i minimalnym stopniem. Podaj i udowodnij odpowiednie twierdzenie.
  17. Podaj i udowodnij twierdzenie Whitney'a o grafie 2-spójnym i podaj jego uogólnienia (podaj twierdzenia Mengera)
  18. Podaj i udowodnij warunek konieczny i dostateczny na to by graf był grafem Eulera.
  19. Podaj i udowodnij warunek konieczny i dostateczny na to by graf był grafem półeulerowskim.
  20. Podaj i udowodnij warunek konieczny na to by graf był grafem Hamiltona.
  21. Podaj i udowodnij warunek konieczny na to by graf był grafem półhamiltonowskim.
  22. Podaj i udowodnij warunki dostateczne na to, by graf był grafem Hamiltona.
  23. Pojęcie skojarzenia grafu, k-faktora i k-faktoryzowalności.
  24. Podaj i udowodnij twierdzenie Berge'a o skojarzeniu największym i ścieżkach M-zasilających .
  25. Podaj i udowodnij twierdzenie Halla.
  26. Podaj i udowodnij twierdzenie o małżeństwach i wniosek o 1-faktoryzacji.
  27. Związek między pokryciem i skojarzeniem danego grafu. Podaj i udowodnij odpowiednie twierdzenie.
  28. Podaj i udowodnij twierdzenie Königa.
  29. Podaj twierdzenie Tutte'a o skojarzeniu doskonałym. Podaj szkic dowodu.
  30. Podaj związki między zbiorami niezależnymi i pokryciami wierzchołkowymi.
  31. Podaj związki między skojarzeniami a pokryciami krawędziowymi.
  32. Podaj i udowodnij twierdzenie Gallai.
  33. Podaj i udowodnij twierdzenie Turana.
  34. Podaj i udowodnij twierdzenie o oszacowaniu górnym liczb Ramseya.
  35. Podaj i udowodnij twierdzenie o oszacowaniu dolnym liczb Ramseya.
  36. Kolorowanie wierzchołków grafu. Podaj i udowodnij twierdzenie o minimalnym stopniu grafu k-krytycznego.
  37. Podaj i udowodnij oszacowanie górne na liczbę chromatyczną grafu. Podaj twierdzenie Brooksa.
  38. Kolorowanie krawędzi grafu. Podaj twierdzenie Vizinga.
  39. Podaj i udowodnij twierdzenie o indeksie chromatycznym grafu dwudzielnego (podaj odpowiednie pojęcia i lematy).
  40. Grafy planarne, grafy płaskie. Grafy dualne grafów płaskich. Podaj twierdzenie Kuratowskiego.
  41. Podaj i udowodnij wzór Eulera.
  42. Podaj i udowodnij wnioski ze wzoru Eulera o oszacowaniach na liczbę krawędzi.
  43. Podaj i udowodnij wniosek ze wzoru Eulera o minimalnym stopniu grafu planarnego.
  44. Udowodnij, że grafy Kuratowskiego nie są planarne.
  45. Podaj i udowodnij twierdzenie o kolorowaniu mapy dwoma kolorami.
  46. Podaj i udowodnij twierdzenie o kolorowaniu map sześciennych trzema kolorami.
  47. Podaj i udowodnij fakt o kolorowaniu mapy sześcioma kolorami.
  48. Podaj i udowodnij twierdzenie o kolorowaniu mapy pięcioma kolorami.
  49. Podaj twierdzenie o liczbie chromatycznej grafów planarnych i odpowiednie równoważne mu twierdzenia.
      Uwaga: Sformułowanie "Podaj i udowodnij twierdzenie A" oznacza, że powinni Państwo znać to twierdzenie i jego dowód w zakresie, w którym został podany na wykładzie. Nieco inne znaczenie ma zwrot "podaj twierdzenie A"; w tym przypadku wymagał będę sformułowania twierdzenia i zrozumienia co ono oznacza (ewentualnie omówienia niektórych jego zastosowań).


Uwagi, pytania:
Data ostatniej modyfikacji: 3.02.2020 r.