ax≡b(mod m) = x≡ba⁻¹(mod m)

1) Sprawdzam czy może się skrócić

2) NWD (a, m). Jeżeli NWD nie jest dzielnikiem „b” to układ nie ma rozwiązania. Następnie w postaci różnicy iloczynów a*z – m*w.

3) Podstawiam a⁻¹(mod m)=z

4) x=b*z

5) Dzielimy wynik b*z przez m i reszte z dzielenia „t” wstawiamy przed modulo

6) Wynik na postać x≡t(mod m)

$\left\{ \begin{matrix} x \equiv a_{1}(mod\ m_{1}) \\ x \equiv a_{2}(mod\ m_{2}) \\ \begin{matrix} x \equiv a_{3}(mod\ m_{3}) \\ x \equiv a_{4}(mod\ m_{4}) \\ x \equiv a_{5}(mod\ m_{5}) \\ \end{matrix} \\ \end{matrix} \right.\ $

1) Wybieram 3 dowolne równania.

2) Obliczam m=m₁ * m₂ * m₃

3) Obliczam M₁=m₂*m₃, M₂=m₁*m₃, M₃=m₁*m₂

4) Obliczam N₁ = M₁⁻¹(mod m₁), N₂ = M₂⁻¹(mod m₂), N₃ = M₃⁻¹(mod m₃)

5) Obliczam wynik końcowy x ≡ a₁ * M₁ * N₁ + a₂ * M₂ * N₂ + a₃ * M₃ * N₃(mod m)

$$\overset{}{A \cup B \cup C} = \overset{}{A} + \overset{}{B} + \overset{}{C} - \overset{}{A \cap B} - \overset{}{A \cap C} - \overset{}{B \cap C} + \overset{}{A \cap B \cap C}$$

Macierz sąsiedztwa – macierz która wskazuje ile dróg prowadzi z jednego wierzchołka do drugiego

Macierz osiągalności – macierz która wskazuje z którego wierzchołka możemy osiągnąc inny w jak najmniejszej liczbie kroków.

Cykl – w cyklu nie mogą się powtórzyć żadne wierzchołki poza początkowym i końcowym

Droga prosta – nie może powtórzyć się krawędź

Drogi zamknięte – wszsytko może się powtarzać. Jest ich nieskończenie wiele

Graf pełny – każde dwa wierzchołki są połączone

Cykl(wszystkie wierzchołki parzyste)/droga(2 wierzchołki nieparzyste) Eulera –przez każda krawedz przechodzimy tylko raz

Cykl Hamiltona – cykl prosty przebiegający przez wszystkie wierzchołki grafu.

Graf dwudzielny – każda krawędź łączy wierzchołek jednej grupy z wierzchołkiem z drugiej.

Algorytm Fleury’ego (cykl/droga eulera)

1. Wybierz dowolny wierzchołek „V” stopnia nieparzystego. Jeżeli go nie ma wybierz dowolny wierzchołek „V”. VS={V}, ES=⌀

2. Jeżeli z „V” nie wychodzi żadna krawędź zatrzymaj się. Jeżeli wychodzi to krok 3

3. Jeżeli z V wychodzi tylko jedna krawędź „e=(V,W)” to usuń e z E(G), V z V(G) i przejdź do kroku 5. Jeżeli nie to krok 4

4. Spośród krawędzi wychodzących z V wybierz e=(V,W) dla której graf G\{e} pozostaje grafem spójnym(dla każdej pary wierzchołków istnieje krawędź). Usuń e z E(G). Przejdź do kroku 5.

5. Dopisz W na końcu ciągu VS, e na końcu ES, zastąp V przez W i przejdź do kroku 2.

Algorytm Kruskala

ES=0, dla j od 1 do E(G) wykonuj:
jeżeli graf ES ∪{e_j} jest acykliczny to dołącz e_j do ES.

Algorytm Prima

Wybierz W należące do V(G) i VS = {W};

Dopóki VS różne V(G) wykonuj:

1. Wybierz e =(X,Y) należace E(G) takie, że X należy VS, Y nal do VS takie, że e ma najmniejszą wagę,

2. Dołącz e do ES