145147920076615490224844235907 n

Relacja sąsiedztwa A w zbiorze wierzchołków \\G) jest określona następująco: (v. u') e A wtedy i tylko w tedy gdy wierzchołek v jest sąsiedni z wierzchołkiem w.

Relacja osiągalności R w zbiorze HG) jest zdefiniow ana następująco:

(v, w) e R jeżeli istnieje w G droga o długości co najmniej I od v do w.

Relacje w zbiorach częściowo uporządkowanych - przestrzenie z relacją

Zbiór uporządkowany zbiór, którego elementy można ze sobą porównywać.

Relacja porządku w' zbiorze S struktura niosąca informację na temat sposobu porównywania elementów zbioru S.

Częściowy porządek w zbiorze .V to relacja R, która jest zwrotna, antysymetryczna i przechodnia.

Zamiast (x,y) ? R można stosować zapis x < y i wtedy:

(Z) s < s dla każdego s w S;

(AS)    s * l i I < s implikują s = i:

(P)    s < / i t 3 u implikująs < u.

Zbiór częściowo uporz.ądkow any jest określony przez parę (.V. ■<). x ■< y w tedy i tylko wtedy, gdy x < y i x ^ y x x y wtedy i tylko wtedy, gdy x -< y lubx-y

Element t nakryw a element .v. gdy ,v x n nie ma w- S elementu u takiego, że v -< u< t.

Diagram Hassego zbioru częściowo uporządkowanego (5,^) jest to rysunek grafu skierowanego, w którym od wierzchołka t do wierzchołka s krawędź biegnie wtedy i tylko wtedy, gdy / nakrywa v. Diagramy Hassego rysuje się z krawędziami skierowanymi w dół i bez strzałek.

Poniższy rysunek przedstawia diagram Hassego dla S (I. 2, 3. 4. 5, 6} dla relacji min (w dzieli n, tzn. n jest całkowitą wielokrotnością m).

4    6

Twierdzenie

Każdy skończony zbiór częściowo uporządkowany ma diagram Hassego.

sir 10/15