Relace, binární relace a jejich reprezentace, operace s relacemi

Kartézský součin

• Kartézský součin $n$ množin je množina všech uspořádaných $n$-tic prvků z těchto množin $X_1\times ...\times X_n=\{<x_1,...,x_n>\mid x_1\in X_1,...,x_n\in X_n\}$
• Je-li $X_1=...=X_n=X$, pak píšeme $X^n$ a říkáme $n$-tá kartézská mocnina množiny X
• Velikost $\mid A\times B\mid$ je $\mid A\mid \times \mid B\mid$
• Relace mezi $X_1,...,X_n$ je libovolná podmnožina kartézského součinu $X_1\times ...\times X_n$

Pojem relace

• Relace je množina uspořádaných $n$-tic prvků

• Relace je určena:

  • Aritou vztahu = číslo udávající počet objektů, které do relace vstupují
  • Množiny, jejichž prvky do relace vstupují

• Relace je matematickým protějškem pojmu vztah

• Označuje se $R=\{<x_1,...,x_n>\}$

• Číslu $n$ říkáme arita relace $R$, $R$ se nazývá $n$-ární (unární, binární, ternární, …)

• $<x_1,...,x_n>=<y_1,...,y_m>$, právě když $n=m$ a $x_1=y_1,...,x_n=y_m$

Vztah a operace s relacemi

• Relace jsou speciální množiny (relace je podmmožina kartézského součinu) $\to$ lze s nimi provádět množinové operace a vztahy

• Rovnost (vztah)

  • Označujeme symbolem "$=$"
  • Pro každé $x$ platí: $x\in A$, právě když $x\in B$
  • Dvě množiny obsahují stejné prvky
  • Když $A=B$ říkáme, že množina A se rovná množině B
  • $A=B$ platí, právě když platí zároveň $A\subseteq B$ a $B\subseteq A$

• Inkluze (vztah)

  • Označujeme symbolem "$\subseteq$"
  • Pro každé $x$ platí: jestliže $x\in A$, pak $x\in B$
  • Všechny prvky množiny $A$ jsou také prvky množiny $B$
  • Když $A\subseteq B$ říkáme, že množna $A$ je podmnožinou množiny $B$

• Průnik (operace)

  • Označujeme symbolem "$\cap$"
  • $A\cap B=\{x\mid x\in A$ a $x\in B\}$
  • Prvek $x$ patří do $A\cap B$, právě když patří do A a zároveň do B
  • Společné prvky
  • Množiny $A$ a $B$ se nazývají navzájem disjunktní, právě když $A\cap B=\varnothing$

• Sjednocení (operace)

  • Označujeme symbolem "$\cup$"
  • $A\cup B=\{x\mid x\in A$ nebo $x\in B\}$
  • Prvek $x$ patří do $A\cup B$, právě když patří do A nebo do B
  • Spojení všech prvků v množinách

• Rozdíl (operace)

  • Označujeme symbolem "$-$"
    • $A-B=\{x\mid x\in A$ a $x\notin B\}$
    • Prvek $x$ patří do $A-B$, právě když patří do $A$, ale nepatří do $B$

• Inverze (operace)

  • Inverzní relací k relaci $R\subseteq X\times Y$ je relace $R^{-1}\subseteq Y\times X$
    • $R^{-1}=\{<y,x>|<x,y>\in R\}$
  • “Pořadí v relaci se převrátí”

• Skládání (operace)

  • Je-li $R\subseteq X\times Y$ a $S\subseteq Y\times Z$, pak složením relací je relace $R\circ S\subseteq X\times Z$
    • $R\circ S=\{<x,z>\mid$ existuje $y\in Y:<x,y>\in R$ a $<y,z>\in S\}$
  • “Přes společný prvek (tzv. prostředníka) spojím relace do jedné”

Binární relace a jejich reprezentace

• Základní způsoby reprezentace binárních relací je:

  • Maticí, Grafem, Seznamem seznamů

• Reprezentace maticí (tabulkou)

  • Máme relaci $R\subseteq X\times Y$, kde $X=\{x_1,...,x_m\}$ a $Y=\{y_1,...,y_n\}$. Relaci R repzentujeme maticí/tabulkou, ve které se na místě odpovídající řádku $i$ a sloupci $j$ nachází hodnota, která určuje, zda dvojici $<x_i,y_j>\in R$, nebo $<x_i,y_j>\notin R$
  • $M_R$ se nazývá matice relace $R$
  • Výhodou je přehlednost, nevýhodou je paměťová náročnost

  Pro relaci R = \set{<a,1>,<a,2>,<a,4>,<b,2>,<b,4>,<c,1>}

  

• Reprezentace orientovaným grafem

  • Graf binární relace $R\subseteq X\times X$ dostaneme tak, že:
    • Každý prvek $x\in X$ znázorníme v rovině jako kroužek s označením daného prvku
    • Pokud $<x,y>\in R$, nakreslíme z kroužku odpovídajícího $x$ do kroužku odpovídajícího $y$ orientovanou čáru s šipkou.

  Pro relaci R=\set{<a,b>,<a,d>,<b,d>,<c,a>}

• Reprezentace seznamem seznamů

  • Je vhodný pro uložení binární relace $R$ na množině $X$
  • Reprezentaci tvoří hlavní (spojový) seznam, ve kterém jsou uloženy všechny prvky množiny $X$.
  • Z každého prvku $x\in X$ hlavního seznamu vede seznam obsahující právě ty $y\in X$, pro každé $<x,y>\in R$
  • Reprezentace seznamem seznamů je paměťové úsporná a je vhodná pro počítačové zpracování

  Pro relaci R=\set{<a,b>,<a,d>,<b,d>,<c,a>}

Mocnina relace

• $n$-tou mocninu relace zavádíme pomocí skládání relací

  • $R^1=R$
  • $R^n=R\circ R^{n-1}$
    • $R^2=R\circ R$
    • $R^3=R\circ R^2=R\circ R\circ R$
  • Obecně neplatí $R^n\subseteq R^{n+1}$

• Nechť $R,S,T$ jsou binární relace na $X$, kde $S\subseteq T$

  • $S^{-1}\subseteq T^{-1}$
  • $R\circ S\subseteq R\circ T$ a $S\circ R\subseteq T\circ R$
  • Pokud $R$ je tranzitivní, pak $R^n\subseteq R$ pro každé $n\in \mathbb{N}$
  • $R^m\circ R^n=R^{m+n}=R^n\circ R^m$ pro každé $n\in \mathbb{N}$
  • Pokud je $X$ konečná a $<x,y>\in R^i$ pro každé $i>\mid X\mid$, pak $<x,y>\in R^m$ pro nějaké $m\le \mid X\mid$

Uzávěry relací

• Pro binární relaci $R$ na $X$ definujeme binární relace:
  • $Ref(R)$ = reflexivní uzávěr relace $R$
    • $Ref(R)=R\cup i{d}_x$
    • K relaci přidám relaci identity
  • $Sym(R)$ = symetrický uzávěr relace $R$
    • $Sym(R)=R\cup R^{-1}$
    • K relaci přidám inverzní relaci
  • $Tra(R)$ = tranzitivní uzávěr relace R
    • $Tra(R)$ = ${\cup }_{n=1}^{\infty }{R}^n$
    • Sjednocení nekonečně mnoho relací $R^1\cup ,...,\cup R^n$, pokud ale je R definována na konečné množině $X$, kde $\mid X\mid =n$, pak $Tra(R)={\cup }_{i=1}^n{R}^i$

Příklad

Navigace

Předchozí: Množiny, množinové operace, potenční množina, kartézský součin, číselné množiny, spočetné a nespočetné množiny Následující: Funkce (zobrazení) a jejich vlastnosti Celý okruh: 1. Teoretické základy informačních technologií