Algorytmy  Matematyka Dyskretna
Teoria grafów
Algorytm wyznaczania kodu Prufera
Aby wyznaczyć kod Prufera dla danego drzewa T na zbiorze wierzchołków
{1, ..., n}, należy:
1. Znalez
ć najmniejszy wierzchołek stopnia jeden, powiedzmy  v . Niech
 w będzie wierzchołkiem połączonym z  v ;
2. Zapisać  w oraz usunąć wierzchołek  v wraz z krawędzią  vw ;
3. Jeśli w drzewie pozostała więcej niż jedna krawędz
, to przejść do kroku
1., w przeciwnym razie zakończyć algorytm.
Otrzymany ciÄ…g liczb jest kodem Prufera dla drzewa T.
Algorytm otrzymywania drzewa z kodu
Dla zadanego ciągu liczb (a1, a2, ..., an-2) wybranych w dowolny sposób ze
zbioru {1, ..., n}, aby wyznaczyć drzewo T , dla którego ciąg ten jest kodem
Prufera, należy:
1. Zapisać dwie listy; pierwszą (a1, a2, ..., an-2) oraz drugą {1,2, ..., n} i
rozpocząć ze zbiorem wierzchołków {1, ..., n} i pustym zbiorem
krawędzi.
2. Wyznaczyć z drugiej listy najmniejszą liczbę, powiedzmy  i , która nie
występuje na pierwszej liście. Usunąć pierwszy element z pierwszej listy,
powiedzmy  j , usunąć  i z drugiej listy oraz dodać do zbioru krawędzi
 ji .
3. Jeśli pierwsza lista zawiera co najmniej jedną liczbę, to przejść do punktu
2. Jeśli pierwsza lista jest pusta, to druga będzie się składać z dokładnie
dwóch liczb. Do zbioru krawędzi dodać ostatnią, której wierzchołkami są
właśnie te liczby i zakończyć algorytm.
1
Algorytm obliczania wartości wyrażenia w postaci postfixowej
Dla kolejnych elementów zapisu wyrażenia:
" jeżeli element jest stałą lub zmienną, to wkładamy jego wartość na stos,
" jeżeli element jest znakiem operacji, to:
" zdejmujemy dwie wartości z wierzchu stosu,
" wykonujemy operację na tych wartościach,
" obliczoną wartość wkładamy na wierzch stosu,
" po przejściu całego wyrażenia jego wartość znajduje się na stosie.
Algorytm przeszukiwania drzewa metodą  wgłąb
Dane wejściowe: drzewo T .
ÁÄ… ÁÄ…
" Odwiedzamy korzeń i wkładamy go na STOS; zaznaczamy , jako
wierzchołek odwiedzony;
" Dopóki STOS nie jest pusty, powtarzamy:
" Jeżeli  v jest wierzchołkiem na wierzchu STOSU to sprawdzamy,
czy istnieje syn  u wierzchołka  v , który nie był jeszcze
odwiedzany. Najpierw sprawdzamy  v0 , a potem  v1 .
" Jeżeli takie  u się znajdzie, to odwiedzamy  u , wkładamy je na
wierzch STOSU i zaznaczamy, jako wierzchołek odwiedzony (np.
skreślamy).
" Jeżeli takiego  u nie ma, to zdejmujemy  v ze STOSU i cofamy
się do wierzchołka będącego na stosie pod spodem.
Algorytm przeszukiwania drzewa metodÄ…  wszerz
ÁÄ…
" Odwiedzamy korzeń drzewa i wkładamy go do KOLEJKI;
" Dopóki KOLEJKA nie jest pusta, powtarzamy:
" bierzemy jeden wierzchołek  v z początku KOLEJKI;
" odwiedzamy wszystkich synów wierzchołka  v i wkładamy je na
koniec kolejki.
2
Teoria liczb
Algorytm Euklidesa
Aby obliczyć największy wspólny dzielnik dwóch dodatnich liczb naturalnych a,
b, powtarzamy aż do skutku:
a×b`"0
" dopóki , wykonuj:
a‡Ä…0
" jeżeli , to a := a mod b,
" w przeciwnym wypadku b := b mod a.
aƒÄ…b
" NWD(a, b) = ,
Rozszerzony algorytm Euklidesa
Dane wejściowe: dwie liczby naturalne a,b.
Dane wyjściowe: NWD(a, b) oraz liczby całkowite x,y takie, że
xa + yb = NWD(a, b).
xa :=1, ya :=0, xb :=0, yb :=1,
" podstaw:
a×b`"0
" dopóki , wykonuj:
a‡Ä…0
" jeżeli , to a := a mod b,
xa := xa - xb × Å›Ä…a÷b źą
;
ya := ya - yb × Å›Ä…a÷bźą
;
" w przeciwnym wypadku: b := b mod a,
xb := xb - xa × Å›Ä…b÷aźą
;
yb := yb - ya × Å›Ä…b÷aźą
;
" NWD(a, b): = a + b.
x := xa , y := y
" Jeżeli a > 0 , to ;
a
x := xb , y := yb .
" Jeżeli b > 0 , to
3
Spis treści
Teoria grafów........................................................................................................................................1
Algorytm wyznaczania kodu Prufera..............................................................................................1
Algorytm otrzymywania drzewa z kodu..........................................................................................1
Algorytm obliczania wartości wyrażenia w postaci postfixowej....................................................2
Algorytm przeszukiwania drzewa metodą  wgłąb ........................................................................2
Algorytm przeszukiwania drzewa metodÄ…  wszerz .......................................................................2
Teoria liczb...........................................................................................................................................3
Algorytm Euklidesa.........................................................................................................................3
Rozszerzony algorytm Euklidesa.....................................................................................................3
4