Indukcja matematyczna :metoda dowodzenia twierdzeń; zazwyczaj twierdzenia te dotyczą liczb naturalnych, ale nie tylko; poprawność jej wynika z dobrego uporządkowania liczb naturalnych (czyli z zasady minimum)

Zasada Minimum (ZMin): Dowolny niepusty podzbiór S zbioru liczb naturalnych N ma w sobie liczbę najmniejszą

Przykład 1 (Francesco Maurolio - 1575) Suma początkowych n liczb nieparzystych wynosi n do kwadratu. 1 + 3 + 5 + … + (2n-1)=n^2 Przeprowadzone rozumowanie wykazuje, że Jeśli Z jest jakimś zbiorem liczb naturalnych, w którym jest zero oraz Z wraz z każdą liczbą naturalną k zawiera również kolejną liczbę k+1

(tzn. dla każdego k należącego do Z zachodzi, że k+1 należy do Z to wówczas Z musi zawierać wszystkie liczby naturalne, tzn Z=N.

Przykład 2 0 + 1 + 2 + … + n = n(n+1)/2 dla n >= 0

Przykład 3 0^2 + 1^2 + 2^2 +3^2 + … +(n-1)^2 +n^2 = n(n+1)(2n+1)/6, Czasami jest tak, że pewna własność nie dotyczy wszystkich liczb naturalnych, ale prawie wszystkich (tzn. wszystkich poza być może pewną skończoną liczbą wartości początkowych.

Zasada Indukcji Matematycznej (ZIM) Jeżeli Z zawiera się w zbiorze liczb naturalnych N :w którymko należy do Z oraz Z wraz z każdą liczbą naturalną k >= ko zawiera również kolejną liczbę k+1 (tzn. dla każdego k >= ko zachodzi, że jeśli k należy do Z , to k+1 należy do Z), to zbiór Z zawiera wszystkie liczby naturalne n >= ko (tzn. N – {0,1,...,ko-1} zawiera się w Z).

Pierwszy warunek nazywamy bazą indukcji (krok podstawowy).

W drugim warunku najpierw dokonujemy założenia indukcyjnego (o tym, że k należy do Z),a następnie wykonujemy krok indukcyjny dowodząc, że k+1 należy do Z.

Przykład 4.n^2 < 2^n dla n >= 5

Przykład 5.Dla dowolnej liczby rzeczywistej a >= -1 oraz dowolnego n należącego do N zachodzi(1+a)^n >= 1+ n*a

Przykład 6.O ile tylko n >= 2, to liczba postaci 2^(2^n) ma na końcu w zapisie dziesiętnym cyfrę 6, tzn. 2^(2^n) = 10x +6 dla pewnej liczby naturalnej x.

Zasada Indukcji Zupełnej (ZIZ) Jeżeli Z jest jakimś zbiorem liczb naturalnych , który wraz z każdym początkowym fragmentem zbioru N postaci {0,1,...,k-1} zawiera

również kolejną liczbę k (tzn. dla każdego k należącego do N zachodzi:jeśli (dla każdego l<k jest tak, że l należy do Z), to k+1 należy do Z to Z zawiera wszystkie liczby naturalne (Z=N). Zauważmy, że nie ma tu wyróżnionego kroku bazowego (ukryty jest on w warunku dla k=0, bo poprzednik implikacji jest trywialnie spełniony).

Przykład 7. Mamy prostokątną czekoladę złożoną z K=a*b (a,b > 0) kwadratowych kawałków. Wykonujemy cięcia wzdłuż którejś z linii pomiędzy kawałkami.

Ile razy trzeba ułamać czekoladę, by rozdzielić wszystkie kwadraciki.

Zasada Maksimum (ZMax) Dowolny niepusty i ograniczony od góry podzbiór S zbioru liczb naturalnych ma w sobie liczbę największą Twierdzenie 1

Następujące zasady są równowazne:Zmin, ZIZ, ZIM, ZMax. a) ZMin implikuje ZIZ b) ZIZ implikuje ZIM c) ZIM implikuje Zmax d) ZMax implikuje ZMin

Metoda indukcji matematycznej ma zastosowanie w sytuacjach następujących: znamy na początku odpowiedź; wiemy jak wyprowadzić odpowiedź w danym kroku z odpowiedzi w poprzednim kroku; odgadujemy ogólne rozwiązanie.

Niezmiennik pętli (używany do projektowania algorytmów i dowodzenia ich poprawności)

Zdanie p jest niezmiennikiem pętli dopóki q, wykonuj S wtedy, gdy spełnia ono następujący warunek: jeśli zdania p i q są prawdziwe, zanim wykonamy krok S, to zdanie p będzie prawdziwe po wykonaniu S.

Twierdzenie o niezmiennikach pętli Załóżmy, że p jest niezmiennikiem pętli „dopuki q, wykonuj S” oraz zdanie p jest prawdziwe kiedy wchodzimy do pętli. Wówczas zdanie p jest prawdziwe po każdej iteracji pętli. Jeśli pętla kończy się, to po jej zakończeniu zadanie p jest prawdziwe, a zdanie q jest fałszywe.

Przykład (algorytm dzielenia)

{Dane: liczby całkowite m>=0 i n>0} {Wyniki: liczby całkowite q i r takie, że q*n + r = m oraz 0 <= r < n} początek q:=0 r:=m {niezmiennik pętli: q*n + r = m oraz r >= 0} dopóki r>=n, wykonuj q:=q+1 r:=r-n koniec

Dowód.

1. Zdanie „ q*n + r = m oraz r >= 0” jest prawdziwe przed wejściem w pętlę

2. Zakładamy, że zdanie „ q*n + r = m oraz r >= 0” prawdziwe w pewnym kroku iteracji

3. Dowieść można, że po kolejnej iteracji zdanie „ q'*n + r' = m oraz r'>= 0” też jest prawdziwe

q'*n + r' = (q+1)*n + (r - n) = q*n + n + r – n = q*n +r =m

r' = r – n >= n-n = 0

Powołujemy się na twierdzenie o niezmiennikach pętli i otrzymujemy:

po zakończeniu pętli zdanie q*n + r = m oraz zdanie r >= 0 są prawdziwe, a zdanie r >=n jest fałszywe czyli r<n.

Funkcja o dziedzinie X i przeciwdziedzinie Y to dowolna relacja f zawarta w X x Y (f: X → Y) taka, że:każdy element dziedziny ma jakąś wartość przypisaną funkcją f

∏ (x ε X) ∑ (y ε Y) ( f(x)=y) Taka wartość jest co najwyżej jedna ∏ (x ε X) ∏ (y1, y2 ε Y) ( jeżeli f(x)=y1 oraz f(x)=y2, to y1=y2)

Surjekcja (funkacja „na”) to funkcja f: X → Y spełniająca warunek: cała przeciwdziedzina jest wykorzystana tzn. każdy jej element jest wartością funkcji dla jakiegoś elementu dziedziny ∏ (y ε Y) ∑ (x ε X) ( f(x)=y)

Injekcja (funkcja rożnowartościowa, 1-1) jeżeli różnym elementom dziedziny przyporządkowuje różne elementy przeciwdziedziny ∏ (x1, x2 ε X) ( jeżeli x1 ≠ x2, to f(x1) ≠ f(x2))

Bijekcja, to funkcja, która jest jednocześnie surjekcją i injekcją.

Funkcja odwrotna do funkcji f: X → Y, jest to funkcja f^-1 taka, że ; każdy element dziedziny f^-1 ma przypisaną jakąś wartość, co oznacza, że sama funkcja f wyczerpuje wszystkie elementy przeciwdziedziny, a zatem jest surjekcją ;f^-1 ma przypisywać dokładnie jeden taki element, czyli każdy element z Y jest przypisany (przez f) jednemu elementowi z X, a zatem f musi być injekcją A zatem: funkcja posiada funkcję odwrotną wtw gdy jest bijekcją.

Złożenie funkcji f: X → Y i funkcji g: Y → Z to funkcja gf:X → Z określona dla wszystkich argumentów x ε X jako (gf(x)=g(f(x)).

Złożenie gf i fg to na ogół różne funkcje.

Gdy f:X → Y jest bijekcją to istnieje funkcja odwrotna f^-1: Y → X i (f^-1f):X → X (identyczność na zbiorze X i (f^-1f)(x) = (f^-1(f(x)) = x. Dla h:X → Y, g:Y → Z i f:Z → W zachodzi f(gh)=(fg)h.

ZLICZANIE ZBIORÓW Niech: Z0=zbiór pusty Z1={0} Z2={0,1} Z3={0,1,2} . . . Zk={0,1,2, . . . , k-1} Gdy m<n, to nie istnieje injekcja z Zn w Zm.

Zbiór X skończony to zbiór bijektywny z pewnym zbiorem Zn (f:Zn → X).

Liczba elementów skończonego zbioru X, to jedyna liczba naturalna n taka, że istnieje bijekcja z Zn w X i oznaczamy ją przez |X|.

Np. |Zn|=n; |Z0|=0

Zbiór X jest nieskończony wtw istnieje injekcja z N w X.

Zbiór przeliczalny to zbiór skończony lub bijektywny z N (f: N → X).

Zasada Szufladkowa DirichletaJeśli n obiektów jest rozmieszczonych w m szufladach i n>m, to istnieje szuflada z przynajmniej dwoma obiektami.

Dowód. Zbiór obiektów jest bijektywny ze zbiorem Zn, a zbiór szuflad ze zbiorem Zm. Rozmieszczenie obiektów w szufladach to określenie funkcji z Zn w Zm.

Ponieważ n>m to ta funkcja nie jest injekcją (1-1), a zatem lokuje co najmniej dwa obiekty w tej samej szufladzie.

Przykład. *W grupie 13 osób muszą być co najmniej dwie, które urodziły się w tym samym miesiącu. *Pewna grupa osób wita się podając sobie ręce. Nikt nie wita się z samym sobą i żadna para osób nie wita się podwójnie. Czy muszą być dwie osoby, które witały taką samą liczbę osób? *Wybierzmy dowolnie 10 różnych liczb naturalnych a1,a2,...,a10 spośród 1,2,..,100. W zbiorze { a1,a2,...,a10} można wybrać dwa rozłączne podzbiory, dające tę samą sumę. (max suma 91 + … + 100 =955; 1024 podzbiorów 10-elementowego zbioru; zatem dawa o tej samej sumie)

Uogólniona Zasada Szufladkowa Jeśli m obiektów rozmieszczonych jest w n szufladach i m>n*r, dla pewnego naturalnego r, to istnieje szufladka z co najmniej r+1 obiektami.(jeżeli każda szuflada ma co najwyżej r obiektów i n szuflad jest, to w sumie jest co najwyżej n*r obiektów)

Zasada mnożenia Dla skończonych zbiorów X,Y zachodzi |X x Y| = |X| * |Y|.

Dowód. Pokazujemy, że |Zm x Zn| = m*n. Pokazujemy, ze funkcja f: Zm x Zn → Zmn, gdzie f(i,j)=i*n+j ε Zmn (gdy odpowiednie i,j) jest bijekcją.

Założenie: f(i,j) = f(i',j') czyli i*n+j = i'*n +j'. Założenie i<=i'. Wówczas (i' – i)n =j-j'.

Lewa strona: wielokrotność n, prawa leży w zbiorze {-n+1, …, n-1}, gdyż j,j' ε Zn.

0 jedyna wielokrotność w zbiorze tym, to i'-i=0 i j-j'=0, co dowodzi injektywności f.

Surjektywność. Niech y ε Zmn, i największa liczba taka, że in<y.

Wówczas y<(i+1)n, a zatem istnieje j ε {0, …, n-1} takie, że y=in+j=f(i,j).

Zalożenie, |X|=m i |Y|=n. Wówczas |X x Y| = |Zm x Zn|= m*n = |X|*|Y|.

Przykład. Turniej rycerzy z bractwa czerwonych (12 rycerzy) i niebieskich (15). Ile różnych indywidualnych pojedynków może być stoczonych, jeśli nie walczą z rycerzami z tego samego bractwa.C, N, pojedynek, to uporządkowana para (c,n), gdzie c ε C, n ε N.,|C x N| = |C| * |N| = 12 * 15 = 300

Zasada dodawania(a) Dla skończonych i rozłącznych zbiorów A i B mamy: |A υ B| = |A| + |B|.(b) Dla skończonych zbiorów mamy: |A υ B| = |A| + |B| - |A ∩ B|.

Dowód.(a) Niech liczności zbiorów |A|=m , |B|=n będą poświadczone bijekcjami f:Z_m → A i g:Z_n → B. Wtedy funkcja Z_m+n → A υ B zadana przez : h(x) = f(x) dla x ε {0,1, … , m-1} h(x) = g(x-m) dla x ε {m, … , m+n+1} jest bijekcją.

h jest injekcją: niech x1 ε {0,1, … , m-1} oraz x2 ε {m, … , m+n+1} (x1 ≠ x2);

mamy, że h(x1) ≠ h(x2). h jest surjekcją: niech y ε A υ B. Niech y ε A. Wówczas z surjektywności f wiemy, że istnieje x ε Z_m taki, że f(x)=y. Ale h(x)=f(x)=y.

(b) |S υ T| = |S| + |T\S|

|T| = |T\S| + |S ∩ T|

|S υ T| + |S ∩ T| = |S| + |T\S| + |S ∩ T| = |S| + |T|

Zasada włączania i wyłączania Dla zbiorów skończonych {A1, …, An} zachodzi|A₁ υ … υ A_n| = ∑_{I ε {1, … , n}} (-1)^|I|+1 |∩_{i ε I} A_i|= |A₁| + … + |A_n| - |A₁ ∩ A₂| - |A₁ ∩ A₃| - … - |A_n-2 ∩ A_n| - |A_n-1 ∩ A_n|+ |A₁ ∩ A₂ ∩ A₃| + …+ |A_n-2 ∩ A_n-1 ∩ A_n| - |A₁ ∩ A₂ ∩ A₃ ∩ A₄| - … - |A_n-3 ∩ A_n-2 ∩ A_n-1 ∩ A_n|+ …(-1) ⁿ⁺¹ |A₁ ∩ … ∩ A_n|

Zbiór potęgowy (czyli zbiór podzbiorów) zbioru X oznaczamy przez P(X).

Przykład. P(pusty_zbiór) = {pusty zbiór} i |P(pusty_zbiór)|= 1

P({pusty_zbiór})={ pusty_zbiór, { pusty_zbiór} i |P({pusty_zbiór})|=2

P({a,b}) = {pusty_zbiór, {a}, {b}, {a,b}}

P({a,b,c}) = {pusty_zbiór, {a}, {b}, {c}, {a,b}, {a,c},{b,c},{a,b,c}}

Ogólna sytuacja Niech p_n oznacza liczbę podzbiorów zbioru n-elementowego.

Wówczas p_n =2ⁿ. Uzasadnienie. Znamy liczbę p_n i chcemy policzyć p_{n +1.}

Niech zbiór Z ma n+1 elementów. Jeżeli a ε Z, to Z'=Z\{a}.

Podzbiory zbioru Z można podzielic na dwa elementy: (a) mające w sobie element a (b) nie mające w sobie element a W drugim przypadku są to podzbiory zbioru Z'. Jest więc ich dokładnie p_n

Każdy zaś podzbiór pierwszego typu (czyli A zawarte w Z, takie, że a ε A) jest jednoznacznie wyznaczony przez swoje pozostałe elementy (tzn. elementy różne od a). A zatem każdy taki zbiór A (że a ε A zawartego w Z) jest postaci A' υ {a} dla pewnego A' zawartego w Z'. A zatem podzbiorów zbioru Z, w których jest element a, jest też tyle ile podzbiorów zbioru Z', tzn. p_n.

Łacznie więc zbiór Z ma p_n + p_n podzbiorów czyli p_n+1= 2* pn. Teraz już można stwierdzić, że to wraz z warunkiem p_n=1 jest spełnione przez p_n =2ⁿ.

Dla dowolnego skończonego zbioru X mamy |P(X)|= 2^|X|.

Zliczanie funkcji Zbiór funkcji X → Y oznaczamy Y^X.

Uwaga Dla skończonych zbiorów X,Y mamy |Y^X| = |Y|^|X|.

Dowód. Niech X={x₀, …, x_m-1} oraz Y={y₀, …, y_n-1). Każda funkcja f:X → Y to krotka wartości dla kolejnych Xi:

(f(x₀), …, f(x_m-1)) ε Y x … x Y (m razy)

A więc zbiór funkcji z X w Y jest równoliczny z Y^m.

Z zasady mnożenia otrzymujemy więc:

|Y x … x Y |(m razy) = |Y| x … x |Y| (m razy) = n^m =|Y|^|X|.

Przykłady 1,2

Uwaga Liczba injekcji ze zbioru skończonego X w zbiór skończony Y wynosi

|Y| * (|Y|-1) * … * (|Y|-|X|+1) = |Y|! / (|Y|-|X|)!

Dowód. Niech X={x₀, …, x_m-1} oraz Y={y₀, …, y_n-1). Każdą injekcję f:X → Y można utożsamić z uporządkowanym wyborem m różnych elementów ze zbioru Y:

f(x₀), …, f(x_m-1) Pierwszy element wybieramy na n sposobów, drugi na n-1 (bo musi być różny od pierwszego), itd., m-ty na n-m+1 sposobów.

Liczba injekcji zatem wynosi: n*(n-1)* … * (n-m+1).

Przykład 3 Uwaga Liczba bijekcji ze zbioru skończonego X w zbiór skończony Y (gdzie |X|=|Y|) wynosi |X|! |Y| * (|Y|-1) * … * (|Y|-|X|+1) = |Y|! / (|Y|-|X|)!

Dowód.Każda injekcja jest bijekcją. Liczba injekcji=liczbie bijekcji czyli n*(n-1)* … * (n-n+1) = n!

Permutacja zbioru skończonego X to f: X → X będąca bijekcją.Zbiór permutacji zbioru Z_n oznaczamy przez S_n (permutacje oznaczamy przez alfa, beta, …)

Przykład Dla dowolnych permutacji alfa, beta skończonego zbioru X a) alfa złożone z beta to permutacja X b) alfa^-1 permutacja taka, że alfa złożone z alfa^-1 = idX = alfa^-1 zlożone z alfa..Zbiór n-elementowy ma dokladnie n! Permutacji (|S_n |=n!).

Przykład Cykl zbioru n-elementowego X to taka permutacja zbioru X, dla której

{x, alfa(x), alfa²(x), …, alfa^n-1(x)} = X przy dowolnym x ε X.

Przykład Rozkład permutacji na rozłączne cykle

Dowolną permutację alfa zbioru X można rozłożyć na rozłączne cykle w sposób następujący:

• wybierz dowolny element x ε X, który nie jest jeszcze w żadnym cyklu

• iteruj prmutację alfa otrzymując kolejno: alfa(x), alfa²(x), …, alfa^j(x)=x

• dodaj do rozkładu cykl x, alfa(x), alfa²(x), …, alfa^j-1(x)

• jeżeli w zbiorze X pozostały jeszcze elementy niepokryte przez żaden cykl, to wróć do punktu 1

Dowód.

• iteracja w punkcie 2 zawsze osiąga element wyjściowy x.

Zbiór X skończony → iteracja alfa(x), alfa²(x), … w pewnym kroku musi wrócić do elementu już rozważanego czyli

dla pewnych i <j będzie alfaⁱ(x) = alfa^j(x)

Weźmy najmniejsze takie j. Gdyby i ≠ 0 to alfa^i-1(x) = alfa^j-1(x) bo alfa permutacja, co sprzeczne z minimalnością j.

A zatem j=0.

• Otrzymane cykle są rozlączne. Zał. że nie są. Niech y=alfaⁱ(x), ten który był już w poprzednich cyklach. →

i>0 (bo x wybrany jako element nie pokryty przez żaden cykl. → Istnieje element z w tym samym cyklu co y taki, że alfa(alfa^i-1(x))=y. Alfa to permutacja → alfa^i-1(x)=z → sprzeczne z tym, ze y to jedynym elementem z poprzedniego cyklu.

Zapisujemy: alfa = (x₀, …)(x₁, …) … (x_k-1, …)

Różne sposoby wybierania k elementów z n-elementowego zbioru

Y ={y1, …, yn}.Nazywamy je schematami wyboru.

Dwa pytania ważne:

Czy istotna kolejność wylosowanych elementów?

Czy wylosowane elementy mogą się powtarzać?

TAK/TAK: Wariacje z powtórzeniami Każdy wybór ma postać ciągu długości k o elementach ze zbioru Y. Wariacji z powtórzeniami jest n^k

TAK/NIE: Wariacje bez powtórzeńKażdy wybór ma postać ciągu długości k o elementach ze zbioru Y, ale każdy element występuje co najwyżej raz.Wariacji bez powtórzeń jest n*(n-1)* … * (n-k+1)=n!/(n-k)!

NIE/NIE: KombinacjeIle jest k-elementowych podzbiorów zbioru Y: (ⁿ_k)=n!/k!*(n-k)!

NIE/TAK: Kombinacje z powtórzeniamiLiczba kombinacji z powtórzeniami :(^n+k-1_k)

Podziały zbiorów

Na ile sposobów można podzielić zbiór Y na r rozłącznych podzbiorów

A1, A2, … , Ar o mocach odpowiednio: t1, t2, …, tr, gdzie t1+ t2+ …+ tr =n? (ⁿ_t1)(^n-t1_t2)(^n-t1-tt2_t3) … (^{n-t1-t2-...-t(r-1)}_tr) = n!/t1!t2!...tr!

Współczynniki dwumianowe – własności

(ⁿ₀) = (ⁿ_n) = 1

(ⁿ_k) = 0 dla k>n

(ⁿ₁) = n dla n>0

(ⁿ_k) = n!/((n-k)!k!)

(ⁿ_k)=(ⁿ_n-k) dla n>=k>=0

(ⁿ_k)=(^n-1_k-1) + (^n-1_k)

Trójkąt Pascala

(⁰₀)

(¹₀)(¹₁)

(²₀)(²₁)(²₂)

(³₀)(³₁)(³₂)(³₃)

(⁴₀)(⁴₁)(⁴₂)(⁴₃)(⁴₄)

…

(ⁿ₀)(ⁿ₁)(ⁿ₂) . . . (ⁿ_n-2)(ⁿ_n-1)(ⁿ_n)

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

Reguła sumowania po górnym indeksie

Niech n, k ε N

∑_i=0ⁿ (ⁱ_k) =(ⁿ⁺¹_k+1)

Reguła sumowania równoległego

Niech n, k ε N

∑_i=0^k (ⁿ⁺ⁱ_i) =(^n+k+1_k)

Tożsamość Cauchy'ego

Niech m, n, k ε N

∑_i=0^k (^m_i)(ⁿ_k-i) =(^m+n_k)

Twierdzenie o dwumianie

Niech x,y ε R i n ε N

(x+y)ⁿ=∑_i=0ⁿ (ⁿ_i) xⁱy^n-i

np. (a+b)⁴ =a⁴+4a³b +6a²b²+4ab³+b⁴

Wniosek

(1+x)ⁿ=∑_i=0ⁿ (ⁿ_i) xⁱ

(ⁿ₀) + (ⁿ₁) + … + (ⁿ_n) = 2ⁿ

^{zliczanie kolejno podzbiorów 0, 1, 2, … -elementowych = liczba podzbiorów zbioru n elementowego}

(ⁿ₀) - (ⁿ₁) + … + (-1)ⁿ(ⁿ_n) = 0ⁿ

^{(liczba podzbiorów o parzystej liczbie elementów = liczbie podzbiorów o nieparzystej liczbie elementów)}

Permutacje bez punków stałych Nieporządek na zbiorze X to permutacja alfa:X → X taka, że alfa(x) różne od x dla dowolnego x należącego do X (permutacja bez punktów stałych) Podsilnia liczby n (!n), to liczba nieporządków zbioru n-elementowego. !0=1

Przykład

Z4={0,1,2,3} ma 4!=24 permutacje, ale tylko 9 to nieporządki

(0,1,2,3) ---- (1,0,3,2) (1,2,3,0) (1,3,0,2)

(2,0,3,1) (2,3,0,1) (2,3,1,0)

(3,0,1,2) (3,2,0,1) (3,2,1,0)

OBSERWACJA !n=n! ∑ _i=0ⁿ ((-1)ⁱ/i!)

Współczynniki multimianowe współczynniki dwumianowe (x+y)ⁿ

A jak z: (x1+ … +xr)ⁿ

podział zbioru n-elementowego na r części o odpowiednio k1,k2, ..kr elementach, gdzie k1+k2+..+kr=n.

Niech n – całkowite a r>=2

(ⁿ_k1,k2,...,kr)

to liczba umieszczenia n obiektów w r pudełkach z odpowiednio k1 obiektami w pierwszym pudełku, k2 obiektami w drugim pudełku, itd

Mamy (ⁿ_n,0,...,0) = 1 , (ⁿ_1,1,...,1) = 1, (ⁿ_{0,k1,k2,...,kr}) = (ⁿ_k1,k2,...,kr), (ⁿ_k1,k2,...,kr) =, (ⁿ_{sigma(k1),sigma(k2),...,sigma(kr)}), dla dowolnej permutacji sigma zbioru {1,...,r}, (x1+ … +xr)ⁿ=∑_{k1+k2+...+kr=n} (ⁿ_k1,k2,...,kr) x1^k1 … xr^kr

Funkcje tworzące Nieskończony ciąg (a₀,a₁,a₂,a₃, … ) może być przedstawiony jako szereg potęgowy zmiennej xA(x) = a₀+a₁x+a₂x²+a₃x³ + … = ∑_k>=0 a_kx^k

A(x) nazywamy funkcją tworzącą ciągu (a₀,a₁,a₂,a₃, … ).

Funkcja tworząca jest to pojedyncza wielkość reprezentująca cały nieskończony szereg.Niech A(x) będzie dowolnym szeregiem potęgowym ∑_k>=0 a_kx^k

Przyjmujemy następujące oznaczenie

[xⁿ]A(x)=a_n

tzn. [xⁿ]A(x) – współczynnik przy xⁿ w A(x).

Jak traktować funkcje tworzące?

I SPOSÓB

Traktujemy A(x) jako szereg liczb rzeczywistych (zespolonych)

szereg A(x) jest zbieżny , jeśli

• istnieje stała M>=0 ograniczająca wszystkie skończone początkowe sumy, tzn.

|a₀| + |a₁x| + |a₂x²| + … + |a_nxⁿ| <= M

zachodzi dla dowolnego n>=0.

• dla pewnej liczby x₀ ε R szereg A(x₀) jest zbieżny to i szereg A(x₁) jest zbieżny dla dowolnego x₁ ε R spełniającego |x₁| <= |x₀|.

Możemy więc

• określić promień zbieżności szeregu jako pewną liczbę r taką, że jeśli |x| < r, to A(x) jest zbieżny a

• sam szereg A(x) potraktować jako funkcję A: (-r,r) → R

o wartościach A(x) = lim _{n → niesk.}(a₀ + a₁x + a₂x² + … + a_nxⁿ)

II SPOSÓB

(bardziej użyteczny w praktycznych obliczeniach i przekształceniach)

Traktujemy A(x) jako formę zapisu ciągu (a₀,a₁,a₂,a₃, … ) czyli jedynie jako ciąg symboli. Równości pomiędzy odpowiednimi wzorami służą rozwiązaniu problemów kombinatorycznych (tak więc traktujemy je jako równości dwu wyrażeń, a nie jako równości dwu funkcji rzeczywistych).

Niech: A(x) - funkcja tworzącą ciągu (a₀,a₁,a₂,a₃, … )

B(x) - funkcja tworzącą ciągu (b₀,b₁,b₂,b₃, … )

Wówczas:

• A(x)=B(x) wtw a₀ = b₀, a₁ = b₁, a₂ = b₂, …

• c*A(x) + d*B(x) = ∑_n=0^niesk (c*a_n + d*b_n)xⁿ

• A(x)B(x) jest szeregiem potęgowym

(a₀+a₁x+a₂x²+a₃x³ + …)(b₀+b₁x+b₂x²+b₃x³ + …) = a₀ b₀ + (a₀b₁+a₁b₀)x + (a₀b₂+a₁b₁+a₂b₀)x² + …

Współzynnik stojący przy xⁿ w tym iloczynie jest równy a₀b_n + a₁b_n-1 + … + a_nb₀ = ∑_k=0ⁿ a_kb_n-k

Dlatego jeśli chcemy przekształcić dowolną sumę postaci(*)c_n = ∑_k=0ⁿ a_kb_n-k

i mamy funkcje tworzące A(x) i B(x) to otrzymamy c_n =[xⁿ]A(x)B(x).

Ciąg (c_n) zdefiniowany wzorem (*) jest nazywany splotem ciągów (a_n) i (b_n).

Dwa ciągi są „splecione” tworząc sumę iloczynów, dla których dolne indeksy sumują się do ustalonej wartości. Splot ciągów odpowiada mnożeniu ich funkcji tworzących.

Funkcje tworzące dają nam skuteczną metodę odkrywania i dowodzenia nowych równości. Są one bardzo użytecznym narzędziem przy wyznaczaniu wartości elementów ciągu. Jeżeli bowiem mamy funkcję tworzącą danego ciągu oraz w jakiś sposób będziemy w stanie poznać postać zwartą tej funkcji, to rozwijając tę postać zwartą w szereg Taylora, poznamy kolejne współczynniki tego rozwinięcia, które są kolejnymi wyrazami naszego ciągu.

Funkcje tworzące w zliczaniuWiemy już, że(1+x)^m=∑_n=0^m (^m_n) xⁿ

Twierdzenie1Dla liczby rzeczywistej y oraz liczby naturalnej n zachodzi (1+x)^y=∑_n=0^niesk. (^y_n) xⁿ

Dla liczby naturalnej m zachodzi 1/(1-x)^m+1=∑_n=0^niesk. (^m+n_n) xⁿ

Przykład 1 Policzmy sumę ∑_k=0ⁿ k² = 1+4+9+...+n²

Zaczynamy od znalezienia zwartej postaci funkcji tworzącej

G(x)= ∑_n=0^niesk. n²xⁿ

Z Wniosku1 mamy: (W1) 1/(1-x) = ∑_n=0^niesk. (ⁿ_n) xⁿ⁼=∑_n=0^niesk. xⁿ

(W2) 1/(1-x)² = ∑_n=0^niesk. (ⁿ⁺¹_n) xⁿ = ∑_n=0^niesk. nxⁿ +∑_n=0^niesk. xⁿ

(W3) 1/(1-x)³ = ∑_n=0^niesk. (ⁿ⁺²_n) xⁿ = 1/2∑_n=0^niesk. n²xⁿ +3/2∑_n=0^niesk. nxⁿ +∑_n=0^niesk. xⁿ

Środkowe po przekształceniu daje

(W4)∑_n=0^niesk. nxⁿ = 1/(1-x)² - 1/(1-x)

Z W2, W3, W4 dostajemy zwartą postać funkcji tworzącej, a mianowicie

G(x)=∑_n=0^niesk. n²xⁿ = 2/(1-x)³ - 3/(1-x)² + 1/(1-x)

Obserwacja

Dla funkcji tworzącej A(x) = a₀+a₁x+a₂x²+a₃x³ + … zachodziA(x)/(1-x) = a₀+(a₀+a₁)x+(a₀+a₁+a₂)x² + …

Naszym zadaniem jest teraz policzenie funkcji tworzącej H(x) dla ciągu

1, 1+4, 1+4+9, … , (1+4+9+...+n²), …

ciągu sum początkowych wyrazów ciągu 1, 4, 9, … , n², …

A zatem

H(x) = G(x)/(1-x) = 2/(1-x)⁴ - 3/(1-x)³ + 1/(1-x)² = 2∑_n=0^niesk. (ⁿ⁺³_n) xⁿ - 3∑_n=0^niesk. (ⁿ⁺²_n) xⁿ + ∑_n=0^niesk. (ⁿ⁺¹_n) xⁿ = ∑_n=0^niesk. (1/3*n³+1/2*n²+1/6*n) xⁿ

Co oznacza, że

∑_k=0ⁿ k² = [xⁿ]H(x) = (2n³+3n²+n)/6

Przykład2

Wszystkie możliwe sposoby podziału 50 centów

(1-c, 5-c, 10-c, 25-c, 50-c)

Nieskończona suma wszystkich możliwości rozmienienia dowolnej kwoty za pomocą (1-c, 5-c, 10-c, 25-c, 50-c)

A1 = [0] + (1) + (1)(1) +(1)(1)(1) + ...

A5 = [0] + (5) + (5)(5) +(5)(5)(5) + ...

A10 = [0] + (10) + (10)(10) +(10)(10)(10) + …

A25 = [0] + (25) + (25)(25) +(25)(25)(25) + …

A50 = [0] + (50) + (50)(50) +(50)(50)(50) + ...

B=A1 x A5 = ([0] + (1) + (1)(1) +(1)(1)(1) + …)

x ([0] + (5) + (5)(5) +(5)(5)(5) + …)= [0] +(1) + (5) + (1)(1) + (1)(5) + (5)(5) + (1)(1)(1) + …

C = B x ([0] + (10) + (10)(10) +(10)(10)(10) + …)

D = C x ([0] + (25) + (25)(25) +(25)(25)(25) + … )

E = D x ([0] + (50) + (50)(50) +(50)(50)(50) + … )

Grupujemy składniki sumy E w podsumy o tych samych wartościach

E = ((1)) + ((1)(1)) + ((1)(1)(1)) + ((1)(1)(1)(1))+((1)(1)(1)(1)(1) +(5))+((1)(1)(1)(1)(1)(1) +(5)(1)) + ...

Zastępujemy teraz:(1) przez x, (5) przez x⁵, (10) przez x¹⁰, (25) przez x²⁵, (50) przez x⁵⁰

Otrzymujemy nieskończony szereg zmiennej x:

E(x) = (1 + x + x² + x³ + …) * (1 + x⁵ + x¹⁰ + x¹⁵ + …) * (1 + x¹⁰ + x²⁰ + x³⁰ + …) * (1 + x²⁵ + x⁵⁰ + x⁷⁵ + …) *(1 + x⁵⁰ + x¹⁰⁰ + x¹⁵⁰ + …) = 1 + x + x² + x³ + x⁴ + 2x⁵ + 2x⁶ + 2x⁷ + 2x⁸ + 2x⁹ + 4x¹⁰ + ...

Liczba różnych możliwych sposobów rozmienienia n centów jest równa współczynnikowi stojącemu przy jednomianie xⁿ.

Oznaczmy występujące w E(x) funkcje tworzące

A_k(x) = 1 + x^k + x^2k + x^3k + …

dla k = 1, 5, 10, 25, 50.

Mamy, że (tak jak W1)

1 + x^k + x^2k + x^3k + … = 1/(1-x^k)

Czyli mamy

A(x) = A₁(x) = 1/(1-x)

B(x) = A(x) * A₅(x) = A(x)/(1-x⁵)

C(x) = B(x) * A₁₀(x) = B(x)/(1-x¹⁰)

D(x) = C(x) * A₂₅(x) = C(x)/(1-x²⁵)

E(x) = D(x) * A₅₀(x) = D(x)/(1-x⁵⁰)

Stąd

A(x) = 1 + x*A(x)

B(x) = A(x) + x⁵*B(x)

C(x) = B(x) + x¹⁰*C(x)

D(x) = C(x) + x²⁵*D(x)

E(x) = D(x) + x⁵⁰*E(x)

oraz zależności między współczynnikami

a_n=1, b_n=a_n+b_n-5, c_n=b_n+c_n-10, d_n=c_n+d_n-25, e_n= d_n +e_n-50

n	0	5	10	15	20	25	30	35	40	45	50
an	1	1	1	1	1	1	1	1	1	1	1
bn	1	2	3	4	5	6	7	8	9	10	11
cn	1	2	4	6	9	12	16	10	25	30	36
dn	1					13					49
en	1										50

Równania rekurencyjne i funkcje tworzące

Schemat postępowania przy przeliczaniu obiektów kombinatorycznnych:

• znalezienie związku rekurencyjnego

• obliczenie kilku początkowych wartości

• odgadnięcie ogólnego wzoru

• udowodnienie wzoru stosując indukcję matematyczną

• jeżeli wzoru nie sposób odgadnąć,to czasami można za pomocą równania rekurencyjnego zbudować funkcję tworzącą, której współczynniki po rozwinięciu w szereg potęgowy wyznaczą rozwiązanie

Permutacje

Wzór rekurencyjny: a₁=1, a_n=n*a_n-1

Początkowe wyrazy ciągu a_n: a₂=2*a₁=2*1=2!, a₃=3*a₂=3*2!=3!

Ogólny wzór: a_n=n!

Indukcja:

• dla n=1 wzór prawdziwy;

• zakładamy, że prawdziwy dla pewnego k: a_k=k!

• Dowodzimy: a_k+1= (k+1)*a_k = (k+1)*k! =(k+1)!

Wykładnicza funkcja tworząca ciągu a_n:

f(x)=∑_n=0^niesk. (a_n/n!)xⁿ = 1 + ∑_n=1^niesk. (n*a_n-1/n!)xⁿ = 1 + x∑_n=1^niesk. (a_n-1/(n-1)!)x^n-1 = 1+x*f(x)

Stąd f(x) = 1/(1-x) = ∑_n=0^niesk. xⁿ czyli an=n!

Ciąg Fibonacci'ego Rozważmy ciąg (f₀, f₁, f₂, f₃, …) zdefiniowany następująco

f₀ = 0

f₁ = 1

f_n = f_n-1 + f_n-2 dla n >=2

Jak można otrzymać postać zwartą jego wyrazów uzywając funkcji tworzących.

Weź pod uwagę zależności rekurencyjne aby otrzymać stosowne równanie dla funkcji tworzącej F(x) dla ciagu.

F(x) = ∑_n=0^niesk f_nxⁿ = x + ∑_n=2^niesk (f_n-1+f_n-2)xⁿ = x + xF(x) +x²F(x)

Po przekształceniu mamy

F(x) = x/(1-x-x²) = x/(1-z₀x)(1-z₁x) = (1/sqrt(5))/((1/(1-z₀x)) – (1/(1-z₁x))

gdzie z₀ = (1 + sqrt(5))/2 z₁ = (1 – sqrt(5))/2

Chcemy wykorzystać funkcje F(x) do przedstawienia współczynników f_n w postaci zwartej.

Obserwacja

Dla funkcji tworzącej

A(x) = a₀+a₁x+a₂x²+a₃x³ + …

zachodzi

A(x)/(1-x) = a₀+(a₀+a₁)x+(a₀+a₁+a₂)x² + …

F(x) = (1/sqrt(5))(∑_n=0^niesk (z₀)ⁿxⁿ - ∑_n=0^niesk (z₁)ⁿxⁿ) = (1/sqrt(5))∑_n=0^niesk ((z₀)ⁿ - (z₁)ⁿ)xⁿ

Postać zwarta to

f_n = (1/sqrt(5)) ((z₀)ⁿ - (z₁)ⁿ)

Funkcje wymierne

• Stopień wielomianu degP(x) = n, jeśli P(x) = p₀ + p₁x + … + p_nxⁿ.

• Funkcja wymierna R(x) to funkcja postaci P(x)/Q(x) gdzie P(x) oraz Q(x) różne od zera są wielomianami skończonego stopnia

ObserwacjaNiech A(x) oraz B(x) będą wielomianami degA(x)>=degB(x). Wówczas istnieją wielomiany Q(x) oraz R(x) takie, że

A(x) = Q(x)B(x) + R(x)

gdzie degR(x) < degA(x) = degQ(x) +degB(x).

Przykład1

WniosekNiech P(x) oraz Q(x) będą wielomianami degP(x)>=degQ(x)

Wówczas funkcję wymierną R(x) = P(x)/Q(x) można przedstawić w postaci

R(x) = P(x)/Q(x) = A(x) + B(x)/Q(x)

dla pewnych wielomianów A(x) i B(x) takich, że degB(x) < degQ(x).

TwierdzenieNiech P(x) oraz Q(x) będą wielomianami takimi, że

• degP(x) < degQ(x)

• Q(x) = S(x)T(x), gdzie oba wielomiany S(x), T(x) są stopnia co najwyżej 2,

• q0 różne od 0

Wówczas istnieją wielomiany A(x) oraz B(x) takie, że degA(x) < degS(x) i

degB(x) < degT(x) oraz P(x)/Q(x) = A(x)/S(x) + B(x)/T(x).

(twierdzenie to pozwala na rozbijanie skomplikowanych funkcji wymiernych na sumę prostszych)

Wniosek (metoda rozwijania funkcji wymiernej w szereg)Rozważmy funkcję wymierną w postaci R(x) = P(x)/Q(x)gdzie degP(x) < deg Q(x) i q₀ różne od 0. Załózmy ponadto, że wielomian Q(x) rozkłada się na następujący iloczyn czynników liniowych Q(x) = q₀(1- z₁x)^m1*(1- z₂x)^m2* … * (1-z_k)^mk

Z wcześniej podanego twierdzenia mamy, że R(x) = P(x)/Q(x) = P₁(x)/(1- z₁x)^m1 + P₂(x)/(1- z₂x)^m2 + … + P_k(x)/(1- z_kx)^mk.

gdzie deg P_i(x) < m_i. Korzystając z obserwacji (powyżej podanej) można otrzymać

R(x) = ∑ _i=0^k (g_i,1/(1-z_ix) + g_i,2/(1-z_ix)² + … + g_i,mi/(1-z_ix)^mi)

Wykonując pewne operacje (prowadzące od f.tw do f.tw) i porównując współczynniki otrzymuje się pewne równanie, rozwiazanie którego daje nam poszukiwane współczynniki g_i,j. Z drugiej strony można pokazac, że

1/(1-zx)^m+1 = ∑_n=1^niesk (^m+n _m)zⁿxⁿ

co w konsekwencji daje

[xⁿ]R(x) = ∑ _i=1^k (g_i,1 + g_i,2 (ⁿ⁺¹ ₁)+ … + g_i,mi (^mi+n-1 _mi-1))z_iⁿ

1) Dzielenie liczb z resztąDla każdej liczby całkowitej a istnieje jednoznacznie wyznaczony iloraz q i reszta r spełniajace warunek a=b*q +r

gdzie 0<=r<b .Resztę r z dzielenia a przez b zapisujemy a mod b.

Przykład.47 mod 9 = 2,32 mod 43 = 32 , -3 mod 7 = 4,-22 mod -2 = 0

Struktura danych -jest to system relacyjny<U, {r_i}_{iε I}>

gdzie U- uniwersum systemu {r_i}_{iε I} - zbiór relacji (operacji) na strukturze danych

Formalna definicja struktury danych składa się z : sygnatury systemu relacyjnego ,sygnatury wszystkich operacji struktury, specyfikacji (opisu) operacji struktury

LISTA To skończony ciąg elementów

q = [x₁,x₂,...,x_n]

gdzie

x₁ – lewy koniec listy

x₂ – prawy koniec listy

|q|=n - długość listy

Szczególny przypadek: lista pusta: q=[]

Podstawowe abstrakcyjne operacje na listach:

(q = [x₁,x₂,...,x_n] , r = [y₁,y₂,...,y_m], 0 <= i <= j <= n )

• dostęp do elementów listy: q[i] = x_i

• podlista: q[i .. j] = [x_i,x_i+1,...,x_j]

• złożenie: q & r = [x₁,x₂,...,x_n,y₁,y₂,...,y_m]

Przykład:Wstawianie elementu x za element x_i na liście q można zdefiniować następująco q[1..i-1] & [x] & q[i+1..|q|]

Podstawowe operacje na końcach listy

• top(q) = q[1] – pobieranie lewego końca listy

• push(q,x) = [x]&q – wstawianie elementu x na lewy koniec listy

• pop(q) = q(2 .. |q|) - usunięcie bieżącego lewego końca listy

• rear(q) = q(|q|) - pobieranie prawego końca listy

• inject(q,x) = q & [x] – wstawienie elementu x na prawy koniec listy

• eject(q) = q(1 .. |q|-1) – usunięcie bieżącego prawego końca listy

STOS Jest to struktura danych, do której dostęp jest możliwy tylko od strony tzw. wierzchołka czyli pierwszego wolnego miejsca na nim.Zasadę działania stosu określa się w skrócie jako LIFO (Last In First Out)

Podstawowe operacje na stosie (s = (e₁,e₂,...,e_n))

push(s,e) = (e,e₁,e₂,...,e_n)– położenie elementu na stos

pop(s) = (e₂,...,e_n)– zdjęcie elementu ze stosu

top(s) = e₁ – pobranie elementu ze stosu

empty(s) wtw n=0 – służy do sprawdzania czy stos jest pusty

Własności stosu top(push(s,e)) = e pop(push(s,e)) = s not empty(s) → push(pop(s), top(s)) = s while not empty(s) do s:=pop(s) – ma własność stopu

Kolejki Jest to struktura danych, której zasadę działania określa się w skrócie jako FIFO (First In First Out)

Podstawowe operacje na kolejkach

(q = (e₁,e₂,...,e_n))

• first(q) = e₁ – pobieranie pierwszego elementu z kolejki

• in(q,e) = (e₁,e₂,...,e_n,e)- wprowadzenie elementu na koniec kolejki

• out(q) = (e₂,...,e_n) gdy n>0 - usuniecie elementu z czoła kolejki

• empty(q) wtw n=0– służy do sprawdzania czy kolejka jest pusta

Czy prawda:

not empty(q) → in(e,out(q))=out(in(e,q)) ? (+)

first(q)=e → out(in(e,q))=q ?

(not empty(q) and first(q)=e → in(e,out(q))=q ?

Zbiory Kolekcja różnych elementów, gdzie |S| liczba elementów zbioru.

Podstawowe operacje

Operacja	Efekt działania operacji	Nazwa operacji
insert(x,S)	S:=S υ {x}	Wstawienie elementu x do zbioru S
delete(x,S)	S:=S \ {x}	Usunięcie elementu x ze zbioru
member(x,S)	True gdy x ε S False gdy not x ε S	Sprawdzenie czy x jest elementem S
min(S)	a - najmniejszy element w zbiorze S	Zwraca najmniejszy element w zbiorze S ze względu na pewien ustalony porządek
deletemin(S)	S:=S \ {min(S)}	Usuniecie najmniejszego elementu w zbiorze S
union(S1,S2)	S:=S1 υ S2	Suma zbiorów S1 i S2, gdy są rozłączne

Grafy Oznaczenia:

• G = < V, E > - graf bez wag, gdzie V zbiór wierzchołków, E – zbiór krawędzi

• |V| = n - liczba wierzchołków grafu G

• |E| = m- liczba krawędzi grafu G

• (i,j)- krawędź (para uporządkowana) z wierzchołka i do wierzchołka j w grafie skierowanym

• {i, j}- krawędź łącząca wierzchołki i oraz j w grafie nieskierowanym

• G = < V, E, f > - graf z wagami, gdzie V, E jw, a f: E → R funkcja wag

Operacje na grafach:

(G = < V, E >, G1 = < V1, E1 >, G2 = < V2, E2 > )

• suma grafów: G1 υ G2 = < V1 υ V2, E1 υ E2 >

• przecięcie grafów: G1 ∩ G2 = < V1 ∩ V2, E1 ∩ E2 >

• różnica grafów: G1 \ G2 = < V1 \ V2, E1 \ E2 >

• podgraf grafu G to graf H taki, że V(H) zawiera się w V(G) i E(H) zawiera się w E(G)

• restrykcja grafu G do podzbioru X zawartego w V, to G|X =< X, {{v,w}: v,w ε X }>

• podgraf indukowany grafu G to graf będący restrykcją grafu G

Marszruta – skończony ciąg krawędzi z wierzchołka u do v o długości=liczbie krawędzi

Droga (ścieżka)– marszruta bez powtarzających się krawędzi

Cykl – marszruta zamknięta (jedynym powtarzającym się wierzchołkiem jest jej początek=koniec

Graf spójny – graf, w którym między dwoma dowolnymi wierzchołkami istnieje droga

Graf skierowany nie ma pętli

Wierzchołek izolowany – nie posiada sąsiadów

Drzewo – graf spójny nie zawierający cykli

Drzewo rozpinające grafu G – podgraf zawierający wszystkie jego wierzchołki i będący drzewem

Cykl Eulera to zamknięta marszruta przechodząca przez każdą krawędź dokładnie raz

Graf eulerowski to graf posiadający cykl Eulera

Graf jednokreślny to graf posiadający marszrutę przechodzącą dokładnie raz przez każdą krawędź

Cykl Hamiltona to cykl przechodzący przez wszystkie wierzchołki grafu (maszruta zamknięta odwiedzająca każdy wierzchołek dokładnie raz)

Graf hamiltonowski to graf posiadający cykl Hamiltona

Ścieżka Hamiltona to ścieżka przechodząca przez wszystkie wierzchołki, kazdy odwiedzając jedynie jeden raz

TW.Jeżeli G=<V,E> graf to ∑_{v ε V} deg v=2|E|, gdzie deg v to stopień wierzchołka (liczba krawędzi incydentnych)

TW.Dla grafu T=<V,E> następujące warunki są równoważne T jest drzewem, T nie zawiera cykli i ma |V|-1 krawędzi , T jest spójny i ma |V|-1 krawędzi, T jest spójny a usuniecie dowolnej krawędzi tworzy dokładnie dwie składowe

dowolne dwa wierzchołki T są połączone dokładnie jedną drogą, T nie zawiera cykli ale dodanie dowolnej nowej krawędzi tworzy dokładnie jeden cykl

TW.Graf G jest eulerowski wtw gdy jest spójny i stopień każdego wierzchołka jest parzysty

TW.Graf G jest jednokreślny wtw gdy jest spójny i jego wszystkie , poza co najwyżej dwoma wierzchołkami, mają parzysty stopień

KOLOROWANIE GRAFÓW

Przypisanie wierzchołkom grafu kolorów w taki sposób, by każde dwa sąsiednie wierzchołki miały różne kolory.

Kolorowanie grafu G=<V,E> to funkcja c: V → N taka, że c(v)=/=c(w) gdy (v,w) jest krawędzią.

Kolorowanie grafu na k kolorów wyznacza rozbicie zbioru na sumę rozłączną V = V₀ υ V₁ υ … υ V_k-1 jednobarwnych zbiorów Vi przy czym każdy graf indukowany postaci G|Vi jest antykliką (graf bez krawędzi).

Odwrotnie: rozbicie V = V₀ υ V₁ υ … υ V_k-1 pozwala na pokolorowanie grafu G na k kolorów

Graf k-kolorowany (k-barwny) to graf dający się pokolorować k barwami.

Liczba chromatyczna grafu τ(G) to najmniejsza liczba barw, którymi można pokolorować graf G.

Optymalne kolorowanie grafu G to kolorowane używające dokładnie τ(G) kolorów.

TW.Graf, którego wszystkie wierzchołki mają stopień nie większy niż k jest (k+1)-kolorowalny(indukcja ze względu na liczbę wierzchołków w grafie)