Twoim problemem jest to, że powszechną NICOŚĆ mylisz z osobistą PUSTKĄ
x mod y = x-y*(podłoga)x/y
RELACJE zwrotna, jeśli xRx   antysymetryczna, jeśli ( xRy Ù yRx ) Þ x = y
przechodnia, jeÅ›li ( xRy Ù yRz ) Þ xRz   symetryczna, jeÅ›li xRy Þ yRx                          Â
zwrotną, przechodnią i symetryczn -:równoważności
zwrotnÄ…, przechodniÄ… i antysymetrycznÄ… -
(częściowego porządku) porządkującą
plan montowanie 4 urzÄ…dzen na 6 stanowiskach-64(przyrastajÄ…cej)
x1+x2+x3=7 ; n=3 ; k=7 ; (n+k-1 po k)
podzielić 6 elementów na 3 bloki
Sur|n,k|={|n| po |k|}*|k|! //6 elem
ponumerowanych na 3 bloki ponumerowane
Â
P(n, k)=P(n-1,k-1)+P(n-k,k) - liczba podziałów liczby n na k składników
P(n)- liczba wszystkich podziałów liczby n
Przyjmujemy, że P(n, 1) = P(n,n) = 1               Diagram Ferrersa
Dla podziału  n = a1 + ... + ak
tworzymy diagram o kÂ
wierszach, który zawiera ai
punktów w i-tym wierszu
Przykład dla podziału liczby
10 = 5 + 3 + 2Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â
·  ·  ·  ·  ·
·  ·  ·
·  ·
Â
Podział sprzężony wynika z transpozycji diagramu Ferrersa
PrzykÅ‚ad podziaÅ‚u sprzężonego 10 = 3 + 3 + 2 + 1 + 1 Â
Â
Â
| A v B v C | = |A| + |B| + |C| - |A^B| - |B^C| - |A^C| + |A^B^C|Â Â Â Â Â Â Â Â Â Â Â |A v B| = |A| + |B| - |A^B|
GRAFY m=d(i)/2 ; dla k=1 // n -1=<m=< (n-1)n / 2   ;  dla k>1 // n -k=<m=< (n-k)(n –k +1) / 2         Â
Planarny dla n>=3 gdy m=<3n-6 // nie jest jak ma K5 Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Planarny i dwudzielny m<=2n-4
Planarny n-m+f=k+1 (f-liczba ścian)       Planarny i Spójny n-m+f=2
Dwudzielny K3,3 3*3-ilość krawÄ™dzi a 3+3 ilość wierzchoÅ‚ków                                                                                                         Â
EKLER Drogą Eulera w grafie nazywamy drogę prostą zawierającą wszystkie krawędzie grafu.
Cyklem Eulera nazywamy zamkniętą drogę Eulera. Graf spójny G ma cykl Eulera wtedy i tylko wtedy, gdy stopień każdego wierzchołka jest parzysty. Graf spójny, mający dokładnie dwa wierzchołki
stopnia nieparzystego, ma drogę Eulera.Graf skierowany spójny zawiera cykl Eulera wtedy i tylko wtedy, gdy dla każdego wierzchołka v zachodzi d+(v) = d-(v).
Graf pochodny dla Eulerowskiego NIE jest Eulerowski ponieważ aby graf skierowany był Eulerowski
stopień wejściowy i wyjściowy każdego wierzchołka musi być równy, wymagana jest silna spójność
grafu. Graf pochodny jest spójny (gwarantuje to silna spójność grafupierwotnego) Przechodząc na graf
nie skierowany nie mamy gwarancji, że zastepując 1 lub 2 łuki na 1 krawędź w grafie
pochodnym stopniwe wszystkich wierzcholków w grafie pochodnym są parzyste.
HAMILTON DrogÄ… Hamiltona w grafie G nazywamy takÄ… drogÄ™ elementarnÄ…,
która zawiera wszystkie wierzchołki grafu. Cyklem Hamiltona w grafie G nazywamy
cykl o długości |V|, zawierający wszystkie wierzchołki grafu (zamknięta droga Hamiltona)
Graf pełny Kn jest hamiltonowski dla każdego n ³ 3: Kn zawiera (n-1)!/2 cykli Hamiltona
Dirac: d(v) ³ n/2 d(v)-liczbaodchodzacych krawędzi z każdego punktu
Ore: Graf o n wierzchołkach dla n ³ 3, w którym d(v) + d(w) ³ n
Liczba Krawędzi: m >= (n-1)(n-2)/2 + 2             Tw. Nasha Williamsa: d(v)+ ³ n/2 ; d(v)- ³ n/2
Tw. Meyniel: jeżeli graf skierowany bez pętli jest silnie spójny i dla
dowolnych dwóch wierzchołków niezależnych suma ich stopni jest równa co
najmniej 2n-1 to graf zawiera cykl Hamiltona.      Tw.Redei: każdy turniej zawiera droge Hamiltona
Tw. Camiona: każdy silnie spójny turniej zawiera cykl Hamiltona
Turniej to graf zawierajacy dokładnie jeden łuk dla każdej pary punktów (pochodna turnieju jest grafem
pełnym) Turniej może reprezentować wyniki spotkań par uczestniczących
w rozgrywkach typu "każdy z każdym" (bez remisów)
Uwaga: ten turniej nie jest silnie spójny (nie ma drogi z b do d)
Tw. Chvatala: dla Â
Graf jest panacykliczny, jeśli zawiera cykle o długości k   dla każdego k, 3 £ k £ n.
Skojarzeniem w grafie G nazywamy dowolny podzbiór krawędzi parami niezależnych.
Przykład skojarzeniaPokryciem krawędziowym grafu nazywamy taki podzbiór jego krawędzi, że każdy wierzchołek grafu jest incydentny z przynajmniej jedną krawędzią z tego podzbioru. jeśli graf dwudzielny t (G) = n (G)
        Â
n (G)-maksymalna liczba krawędzi niezależnych w grafie G
a (G)-maksymalna liczba wierzchołków niezależnych w grafie G
r (G)-minimalna liczba krawędzi pokrywających wszystkie wierzchołki
t (G)-minimalna liczba wierzchołków pokrywających wszystkie krawędzie grafu
Tw Gallai:,Jeśli graf jest grafem bez wierzchołków izolowanych, to a (G) + t (G) = n (G) + r (G) = n.
Ponadto zachodzą nierówności: n (G) £ t (G) (maks.moc skojarz. £ min. moc pokr.wierz.), a (G) £ r (G) (maks.moc zb.w.stab. £ min.moc pokr.kraw.) n (G) £ r (G) ; a (G) £ t (G)
Zbiorem wewnętrznie stabilnym [a (G)]- wierzchołków grafu G nazywamy dowolny podzbiór wierzchołków parami niezależnych. (=2)
Pokryciem wierzchołkowym [t (G)] grafu nazywamy taki podzbiór jego wierzchołków, że każda krawędź grafu jest incydentna z przynajmniej jednym wierzchołkiem z (=3)
Â
Graf nazywamy k-spójnym krawędziowo (mini. Zbiór rozpajający), jeśli l(G) ³ k
Przykład l(G) = 2 , graf 2-spójny krawędziowo
Graf nazywamy k-spójnym, jeśli c(G) ³ k
Przykład zbioru rozdzielającego zbiory rozdzielające:
{ a, b, d }, { a, d }, {b, d }; ...