NWD(0,n)=|n|

Euklides reku: NWD(0,n)=n, NWD(m,n)=NWD(n modm, m)

a=b(mod n)a mod n = b mod n

a-b jest krotnością n

Euler: fi(p) = p-1 fi(p^a)=p^a-p^(a-1) fi(mn)=fi(m)*fi(n) twierdz: a,n nal do P nwd(a,n)=1 wtedy a^fi(n) = 1 (mod n)

Graf pełny - klika o n wierzchołkach (Kn) (max liczba krawędzi, m=(n po 2)=2(n-1)/2 lub n^2 w skierowanym)

Graf planarny/płaski - można narysować bez przecinających się krawędzi

Dla grafu bez pętli liczba wierzch=2*|U|

Marszruta - ciąg wierzchołków, elementarna- nie powtarzają sie wierzchołki, prosta- nie powt. się gałęzie (więc jest elementarna)

Droga - marszruta w grafie nieskierowanym lub marszruta skierowana

Cykl elementartny - powtarzaja sie tylko wierzchołki poczatkowe i koncowe

Graf spójny - dla każdej pary wierzch istnieje marszruta je laczaca

Graf silnie spójny - dla kazdej pary wierzch istnieje droga je laczaca

Składowa spójności - maksymalny podgraf spójny

m-krawedzi, n - wierzch, k-liczba skladowych spojnosci

Graf o wiecej niz
krawedziach jest spojny,

C(G)=m+k-n C=0 w grafie nie wystepuja cykle elementarne

C=1 w grafie istnieje dokladnie 1 cykl elementarny

C jest rowna liczbie galezi ktore nalezy usunac aby powstal graf nie zawierajacy cykli elementarnych

Las - C=0, drzewo - las spójny, liść - wierch. Drzewa o st=1, drzewo rozp - podgraf bedacy drzewem i zawierajacy wszystkie wierzcholki grafu, karkas - graf bedacy wszystkimi drzewami rozpinającymi

---