CZĘŚĆ 2: PRAWDOPODOBIEŃSTWO I KOMBINATORYKA

• Prawdopodobieństwo w matematyce dyskretnej

  Dział badający szansę zajścia zdarzeń w modelach opartych na zbiorach skończonych lub przeliczalnych, gdzie każdemu wynikowi przypisuje się liczbę z przedziału [0,1].

• Kombinatoryka

  Dział matematyki zajmujący się zliczaniem liczby możliwych konfiguracji (zbiorów, ciągów, podziałów) obiektów spełniających określone warunki.

• Permutacja

  Każdy liniowy (uporządkowany) ciąg wszystkich elementów danego zbioru; liczba permutacji n różnych elementów wynosi n! (n silnia).

• Wariacje (wariacje bez powtórzeń)

  Każdy uporządkowany ciąg k różnych elementów wybranych z n-elementowego zbioru.

  Wzór na liczbę wariacji bez powtórzeń:

  V(n, k) = n!/(n-k)!

  Przykład: Wybieramy 3 osoby z 10 na stanowiska: prezes, wiceprezes, sekretarz (kolejność ma znaczenie, nie można być na dwóch stanowiskach).

• Wariacje z powtórzeniami

  Każdy uporządkowany ciąg k elementów wybranych z n-elementowego zbioru, przy czym elementy mogą się powtarzać.

  Wzór na liczbę wariacji z powtórzeniami:

  W(n, k) = nᵏ

  Przykład: Tworzymy 4-cyfrowy kod PIN (cyfry mogą się powtarzać, kolejność ma znaczenie).

• Kombinacje (bez powtórzeń)

  Każdy nieuporządkowany zbiór k różnych elementów wybranych z n-elementowego zbioru.

  Wzór na liczbę kombinacji bez powtórzeń:

  C(n, k) = \(\binom{n}{k}\) = n!/[k!(n-k)!]

  Przykład: Wybieramy 3 osoby z 10 do komisji (kolejność nie ma znaczenia, nie można być w komisji dwa razy).

• Kombinacje z powtórzeniami

  Każdy nieuporządkowany zbiór k elementów wybranych z n-elementowego zbioru, przy czym elementy mogą się powtarzać.

  Wzór na liczbę kombinacji z powtórzeniami:

  C̄(n, k) = \(\binom{n+k-1}{k}\) = (n+k-1)!/[k!(n-1)!]

  Przykład: Kupujemy 5 cukierków w sklepie z 3 rodzajami cukierków (kolejność zakupu nie ma znaczenia, możemy kupić wiele takich samych).

CZĘŚĆ 3: PODSTAWOWE POJĘCIA GRAFOWE

• Graf

  Struktura matematyczna składająca się ze zbioru wierzchołków (punktów) oraz zbioru krawędzi (połączeń) między niektórymi parami tych wierzchołków.

• Graf prosty

  Graf nieskierowany, bez pętli i bez wielokrotnych krawędzi między tymi samymi wierzchołkami.

• Graf ogólny (multigraf)

  Graf, który może zawierać pętle i/lub wielokrotne krawędzie między tymi samymi wierzchołkami.

• Graf pełny (Kₙ)

  Graf prosty o n wierzchołkach, w którym każde dwa różne wierzchołki są połączone krawędzią.

• Graf regularny (stopnia r)

  Graf, w którym każdy wierzchołek ma ten sam stopień (liczbę incydentnych krawędzi), równy r.

• Stopień wierzchołka

  Liczba krawędzi incydentnych z danym wierzchołkiem (pętla liczy się podwójnie).

• Wierzchołek sąsiedni

  Dwa wierzchołki są sąsiednie, jeśli istnieje krawędź, która je łączy.

• Wierzchołek incydentny

  Wierzchołek jest incydentny do krawędzi, jeśli jest jednym z jej końców.

• Wierzchołek izolowany

  Wierzchołek, którego stopień jest równy zero (nie jest incydentny z żadną krawędzią).

• Graf skierowany (digraf)

  Graf, w którym każdej krawędzi przypisany jest kierunek (jest ona łukiem od jednego wierzchołka do drugiego).

• Graf nieskierowany

  Graf, w którym krawędzie nie mają kierunku i definiują jedynie symetryczną relację sąsiedztwa.

• Graf spójny

  Graf nieskierowany, w którym dla każdej pary wierzchołków istnieje ścieżka je łącząca.

• Graf niespójny

  Graf nieskierowany, który nie jest spójny, czyli składa się z co najmniej dwóch oddzielnych części (składowych spójności).

• Ścieżka (droga)

  Ciąg naprzemiennie ułożonych wierzchołków i krawędzi, rozpoczynający się i kończący wierzchołkiem, w którym każda krawędź łączy swojego poprzednika z następcą w ciągu.

• Ścieżka prosta

  Ścieżka, w której wszystkie wierzchołki (a co za tym idzie i krawędzie) są różne.

• Długość ścieżki

  Liczba krawędzi wchodzących w jej skład.

• Ścieżka nieprzemienna (w grafie skierowanym)

  Taka ścieżka, w której wszystkie łuki są skierowane w tę samą stronę, zgodnie z ich naturalnym kierunkiem w grafie.

• Cykl

  Ścieżka zamknięta, w której pierwszy i ostatni wierzchołek są identyczne, a wszystkie pozostałe wierzchołki i krawędzie są różne.

• Ścieżka Eulera

  Ścieżka w grafie, która przechodzi przez każdą krawędź dokładnie raz.

• Cykl Eulera

  Cykl będący jednocześnie ścieżką Eulera, czyli przechodzący przez każdą krawędź dokładnie raz i kończący się w punkcie startowym.

• Ścieżka Hamiltona

  Ścieżka w grafie, która przechodzi przez każdy wierzchołek dokładnie raz.

• Cykl Hamiltona

  Cykl w grafie, który przechodzi przez każdy wierzchołek dokładnie raz (z wyjątkiem powtórzenia początkowego jako końcowego).

• Twierdzenie Eulera o cyklu Eulera

  Spójny graf nieskierowany ma cykl Eulera wtedy i tylko wtedy, gdy stopień każdego jego wierzchołka jest liczbą parzystą.

CZĘŚĆ 4: ZAAWANSOWANE POJĘCIA GRAFOWE

• Twierdzenie Halla (o małżeństwach)

  W grafie dwudzielnym istnieje skojarzenie doskonałe obejmujące wszystkie wierzchołki z jednej partii wtedy i tylko wtedy, gdy dla każdego podzbioru tych wierzchołków liczba jego sąsiadów w drugiej partii jest nie mniejsza niż liczność tego podzbioru.

• Twierdzenie Kuratowskiego

  Graf jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu homeomorficznego z grafem pełnym K₅ lub z pełnym grafem dwudzielnym K₃,₃.

• Drzewo

  Spójny graf nieskierowany, który nie zawiera żadnych cykli. Równoważne definicje: 1) Każde dwa wierzchołki połączone dokładnie jedną drogą prostą. 2) Graf spójny, ale usunięcie jednej krawędzi powoduje, że przestaje być spójny. 3) Graf acykliczny, ale przestaje być acykliczny po dodaniu jakiejkolwiek krawędzi.

• Drzewo spinające (rozpinające) grafu

  Podgraf danego grafu, który jest drzewem i zawiera wszystkie jego wierzchołki.

• Izomorfizm grafów

  Relacja między grafami mówiąca, że są one strukturalnie identyczne; istnieje bijekcja między ich wierzchołkami zachowująca relację sąsiedztwa.

• Homeomorfizm grafów

  Dwa grafy są homeomorficzne, jeśli jeden można uzyskać z drugiego przez iterowane dzielenie krawędzi (wstawianie wierzchołków stopnia 2 na krawędziach) lub ich odwrotność.

• Graf planarny

  Graf, który można narysować tak, by żadne krawędzie się nie przecinały.

• Podgraf

  Graf otrzymany z danego grafu przez usunięcie pewnej liczby wierzchołków lub krawędzi (gdy usuwamy wierzchołek, usuwamy też krawędzie przyległe do niego).

• Ściany w grafie planarnym

  Obszary spójne na które płaszczyzna jest podzielona przez rysunek grafu planarnego. Jeden z tych obszarów jest ścianą zewnętrzną.

• Wzór Eulera dla grafów planarnych

  Dla dowolnego spójnego grafu planarnego zachodzi zależność: v + s – e = 2, gdzie v to liczba wierzchołków, e to liczba krawędzi, a s to liczba ścian (w tym zewnętrznej).

• Twierdzenie Cayleya

  Liczba drzew na oznaczonych n wierzchołkach wynosi nⁿ⁻².

• Problem 4 barw

  Każdy graf planarny można pokolorować 4 kolorami tak, by żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Odpowiednik: każdą mapę można pokolorować 4 kolorami.

CZĘŚĆ 5: TEORIA ZBIORÓW

Teoria zbiorów to podstawa matematyki dyskretnej. Poniższe podczęści szczegółowo opisują kluczowe operacje i pojęcia.

CZĘŚĆ 5.1: OPERACJE NA ZBIORACH

• Moc zbioru

  Liczba elementów należących do danego zbioru (dla zbiorów skończonych) lub ogólna „wielkość” zbioru; oznaczana jako |A| lub card(A).

• Suma zbiorów (A ∪ B)

  Zbiór zawierający wszystkie elementy, które należą do zbioru A lub do zbioru B (lub do obu jednocześnie).

• Iloczyn zbiorów (przekrój, A ∩ B)

  Zbiór zawierający tylko te elementy, które należą jednocześnie do zbioru A i do zbioru B.

• Różnica zbiorów (A \ B)

  Zbiór zawierający te elementy, które należą do zbioru A, ale nie należą do zbioru B.

• Dopełnienie zbioru (Aᶜ lub A’)

  Zbiór wszystkich elementów przestrzeni uniwersum, które nie należą do zbioru A.

• Podwójne dopełnienie

  Prawo mówiące, że dopełnienie dopełnienia zbioru A jest równe samemu zbiorowi A: (Aᶜ)ᶜ = A.

• Prawa De Morgana dla zbiorów

  • (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ — dopełnienie sumy jest iloczynem dopełnień.
  • (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ — dopełnienie iloczynu jest sumą dopełnień.

• Prawo tożsamości (dla zbiorów)

  Dla dowolnego zbioru A: A ∪ ∅ = A oraz A ∩ U = A, gdzie ∅ to zbiór pusty, a U to przestrzeń uniwersum.

CZĘŚĆ 5.2: PODZBIORY I ZBIÓR POTĘGOWY

• Podzbiór (A ⊆ B)

  Zbiór A jest podzbiorem zbioru B, jeśli każdy element zbioru A jest także elementem zbioru B.

• Zbiór potęgowy (P(A))

  Zbiór wszystkich podzbiorów danego zbioru A, łącznie ze zbiorem pustym i całym zbiorem A.

• Moc zbioru potęgowego

  Jeśli zbiór A ma n elementów, to jego zbiór potęgowy P(A) ma 2ⁿ elementów: |P(A)| = 2^|A|.

• Symbol Newtona w kontekście podzbiorów

  Liczba C(n,k) = n nad k oznacza liczbę k-elementowych podzbiorów (kombinacji bez powtórzeń) zbioru n-elementowego.

  Wzór: \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)

  Przykład: Liczba 3-elementowych podzbiorów zbioru 5-elementowego wynosi \(\binom{5}{3} = 10\).

CZĘŚĆ 5.3: MULTIZBIORY

• Multizbiór

  Uogólnienie pojęcia zbioru, które dopuszcza występowanie wielu identycznych kopii tego samego elementu; każdemu elementowi przypisuje się jego krotność (liczbę wystąpień).

• Suma multizbiorów

  Wynikiem jest multizbiór, w którym krotność każdego elementu jest sumą jego krotności w składanych multizbiorach.

• Iloczyn (przekrój) multizbiorów

  Wynikiem jest multizbiór, w którym krotność każdego elementu jest minimum z jego krotności w składanych multizbiorach.

• Różnica multizbiorów

  Wynikiem jest multizbiór, w którym krotność każdego elementu jest różnicą jego krotności w pierwszym i drugim multizbiorze (nie mniejszą niż zero).

• Moc multizbioru

  Suma krotności wszystkich jego elementów (łącznie z powtórzeniami), w przeciwieństwie do mocy zwykłego zbioru, która zlicza tylko różne elementy.

CZĘŚĆ 6: REKURENCJA I FUNKCJE TWORZĄCE

• Równanie rekurencyjne

  Definicja ciągu, w której kolejny wyraz jest określony przez wyrazy go poprzedzające. Cel: znaleźć wzór ogólny na n-ty wyraz.

• Przykład 1: Liczba permutacji

  Rekurencja: aₙ = n·aₙ₋₁

  Warunek początkowy: a₀ = 1

  Rozwiązanie: aₙ = n!

• Przykład 2: Wieże Hanoi

  Rekurencja: aₙ = 2aₙ₋₁ + 1

  Warunek początkowy: a₁ = 1

  Rozwiązanie: aₙ = 2ⁿ – 1

• Przykład 3: Proste na płaszczyźnie

  n prostych, żadne dwie równoległe, żadne trzy nie przecinają się w jednym punkcie

  Rekurencja: aₙ = aₙ₋₁ + n

  Warunki: a₀ = 1, a₁ = 2

  Rozwiązanie: aₙ = 1 + \(\frac{n(n+1)}{2}\) = 1 + \(\binom{n}{2}\)

• Przykład 4: Liczby Fibonacciego

  Rekurencja: Fₙ = Fₙ₋₁ + Fₙ₋₂

  Warunki początkowe: F₀ = 0, F₁ = 1

  Rozwiązanie: Fₙ = \(\frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right)^n – \frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2} \right)^n\)

• Metoda rozwiązywania rekurencji liniowych

  Dla równania: aₙ = Aaₙ₋₁ + Baₙ₋₂

  Rozwiązujemy równanie charakterystyczne: x² = Ax + B

  Jeśli α, β różne pierwiastki: aₙ = c₁αⁿ + c₂βⁿ

  c₁, c₂ wyznaczamy z warunków początkowych

• Zwykła funkcja tworząca

  Dla ciągu {aₙ}: \(f(x) = \sum_{n=0}^{\infty} a_n x^n\)

  Szereg potęgowy o promieniu zbieżności R ≥ 0

• Wykładnicza funkcja tworząca

  Dla szybko rosnących ciągów (np. aₙ = n!):

  \(f(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}\)

  Ma zwykle dodatni promień zbieżności

• Zastosowanie funkcji tworzących

  Znajdowanie wzoru ogólnego ciągu zadanego rekurencyjnie

  Przykład: aₙ = n·aₙ₋₁ → f(x) = 1/(1-x) → aₙ = n!

• Funkcja tworząca ciągu Fibonacciego

  \(f(x) = \frac{x}{1-x-x^2}\)

  Po rozłożeniu na ułamki proste otrzymujemy wzór na Fₙ

• Przydatne rozwinięcia funkcji tworzących

  \(\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n\) dla |x| < 1

  \((1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k\)

  \(e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}\)