1457574200766154062227P9149800 n

i»

Relacje

Relacja dw uargumentow ą na zbiorze S * T jest dowolny podzbiór R zbioru 5 * T.

R C.S ' T

Relacją w zbiorze 5 jest podzbiór R zbioru S * S.

Relacja kongrucncji w zbiorze liczb całkowitych Z zachodzi pomiędzy liczbami całkowitymi m i n gdy liczba m przystaje do liczby /; modułu p (p jest liczbą całkowitą większą niż 1). Oznacza to. że ni - n jest wielokrotnością/?. m - n (mod p)

Kjąsyfikaciaje|ącti.porządkuiących (dla relacji R w zbiorź.ę■S’J:

(Z) relacja zw rotna:

(PZ) relacja przeciw zw rotna: (S) relacja symetry czna: (AS) relacja anty symetry czna: (P) relacja przechodnia: Relacja jest spójna jeśli:

Relacja równoważności: Relacja ąuasiporządku: Relacja porządku:

Relacja porządku liniowego:

(x, x) e R dla wszystkich x e S,

(,x, x) g R dla wszystkich x € S.

(a*, y) e R implikuje (y, x) e R dla wszystkich x.y e S. (.v.y) e R i (y, x) e R implikują x = y.

(x, y) e R i (y, z) e R implikują (.v, z) e R.

(x, y) € R lub (y, at) e R lub .t = y.

zwrotna, symetryczna i przechodnio zwrotna i przechodnia zwrotna, przechodnia i antysymetryczna zwrotna, przechodnia, antysymetryczna i spójna

Relacją odwrotną do relacji R na zbiorze S * Tjest relacja R~ na zbiorze T * S zdefiniowana wzorem:

FT = {(y. x) e T*S: (x,y)eR\

Grafy

Graf skierowany (digraf) G składa się z dwóch zbiorów, niepustego zbioru l'(G) wierzchołków grafu (7 i zbioru E(G) krawędzi grafu G oraz z funkcji y zc zbioru E(G) w zbiór r«J) x V\G).

Jeśli e jest krawędzią grafu G i y(e) = (p, q) to: p jest początkiem krawędzi e. a ą jest końcem krawędzi e. p i ą są również nazywane wierzchołkami e.

Drogą w grafie skierowanym G jest ciąg krawędzi taki. że koniec jednej krawędzi jest początkiem następnej.

Długością drogi jest liczba krawędzi stanowiących drogę

Droga łącząca ciąg wierzchołków X\X2..*x„ jest drogą zamkniętą jeśli X\ = .v_n.

Cykl jest drogą zamkniętą o długości co najmniej 1 z ciągiem wierzchołków .vi.r:..-t»Y|.

Graf acykliczny - graf skierowany nie mający cykli.

Pętla - krawędź z jednym końcem (wierzchołkiem).

Krawędzie e i/są nazywane w iclokrotnymi jeśli y(e) = ;■(/).

Wierzchołek v jest sąsiedni w stosunku do wierzchołka w jeśli w £(G) istnieje krawędź od v do w.

str. V 15