« poprzedni punkt | następny punkt » |
Relacje porządku, tak jak inne relacje, można ilustrować przy pomocy grafów. Jednak zwykle duża liczba krawędzi i występujące pętle (jako konsekwencja zwrotności i przechodniości) sprawiają, że rysunek taki nie zawsze jest czytelny. Wygodnym sposobem przedstawiania porządku są natomiast diagramy Hassego.
Definicja 5.2
Diagramem Hassego relacji porządku á w zbiorze X nazywamy graf niezorientowany G = <X, E>, którego zbiorem wierzchołków jest zbiór X , a krawędzie są określone następująco
(x,y) Î
E wttw x á
y i nie istnieje zÎ
X, że z¹
x, y¹
x i x á
z i z á
y
Jeśli para (x,y) tworzy krawędź, to mówimy, że y jest bezpośrednim następnikiem x.
Zwykle, zamiast strzałek łączących wierzchołki w grafie zorientowanym, w diagramach Hassego krawędzie zaznaczamy odcinkami, w taki sposób, by koniec krawędzi znajdował się na rysunku powyżej początku krawędzi.
Rys. 5.2 Diagram Hassego
Przykład 5.2
(1) Relacja Í inkluzji w zbiorze wszystkich podzbiorów pewnego zbioru X jest relacją porządku częściowego. Oczywiście jest zwrotna, bo AÍ A. Jest też antysymetryczna, ponieważ A Í B i B Í A implikuje A=B. Relacja jest też przechodnia, bo z założeń A Í B i B Í C wynika natychmiast A Í C (por. punkt 1.2).
Zauważmy, że nie wszystkie zbiory należące do P(X) dają się porównać przy pomocy relacji Í . Jeśli x i y są różnymi elementami zbioru X, to mamy {x}Î P(X), {y}Î P(X), ale ani nie zachodzi {x}Í {y}, ani nie zachodzi {y}Í {x}.
Diagram Hassego relacji Í w przypadku, gdy X = {R,G,B} przedstawiono na rysunku 5.2a.
(2) Relacja podzielności | określona w zbiorze liczb naturalnych
x|y wttw x jest dzielnikiem y
jest relacją porządku. Rzeczywiście, relacja podzielności (por. przykład 2.7) jest zwrotna, antysymetryczna i przechodnia. Na rysunku 2.6b przedstawiono graf tej relacji ograniczonej tylko do zbioru {1, 2, 3, ...9}. Rysunek 5.2b przedstawia diagram Hassego tej relacji. Podobnie jak w poprzednim przykładzie, istnieją takie liczby naturalne, których nie możemy porównać przy pomocy |. Na przykład 2 nie jest dzielnikiem 3 i 3 nie jest dzielnikiem 2.
(3) Niech S = {0, 1}. W zbiorze S* zdefiniujemy relację á następująco:
w á w' wttw istnieje słowo w" Î S*, że ww" = w'.
Słowo ww "zostało utworzone ze słowa w przez dopisanie na jego końcu słowa w". Taką operacje na słowach nazywamy konkatenacją. Na przykład, konkatenacja słów "para" i "lotnia" daje słowo "paralotnia".
Jeżeli w' á w, to mówimy, że w' jest segmentem początkowym lub prefiksem słowa w. Relacja á w zbiorze {0,1}* definiuje porządek częściowy. Diagram Hassego tego porządku, z konieczności ograniczyliśmy do kilkunastu elementów, por Rys.5.3. Sam zbiór {0,1}* jest przecież nieskończony.
Rys. 5.3 Diagram Hassego relacji częściowego porządku w zbiorze słów na alfabetem {0,1}, por. przykład 5.2(3).
Uwaga.
Pytanie 3: Czy istnieje diagram Hasse dla zbioru uporządkowanego <Q, £ >?
Zobacz odpowiedź« poprzedni punkt | następny punkt » |