1.Elementy zasady przeliczania z przykłądami: prawo mnożenia, dodawania i ogólne prawo mnożenia.

Prawo mnożenia (iloczynu):

1. Dla sończonych zbiorów S₁,S₂,…,S_k mamy

|S₁xS₂x…xS_k| = $\prod_{j = 1}^{k}{|Sj|}$.

1. Ogólniej, załózmy, że mamy zbiór ciągów (s₁,s₂,…,s_k) długości k o następującej strukturze. Jest n₁ możliwości wyboru s₁, dla ustalonych s₁ i s₂ sąn₃ możliwości wyboru s_3, i ogólnie, mając s_1,s₂,…,s_j-1 możemy wybrać s_j na n_j sposobów. Wówczas nasz zbiór ma n₁n₂*…*n_k elementów.

Prawo dodawania(sumy):

Niech S i T będązbiorami skończonymi.

1. Jeśli zbiory S i T sąrozłączne, tzn S∩T=⌀, to |S∩T|=|S|∪|T|.

2. Ogólnie, |S ∪T|=|S| + |T| -|S∩T|.

2.Na czym polega zasada bijeknij? Przykłady.

Fukncja wzajemnie jednoznaczna (bijekcja)- funkcja będąca jednocześnie funkcją różnowartościową i „na”.Innymi słowy, bijekcja to funkcja (relacja przyporządkowująca każdemu elementowi dziedziny dokładnie jeden element obrezu) taka, że każdemu elementowi obrazu odpowiada dokładnie jeden element dziedziny.

Np. dla każdego x podporządkowany jest jakiś y.np( f(x)= 5.)

3.Schematy wyboru: warjacje z powtórzeniami, bez powtórzeń.

a) Warjacje z powtórzeniami- Warjacją k-elementową z powtórzeniami utworzoną ze zbioru n-elementowego nazywamy każdy k-wyrazowy ciąg różnych lub nie różniących się elementów z tego zbioru. Z k-wyrazowymi warjacjami z powtórzeniami zbioru n-elementowego mamy do czynienia wówczas, gdy k razy wybieramy po jednym elemencie ze zwracaniem z danego zbioru. Z trzech danych elementów: a, b, c , można utworzyć następujące dwuelementowe wariacje z powtórzeniami: {a,a},{a,b},{a,c},{b,a},{b,b},{b,c},{c,a},{c,b},{c,c}.

Liczba k-wyrazowa warjacji z powtórzeniami zbioru n-elementowego wyraża się wzorem:

W_n^k = n^k.

b) Wariacje bez powtórzeń- Warjacją k-elementową bez powtórzeń utworzoną ze zbioru n-elementowego (k≤n) nazywamy każdy k-wyrazowy ciąg różnych elementów z tego zbioru.

Wariacje spełniająnastępujące warunki:

-obejmują jedynie określoną liczbę k spośrób danych n elementów,

-istotna jest kolejność elementów wariacji.

Z k- wyrazowymi warjacjami bez powtórzeń zbioru złożonego z n elementów mamy do czynienia, gdy k razy wybieramy bez zwracania po jednym elemencie z danego zbioru. n-wyrazowe warjacje bez powtórzeń zbioru n-elementowego są permutacjami tego zbioru.

Z trzech danych elementów: a, b,c, można utworzyć następujące dwuelementowe warjacje bez powtórzeń: {a,b},{a,c},{b,a},{b,c},{c,a},{c,b}.

Liczba k-wyrazowa warjacji bez powtórzeń zbioru n-elementowego wyraża sięwzorem:

$$V_{n}^{k} = \frac{n!}{\left( n - k \right)!}$$

4.Schematy wyboru:kombinacje z powtórzeniami, bez powtórzeń.

a) Kombinacja z powtórzeniami:

-Kolejność nie jest ważna

-elementy mogą się powtarzać

( _k^{n + k − 1})=(     _n − 1^{n + k − 1})

b)Kombinacja bez powtórzeń:

-kolejność nie jest ważna

-elementy nie mogą się powtarzać

C_n^k = (_kⁿ)=$\frac{n!}{k!\left( n - k \right)!}$

5.Problem ulic na Manchattanie.

Znajdujemy się w lewym dolnym rogu A i chcemy przejść najkrótszą drogą do prawego górnego rogu B. Na ile sposobów możemy to zrobić?

Każda najkrótsza droga z A do B składa się z 9 odcinków , w tym 6 w prawo i 3 w górę. Wyobraźmy sobie, że idąc taką drogą „kodujemy” ją zapisując ) po każdym odcinku w prawo i 1 po każdym odcinku w górę. Na przykład, droga na powyższym rysunku otrzyma kod

001010001

Operacja kodowania dróg ustala bijekcję między drogami a ciągami binarnymi długości 9 z dokładnie 3 jedynkami i 6 zerami. Z kolei tych ostatnich jest tyle ile jest 3-elementowych

$$(_{3}^{9}) = \frac{9*8*7}{3*2*1} = 84.$$

TWIERDZENIE :Liczba najkrótszych dróg z A do B w prostokątnej kracie o wymiarach k na l wynosi ( _k^k + l).

6.Trójkąt Pascala.

NA bokach trójkąta znajdują się liczby 1, a pozostałe powstają jako suma dwóch bezpośrednio znajdujących się nad nią.Liczby stojące w n-tym wierszu to kolejne współczynniki dwumianu Newtona- rozwinięcia (a+b)ⁿ.

Rys.

7.Dwumian Newtona

Potęgę dwumianu (x+y)ⁿ można rozwinąć w sumę jednomianów postaci ax^ky^l. W każdym z tych jednomianów współczynnik a jest dodatnią liczbą całkowitą, a wykładniki przy x oraz y sumują się do n. Współczynniki a przy jednomianach są symbolami Newtona i nazywane są współczynnikami dwumianowymi.

TWIERDZENE: Jeśli x,y są dowolnymi elementami dowolnego pierścienia przemiennego (np.liczby całkowite, wymierne, rzeczywiste, zespolone), to każdą naturalną potęgę dwumian x+y można rozłożyć na sumę postaci

(x+y)ⁿ=(₀ⁿ)xⁿ⁺(₁ⁿ)x^n-1y+(₂ⁿ)x^n-2y²+(₃ⁿ)x^n-3y³+…+(_nⁿ)yⁿ

Gdzie (_kⁿ) oznacza odpowiedni współczynnik dwumianowy.

Przyjmując x⁰=y⁰=1 (także w przypadku, gdy x=0 lub y=0) można powyższy wzór zapisać za pomocą notacji sumacyjnej

$$\left( x + y \right)^{n} = \sum_{k = 0}^{n}{\left( \frac{n}{k} \right)x^{k - k}y^{k}.}$$

8.Ciągi binarne. Pojęcie (m,n)-ciągu, serii, ciągów zdominowanych.

a) Ciąg zdominowany to taki ciąg binarny w którym na pierwszych i pozycjach znajduję się co najmniej tyle zer ile jedynek.

Zad.Ile jest ciągów binarnych, które składają się z 5 zer i 8 jedynek?

( ₈¹³)=( ₅¹³)=( _n^m + n)=( _m^m + n)

Jeżeli n >= m to liczba ciągów zdominowanych składających się z m jedynek i n zer wynosi:

(m,n)=$\frac{n + 1 - m}{n + 1}(_{\text{\ \ \ n}}^{n + m})\backslash n$b)Seria- Ciąg powtarzających się liczb

Np.1110000111

9.Liczby Catalana

Liczby Catalana są szczególnym ciągiem liczbowym. Ma on zastosowanie w wielu różnych aspektach kombinatoryki. Określony jest wzorem:

C_n=$\frac{1}{n + 1}(_{\text{\ n}}^{2n})$=$\ \frac{\left( 2n \right)!}{\left( n + 1 \right)!n!}$ dla n>=0

Z racji tego, że liczby Catalana spełniają poniższą zależność:

C_n=( _n²ⁿ)- ( _n + 1   ²ⁿ) dla n>=1

Widoczne jest, ze każda z liczb Catalana jest naturalną.

10.Równania rekurencyjne (przykłady-np.wieża w Hanoi).

ZALEŻNOŚĆ REKURENCYJNA

a_n=a_n-1+3 ->Wzór ogólny

a_n=1

a₂=a₁+3=1+3=4

a₃=a₂+3=4+3=7

a_n=3_n-2-> Wzór ogólny

a₃=3*3-2=7

a₅₌3*5-2=13

PROBLEM WIEZY W HANOI

a_n=2_n-1+1->wzór rekurencyjny

a₁=1

a₂=3

a₃=4

a₄=15

a_n=2ⁿ-1->wzór ogólny

(dopisać)

11.Ciąg Fibonacciego. Wzór rekurencyjny i ogólny

F_n=F_n-1+F_n-2 -> Wzór rekurencyjny

F_n=$\frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2})^{n} - \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^{n}$ ->Wzór ogólny

12.Liczby Lucasa.

Liczby Lucasa tworzone są w taki sam sposób jak liczby Fibonacciego, jednak początkowe liczby są równe 2 i 1. Każda następna liczba Lucasa jest sumą dwóch poprzednich.

Ciąg Lucasa to ciąg liczb określonych rekurencyjnie w sposób następujący:

L₀=2

L₁=1

L_n=L_n-1+L_n-2, dla n>1

Początkowe wartości ciągu Lucasa to:

2,1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364

Niech F_n oznacza n-tą liczbę Fibonacciego. W ciągu Lucasa zachodzą równości:

L_n=F_n-1+F_n+1

5F_n=Ln-1+L_n+1

F_2n=L_nF_n

13.

14.Definicja i przykłady grafów. Podstawowe pojęcia (między innymi graf prosty, spójny, oznakowany..)

Graf prosty – jest to graf bez krawędzi wielokątnych i pętli .

Graf spójny – jest to graf składający się z jednego kawałka , tzn taki którego dowolne dwa wierzchołki można połączyć drogą.

Stopień wierzchołka – liczba krawędzi których końcem jest ten wierzchołek

Trasa – jest to linia po której przedostaniemy się z jednego wierzchołka do innego

Droga - jest to trasa w której żaden wierzchołek nie występuje więcej niż jeden raz

Cykl – trasa „która zatacza koło”

Graf planarny – to graf który można narysować bez przecięć

15. Lemat o uścisku dłoni

Wynika z niego, że jeśli pewne osoby witają się, podając sobie dłonie, to łączna liczba uściśniętych dłoni jest parzysta - dlatego m że w każdym uściścisku uczestniczą dokładnie dwie dłonie. Natychmiastowym wnioskiem z lematu o uściskach dłoni jest to, że dowolnym grafie liczba wierzchołków o nieparzystych stopniach jest parzysta.

16.Tworzenie podgrafów

Podgrafem grafu G nazywamy graf, którego wszystkie wierzchołki należą do V(G), a krawędzie do E(G). Zatem graf pokazany na rysunku (1) jest podgrafem grafu(2), ale nie jest podgrafem grafu (3)

_(rys.25)

17.Macierz sąsiedztwa i incydencji grafu.

Macierz sąsiedztwa – jest macierz wymiaru nxm, której wyraz o indeksach i, j jest równy liczbie krawędzi łączących wierzchołek i z wierzchołkiem j.

Macierz incydencji – nazywamy macierz wymiaru nxm, której wyraz o indeksach i, j jest równy 1 ,jeśli wierzchołek i jest incydentalny z krawędzią j, i równy 0 w przeciwnym razie.

(_rys.26)

18.Szczególne rodzaje grafów(pełny, pusty, cykliczny itd..)

a) Graf pusty – jest go graf , którego zbiór krawędzi jest zbiorem pustym. Graf pusty mający n wierzchołków będziemy oznaczać symbolem N_n

_{(rys1 30s)}

b) Grafy pełne – jest to graf prosty, w którym każda para różnych wierzchołków jest połączona krawędzią. Graf pełny mający n wierzchołków oznaczamy symbolem K_n takie grafy mają n(n-1)/2 krawędzi

_{(rys2 30)}

c) Grafy cykliczne, grafy liniowe i koła

Graf spójny , regularny stopnia 2 nazywamy grafem cyklicznym. Graf cykliczny mający n wierzchołków oznaczamy symbolem C_n.

Graf otrzymany z grafu C_n przez usunięcie jednej krawędzi nazywamy grafem liniowym o n wierzchołkachi oznaczamy symbolem P_n.

Graf powstający z grafu C_n-1 przez połączenie każdego wierzchołka z nowym wierzchołkiem v nazywamy kołem o n wierzchołkach oznaczamy je symbolem W_n.

_{(rys3 30)}

d) Graf regularny – jest to graf którego każdy wierzchołek ma ten sam stopień.

_{(rys4 31)}

e) Grafy dwudzielne – jest go graf, którego wierzchołki można pokolorować dwoma kolorami, czarnym i białym w taki sposób, by każda krawędź łączyła wierzchołek czarny z wierzchołkiem białym

_{(rys1 32)}

f) Kostka - nazywamy graf którego wierzchołki odpowiadają ciągom (a₁,a₂,…,a_k) takim, że każdy wyraz a_i jest równy 0 lub 1, i którego krawędzie łączą ciągi różniące się dokładnie jednym wyrazem. Zauważmy, że grafem sześcianu jest graf Q₃. Graf Q_k ma 2^k wierzchołków i k*2^k-1 krawędzi oraz jest grafem regularnym stopnia k.

19.Spójność krawędziowa i wierzchołkowa grafu. Definicja , przykłady.

Spójność krawędziowa jest to najmniejsza liczba krawędzi które należy usunąć, by graf przestał być spójny. X(G)

_{(rys 5.5 44)}

Spójność wierzchołkowa- jest to najmniejsza liczba wierzchołków które należy usunąć, by graf przestał być spójny.

20.Grafy eulerowskie. Definicje, twierdzenia

Graf eulerowski – jest to graf spójny G , jeśli istnieje zamknięta ścieżka zawierająca każdą krawędź G. Taką ścieżkę nazywamy cyklem Eulera. Zauważmy, że ta definicja wymaga, by cykl Eulera przechodził przez każdą krawędź dokładnie jeden raz. Graf który nie jest grafem eulerowskim nazywamy grafem półeulerowskim, jeśli istnieje ścieżka zawierająca każdą krawędź grafu G.

_{(rys 47)}

Twierdzenienie – Graf spójny G jest grafem eulerowskim wtedy i tylko wtedy, gdy stopień każdego wierzchołka grafu G jest liczbą parzystą

Wniosek 1- Graf spójny jest grafem eulerowskim wtedy i tylko wtedy, gdy jego zbiór krawędzi można podzielić na rozłączne cykle.

Wniosek 2 – Graf spójny jest grafem półeulerowskim wtedy i tylko wtedy, gdy ma dokładnie dwa wierzchołki nieparzystych stopni

21.Grafy hamiltonowskie. Definicje, tw.Ore i Diraca.

Graf Hamiltona – graf o zamkniętej ścieżce przechodzącej dokładnie jeden raz przez każdy wierzchołek grafu G jest to graf cykliczny.

Graf półhamiltonowski, jeśli istnieje droga przechodząca dokładnie jeden raz przez każdy wierzchołek.

_{(rys1 53)}

Twierdzenie Ore – Jeśli graf prosty G ma n wierzchołków ( gdzie n>=3) oraz

deg(v)+deg(w)>=n

dla każdej pary wierzchołków niesąsiednich v i w , to grafG jest hamiltonowski

Twierdzenie Diraca- Jeśli w grafie prostym G, który ma n wierzchołków (gdzie n>=3) , deg(v)>=n/2 dla każdego wierzchołka v, to graf G jest hamiltonowsk

22.Drzewa i lasy. Własności

Lasem nazywamy graf nie zawierający cykli, a drzewem las spójny. Drzewa i lasy są grafami prostymi.

_{(rys 1 63)}

Twierdzenie1 – Niech T będzie grafem mającym n wierzchołków. Wtedy następujące warunki są równoważne:

a)T jest drzewem;

b)T nie zawiera cykli i ma n-1 krawędzi;

c)T jest grafem spójnym i ma n-1 krawędzi ;

d)T jest grafem spójnym i każda krawędź jest mostem;

e)każde dwa wierzchołki T są połączone dokładnie jedna drogą;

f) T nie zawiera cykli, ale po dodaniu dowolnej nowej krawędzi otrzymany graf ma dokładnie jeden cykl

Wniosek- Jeśli graf G jest lasem, który ma n wierzchołków i k składowych, to G ma n –k krawędzi.

Drzewo spinające – powstaje w wyniku usunięcia z grafu cyklicznego tylu krawędzi ze graf przestaje być cyklem a wszystkie krawędzie tego grafu są spięte ze sobą.

Twierdzenie2- Jeśli T jest lasem spinającym grafu T, to :

a)każde rozcięcie grafu G ma wspólną krawędź z T;

b)każdy cykl w grafie G ma wspólną krawędź z dopełnieniem T.

23.Macierzowe twierdzenie o drzewach i jego zastosowanie- zlicza liczbę drzew rozpinających grafu.

24.Tw.Cayleya i kody Pruefera.

Twierdzenie Cayleya- Istnieje n^n-2 różnych drzew oznakowanych mających n wierzchołków.

25.Kolorowanie grafów. Liczba chromatyczna, indeks chromatyczny. Przykłady.

Kolorowanie wierzchołków- Jeśli G jest grafem bez pętli, to mówimy, że G jest grafem k-kolorowalnym, jeśli każdemu wierzchołkowi możemy przypisać jeden z k kolorów w taki sposób, by sąsiednie wierzchołki miały różne kolory (n-1)

Liczbą chromatyczną grafu G nazywamy liczbę x(G) równą najmniejszej możliwej liczbie kolorów potrzebnych do legalnego pokolorowania wierzchołków grafu G

Indeks chromatyczny grafu X(G)- określa minimalną liczbę kolorów wystarczającądo prawidłowego pokolorowania krawędzi grafu.

26.Wielomiany chromatyczne

Wielomian pozwalający obliczyć ilość minimalną kolorów , którą można pokolorować wierzchołki

Linia

Drzewo k(k-1)^n-1 T_n

Graf pełny –k(k-1)(k-2)…(k-n+1) K_n

27.Zagadnienei najkrótszej drogi.

Jedziemy Po kolei i szukamy najkrótszych dróg

28.Problem chińskiego listonosza

Polega na tym, by listonosz , który musi doręczyć pocztę, przeszedł jak najkrótszą łączną drogę i powrócił do punktu wyjścia. Jeśli graf jest eulerowskim, to każdy cykl Eulera jest żądaną trasą zamkniętą. Suma krawędzi (wag) musi być jak najmniejsza

29.Problem najkrótszych połączeń(wyznaczanie drzewa spinającego o najmniejszej sumie wag)

Twierdzenie – Niech G będzie grafem spójnym mającym n wierzchołków. Wtedy następująca konstrukcja daje rozwiązanie problemu najkrótszych połączeń

a)niech e₁ będzie krawędzią o najmniejszej wadze;

b)definiujemy krawędzie e₂,e₃,…e_n-1, wybierając za każdym razem nową krawędź o najmniejszej możliwej wadze, która nie tworzy cyklu z dotychczas wybranymi krawędziami e_i. Podgraf T grafu G, którego krawędziami są krawędzie e₁,…,e_n-1, jest szukanym drzewem spinającym.

30.Problem komiwojażera

Problem polega na tym aby komiwojażer, który chce odwiedzić kilka miast i powrócić do punktu wyjscia znalazł drogę o najkrótszej łącznej długości.

Szukamy drogi o najmniejszych wagach