2. Relációk fogalma, megadási módjai, tulajdonságai

2.1. Descartes-féle szorzat

Legyen A és B két tetszőleges halmaz, a∈A és b∈B. Ekkor (a,b)-t az 'a' és 'b' elemekből képzett rendezett párnak nevezzük, ahol
– 'a' az (a,b) rendezett pár első komponense vagy tagja,
– 'b' pedig az (a,b) rendezett pár második komponense vagy tagja.

Legyenek (a,b) és (c,d) rendezett párok. Ekkor (a,b)=(c,d) akkor és csak akkor teljesül, ha a=c és b=d teljesül, azaz a rendezett párok megfelelő komponensei egyenlők.

Legyen 'A' és 'B' két tetszőleges halmaz. Ekkor az 'A' és 'B' halmazok elemeiből képzett rendezett párok halmazát, azaz az
AΧB = { (a,b) | a∈A, b∈B}
halmazt az 'A' és 'B' halmazok Descartes-féle szorzatának vagy direkt szorzatának nevezzük.

Ha az 'A' és 'B' halmazok végesek, valamint |A|=n, |B|=m (n, m∈ℕ⁺), akkor |AΧB|=n*m, vagyis az 'A' és 'B' halmazok direkt szorzatának elemszáma a direkt szorzat tényezőit alkotó halmazok elemszámának szorzata.

Az 'A' halmaz önmagával képzett Descartes-szorzatát az 'A' halmaz 2-ik hatványának ("négyzetének") nevezzük és A² ⇋ AΧA módon jelöljük; az 'A' halmaz önmagával vett n-szeres Descartes-szorzatát (n≥2) pedig az 'A' halmaz n-ik hatványának nevezzük és Aⁿ ⇋ AΧAΧ...ΧA módon jelöljük.

---

Például legyen

A = {"fehér", "piros", "kék", "zöld", "fekete"} és
B = {"Audi", "Mercedes", "Ford"}.

Az 'A' és 'B' halmazok direkt szorzata:

AΧB = {("fehér","Audi"), ("piros","Audi"), ("kék","Audi"), ..., ("fehér","Mercedes"), ("piros","Mercedes"), ("kék","Mercedes"), ..., ("kék","Ford"), ("zöld","Ford"), ("fekete","Ford")}

Mivel |A|=5 és |B|=3, emiatt |AΧB|=5*3=15.

Az AΧB direkt szorzatot ábrázolhatjuk egy 5x3-as mátrix (táblázat) formájában (a táblázat fejsorát és fejoszlopát csak a jobb megértés kedvéért ábrázoltuk):

	Audi	Mercedes	Ford
fehér	(fehér, Audi)	(fehér, Mercedes)	(fehér, Ford)
piros	(piros, Audi)	(piros, Mercedes)	(piros, Ford)
kék	(kék, Audi)	(kék, Mercedes)	(kék, Ford)
zöld	(zöld, Audi)	(zöld, Mercedes)	(zöld, Ford)
fekete	(fekete, Audi)	(fekete, Mercedes)	(fekete, Ford)

Az AΧB direkt szorzatot ábrázolhatjuk egy 15x2-as táblázat formájában is:

Szín	Autómárka
fehér	Audi
piros	Audi
kék	Audi
...	...
fehér	Mercedes
piros	Mercedes
kék	Mercedes
...	...
kék	Ford
zöld	Ford
fekete	Ford

2.2. Relációk

Legyen 'A' és 'B' két tetszőleges halmaz. Ekkor az AΧB Descartes-szorzat bármely
ρ ⊆ AΧB
részhalmazát az 'A' és 'B' halmazok közötti relációnak vagy megfeleltetésnek nevezzük. Ha A=B teljesül, homogén relációról, ha pedig A≠B teljesül, inhomogén relációról beszélünk. (Egyes szerzők a homogén relációk esetében használják a 'reláció' megnevezést, és az inhomogén relációkat nevezik megfeleltetéseknek.)

Ha 'A' és 'B' véges halmazok, akkor elvileg közöttük annyi különböző megfeleltetés létesíthető, ahány lehetséges (különböző) részhalmaza van az AΧB direkt szorzatnak. Ez a direkt szorzat hatványhalmazának^⇒ elemszáma, vagyis ha |A|=n és |B|=m (n, m∈ℕ⁺), akkor a lehetséges megfeleltetések száma 2^n*m.

Ha A=B, akkor a 'ρ' relációt az A-n értelmezett kétváltozós vagy binér relációnak nevezzük; a továbbiakban kétváltozós vagy binér reláció alatt mindig homogén relációt értünk.

• Ha 'ρ' az A-n értelmezett kétváltozós (binér) reláció, akkor ρ⊆AΧA teljesül.
• Az Aⁿ=AΧAΧ...ΧA n-szeres Descartes-szorzatnak (azaz az 'A' halmaz n-edik hatványának^⇒) bármely részhalmazát n-változós homogén relációnak nevezzük.

Ha (a,b)∈ρ teljesül, akkor az 'a' és 'b' elemek relációban vannak egymással. Ezt ρ(a,b) vagy (a ρ b) módon jelöljük. Példák:

• az I osztály tanulói között értelmezett
  τ = {(x,y) | x∈I, y∈I, szomszédok(x,y)} ⊆ IΧI
  szomszédsági reláció jelentése:
  τ(x,y) ⇋ "az 'x' tanuló szomszédja az 'y' tanulónak"
• a természetes számok között értelmezett
  σ = {(a,b) | a∈ℕ, b∈ℕ, ∃q∈ℕ (b=q*a)} ⊆ ℕΧℕ
  oszthatósági reláció jelentése:
  σ(a,b) ⇋ "az 'a' természetes szám osztója a 'b' természetes számnak"
  • az oszthatósági reláció szokásos jelölése: σ(a,b) ⇋ a|b
• egy I alaphalmaz 2^I hatványhalmazán értelmezett
  Φ = {(A,B) | A∈2^I, B∈2^I, A⊆B} ⊆ 2^IΧ2^I
  részhalmaz reláció jelentése:
  A⊆B ⇋ "minden a∈A esetén a∈B teljesül"^⇒

---

Példaként tekintsük a következő halmazokat:

   A = {"fehér", "piros", "kék", "zöld", "fekete"} és
   B = {"Audi", "Mercedes", "Ford"}.

A színek halmazának (A) és a autómárkák halmazának (B) direkt szorzatán adjunk meg egy
   ξ⊆AΧB
relációt pl. a következőképpen:

ξ = {("fehér","Audi"), ("kék","Audi"), ("fehér","Mercedes"), ("piros","Ford")}

Értelmezzük a ξ relációt a következőképpen:
ξ(x,y) ⇋ "az 'x' színű autóból jelenleg 'y' márkájú autó van raktáron"

A ξ reláció ismeretében például feltehetjük az alábbi kérdést: ha fehér színű autót szeretnénk, milyen márkák vannak jelenleg raktáron? A választ az alábbi halmaz elemei adják meg:
{y∈B | ξ("fehér",y)}

A ξ relációt ábrázolhatjuk például nyíldiagrammal:

A ξ relációt ábrázolhatjuk egy "rács" segítségével is:

A fenti ábra 90 fokkal elforgatva:

Az AΧB direkt szorzatot ábrázoló egy 5x3-as mátrixban (vagy táblázatban) jelöljük be azokat az elempárokat, amelyek a ξ reláció elemei:

	Mercedes	Ford	Audi
fehér	(fehér, Mercedes)	(fehér, Ford)	(fehér, Audi)
piros	(piros, Mercedes)	(piros, Ford)	(piros, Audi)
zöld	(zöld, Mercedes)	(zöld, Ford)	(zöld, Audi)
kék	(kék, Mercedes)	(kék, Ford)	(kék, Audi)
fekete	(fekete, Mercedes)	(fekete, Ford)	(fekete, Audi)

---

Egy másik példaként tekintsük a következő halmazokat:

   A = {gyümölcsök nevei} és
   B = {1,2,3,...,67}.

A gyümölcsnevek halmazának (A) és az 1 és 67 közötti természetes számok halmazának (B⊆ℕ) direkt szorzatán adjunk meg egy
   η⊆AΧB
relációt a következőképpen:

η(a,n) ⇋ "az 'a' gyümölcsnév hossza pontosan 'n' darab betű"

Döntsük el, hogy az alábbi állítás igaz-e:

η("alma",4)    

---

Lássunk egy példát binér relációra. Legyen
   A = {1, 2, 3, 4, 5, 6}
és értelmezzük a
   γ⊆AΧA
binér relációt a következőképpen:
   γ = {(1,2), (1,4), (2,4), (2,5), (3,6), (4,5), (5,4), (5,5)}

A γ binér relációt ábrázolhatjuk egy irányított gráffal, ahol a gráf csúcsai (vagy csomópontjai) az 'A' halmaz elemeinek felelnek meg, és az a∈A pontból a b∈A pontba mutató irányított élt (nyilat) akkor és csak akkor ábrázoljuk, ha (a,b)∈γ teljesül.

Ennek megfelelően a γ relációt ábrázoló gráf a következő:

Feladat: próbáljunk meg olyan modelleket konstruálni, amelyekben a fenti relációhoz jelentést rendelünk!

---

Lássunk egy további példát egy binér relációra. Legyen az 'A' halmaz a gyümölcsnevek halmaza, azaz
   A = {gyümölcsök nevei}.

A gyümölcsnevek halmazának (A) önmagával vett direkt szorzatán adjunk meg egy
   θ⊆AΧA
relációt a következőképpen:

θ(a,b) ⇋ "az 'a' és 'b' gyümölcsnevek hossza megegyezik"

Ekkor például
   θ("alma","alma"), azaz ("alma","alma")∈θ,
   θ("barack","szilva"), azaz ("barack","szilva")∈θ,
   θ("szilva","barack"), azaz ("szilva","barack")∈θ.

Ezzel szemben például
   ("alma","citrom")∉θ és
   ("dinnye","dió")∉θ.

A θ relációt véges 'A' halmaz esetén ábrázolhatjuk például irányított gráf formájában. Értelmezzük a θ relációt az

A={"alma", "banán", "barack", "citrom", "dinnye", "dió", "eper", "körte", "mogyoró", "narancs", "szilva"}

halmazon, és ábrázoljuk a θ relációt:

Vegyük észre, hogy az azonos hosszúságú gyümölcsnevek diszjunkt^⇒ elemhalmazokba, osztályokba csoportosíthatók.

---

Egy további példaként vegyük az I = {piros, zöld, kék} alaphalmaz A, B∈2^I részhalmazait és ábrázoljuk a köztük értelmezett "'A' részhalmaza 'B'-nek" (A⊆B) binér relációt táblázatos formában! (Rövidítésként "piros" helyett "p"-t, "zöld" helyett "z"-t, és "kék" helyett "k"-t fogunk használni. Vegyük észre, hogy a táblázat által megjelenített tartalom minden három elemű halmaz esetében ugyanaz lesz. Például p↔a, z↔b, és k↔c helyettesítéseket végrehajtva a táblázat megadja az I={a,b,c} halmaz összes részhalmazát és ezek tartalmazási viszonyait.)

A⊆B	←B→
↓A↓	∅	{p}	{z}	{k}	{p,z}	{p,k}	{z,k}	{p,z,k}
∅
{p}
{z}
{k}
{p,z}
{p,k}
{z,k}
{p,z,k}
↑A↑	∅	{p}	{z}	{k}	{p,z}	{p,k}	{z,k}	{p,z,k}

A fenti táblázat a korábban bevezetett Φ⊆2^IΧ2^I részhalmaz reláció^⇒ kétdimenziós megjelenítése három elemű I alaphalmaz esetén.

2.3. Inverz reláció

Legyen 'A' és 'B' két tetszőleges halmaz, és ρ⊆AΧB az 'A' és 'B' halmazok közötti reláció. Ekkor a
ρ⁻¹ ⊆ BΧA = {(b,a) | a∈A, b∈B, ρ(a,b)}
relációt a ρ reláció inverz relációjának nevezzük.

Az inverz reláció definíciójából következik, hogy ρ⁻¹(b,a) akkor és csak akkor teljesül, ha ρ(a,b) teljesül. Példák:

• az I osztály tanulói között korábban értelmezett τ⊆IΧI szomszédsági reláció inverze
  τ⁻¹ ⊆ IΧI = {(y,x) | x∈I, y∈I, τ(x,y)};
  az inverz reláció jelentése:
  τ⁻¹(y,x) ⇋ "az 'y' tanulónak szomszédja az 'x' tanuló"
  (vegyük észre, hogy tetszőleges 'a' és 'b' tanulókra τ(a,b) teljesüléséből következik τ(b,a), azaz τ⁻¹(a,b) teljesülése; az ilyen tulajdonságú relációkat szimmetrikus relációknak^⇒ nevezzük)
• a természetes számok között korábban értelmezett σ⊆ℕΧℕ oszthatósági reláció inverze
  σ⁻¹ ⊆ ℕΧℕ = {(b,a) | a∈ℕ, b∈ℕ, a|b};
  az inverz reláció jelentése:
  σ⁻¹(b,a) ⇋ "a 'b' természetes szám osztható az 'a' természetes számmal", vagy
  σ⁻¹(b,a) ⇋ "a 'b' természetes szám többszöröse az 'a' természetes számnak"
  (Az a, b∈ℕ természetes számokra σ(a,b) és σ(b,a), azaz σ⁻¹(a,b) akkor és csak akkor teljesül egyszerre, ha a=b teljesül; az ilyen tulajdonságú relációkat antiszimmetrikus relációknak^⇒ nevezzük. Az egész számok körében azonban az oszthatósági reláció már nem antiszimmetrikus!)
• a természetes számok között értelmezett "kisebb, mint" (<), ill. "kisebb-egyenlő, mint" (≤) reláció inverze a "nagyobb, mint" (>), ill. "nagyobb-egyenlő, mint" (≥) reláció: az x, y∈ℕ természetes számokra y>x (ill. y≥x) pontosan akkor teljesül, ha x<y (ill. x≤y) teljesül
  
• az I alaphalmaz 2^I haványhalmazán értelmezett részhalmaz reláció (⊆) inverze a tartalmazási reláció (⊇): az A, B∈2^I halmazokra B⊇A pontosan akkor teljesül, ha A⊆B teljesül (azaz az 'A' halmaz a 'B' halmaz részhalmaza). A tartalmazási reláció jelentése:
  B⊇A ⇋ "a 'B' halmaz tartalmazza az 'A' halmazt"
  

---

Vizsgáljuk meg ismét^⇒ a színek és autómárkák kapcsolatát leíró példát:

   A = {"fehér", "piros", "kék", "zöld", "fekete"} és
   B = {"Audi", "Mercedes", "Ford"}.

A színek halmazának (A) és a autómárkák halmazának (B) direkt szorzatán korábban értelmeztük az alábbi relációt:
   ξ⊆AΧB
   ξ = {("fehér","Audi"), ("kék","Audi"), ("fehér","Mercedes"), ("piros","Ford")}.

A ξ reláció inverze:
   ξ⁻¹⊆BΧA
   ξ⁻¹ = {("Audi","fehér"), ("Audi","kék"), ("Mercedes","fehér"), ("Ford","piros")}

Értelmezzük a ξ⁻¹ inverz relációt a következőképpen:
ξ⁻¹(y,x) ⇋ "az 'y' márkájú autóból jelenleg 'x' színű van raktáron"

A ξ⁻¹ reláció ismeretében például feltehetjük az alábbi kérdést: ha Ford márkájú autót szeretnénk, milyen színűek vannak jelenleg raktáron? A választ az alábbi halmaz elemei adják meg:
{x∈A | ξ⁻¹("Ford",x)}

A ξ⁻¹ inverz relációt is ábrázolhatjuk nyíldiagrammal:

2.4. A kétváltozós (binér) relációk fontosabb tulajdonságai

Legyen 'A' tetszőleges halmaz, amelyen értelmezett az '=' reláció. Legyen továbbá ρ⊆AΧA kétváltozós (binér) reláció. Értelmezzük az alábbi tulajdonságokat:

(1) reflexivitás – irreflexivitás – egyik sem

• reflexivitás: minden a∈A elemre (a,a)∈ρ teljesül (azaz minden elem relációban van önmagával)
  Például a természetes számokon értelmezett
  • oszthatóság ( | ) reflexív reláció, mivel minden természetes szám osztója önmagának
  • egyenlőség ( = ) reflexív reláció, mivel minden természetes szám egyenlő önmagával
• irreflexivitás: minden a∈A elemre (a,a)∉ρ teljesül (másképpen megfogalmazva: nincs olyan a∈A elem, amelyre (a,a)∈ρ teljesül) (azaz egyetlen elem sincs relációban önmagával)
  Például a természetes számokon értelmezett
  • "kisebb, mint" ( < ) és "nagyobb, mint" ( > ) relációk irreflexívek, mivel egyetlen természetes szám sem kisebb (vagy nagyobb) önmagánál

(2) szimmetria – antiszimmetria – aszimmetria – egyik sem

• szimmetria: ha az a∈A és b∈A elemekre (a,b)∈ρ teljesül, akkor ebből (b,a)∈ρ teljesülése következik (azaz a relációban álló elemek kölcsönösen relációban vannak egymással)
  Például a természetes számokon értelmezett
  • egyenlőség ( = ) szimmetrikus reláció
• antiszimmetria: ha az a∈A és b∈A elemekre (a,b)∈ρ és (b,a)∈ρ egyszerre teljesül, akkor ebből a=b teljesülése következik (másképpen megfogalmazva: tetszőleges a, b∈A, a≠b elemekre (a,b)∈ρ teljesüléséből (b,a)∉ρ következik; antiszimmetrikus reláció esetében azonban létezhet olyan a∈A elem, amelyre (a,a)∈ρ teljesül, mivel a=a nyilvánvalóan teljesül) (azaz egyetlen elem sincs kölcsönösen relációban egy másikkal, azonban önmagával relációban állhat)
  Például a természetes számokon értelmezett
  • "kisebb-egyenlő, mint" ( ≤ ) és "nagyobb-egyenlő, mint" ( ≥ ) relációk antiszimmetrikusak (vagyis egyrészt ha két n,m∈ℕ természetes számra n≤m és m≤n (vagy n≥m és m≥n) egyszerre teljesül, akkor n=m, azaz a két szám azonos, nem lehetnek különbözőek; másrészt bármely n∈ℕ természetes szám relációban áll önmagával, mivel n≤n és n≥n teljesül)
• aszimmetria: ha az a∈A és b∈A elemekre (a,b)∈ρ teljesül, akkor ebből (b,a)∉ρ teljesülése következik (azaz egyetlen elem sincs kölcsönösen relációban egy másik elemmel, és nem állhat relációban önmagával sem)
  Jegyezzük meg, hogy aszimmetrikus reláció esetében (a,a)∈ρ teljesüléséből (a,a)∉ρ következik, ami ellentmondás, vagyis nem létezik olyan a∈A elem, amelyre (a,a)∈ρ teljesül; tehát az aszimmetrikus reláció mindig irreflexív. Mivel különböző elemekre mind aszimmetrikus, mind antiszimmetrikus reláció esetében teljesül, hogy (a,b)∈ρ teljesüléséből (b,a)∉ρ teljesülése következik, az aszimmetrikus relációk mindig antiszimmetrikusak. A fenti két megállapítást úgy foglalhatjuk össze, hogy egy reláció akkor és csak akkor aszimmetrikus, ha antiszimmetrikus és irreflexív.
  Például a természetes számokon értelmezett
  • "kisebb, mint" ( < ) és "nagyobb, mint" ( > ) relációk aszimmetrikusak (és korábban láttuk, hogy irreflexívek is)

(3) tranzitivitás – nem teljesülő tranzitivitás

• tranzitivitás: ha az a∈A, b∈A és c∈A elemekre (a,b)∈ρ és (b,c)∈ρ teljesül, akkor ebből (a,c)∈ρ teljesülése következik (azaz ha egy elem relációban áll egy másikkal, ez pedig relációban áll egy harmadikkal, akkor az első elem relációban áll a harmadik elemmel is)
  Például a természetes számokon értelmezett
  • "kisebb, mint" ( < ), "nagyobb, mint" ( > ), "kisebb-egyenő, mint" ( ≤ ), "nagyobb-egyenlő, mint" ( ≥ ) és "egyenlő" ( = ) relációk tranzitívak
• Emeljük ki, hogy a tranzitivitás meghatározásában az a∈A, b∈A és c∈A elemek nem feltétlenül különbözők. Ennek következménye az, hogy
  – ha az a∈A, és b∈A elemek kölcsönösen relációban állnak, akkor tranzitív reláció esetén teljesülnie kell az (a,a)∈ρ és (b,b)∈ρ relációknak is;
  – a tranzitivitást akkor is értelmezni tudjuk, ha az 'A' halmaz egy- vagy kételemű.
  Például
  • ha (a,b)∈ρ és (b,a)∈ρ teljesül, akkor tranzitív reláció esetén ebből (a,a)∈ρ teljesülése következik;
  • ha (b,a)∈ρ és (a,b)∈ρ teljesül, akkor tranzitív reláció esetén ebből (b,b)∈ρ teljesülése következik;
  • ha (a,a)∈ρ és (a,a)∈ρ teljesül, akkor ebből (a,a)∈ρ teljesülése nyilvánvalóan következik;
  • ha (a,a)∈ρ és (a,b)∈ρ teljesül, akkor ebből (a,b)∈ρ teljesülése nyilvánvalóan következik;
  • ha (a,b)∈ρ és (b,b)∈ρ teljesül, akkor ebből (a,b)∈ρ teljesülése nyilvánvalóan következik.

(4) trichotómia – nem teljesülő trichotómia

• linearitás vagy trichotómia: tetszőleges a∈A és b∈A elemekre vagy (a,b)∈ρ, vagy (b,a)∈ρ, vagy a=b teljesül; tehát ha a≠b különböző elemek, akkor az (a,b)∈ρ és (b,a)∈ρ relációk közül legalább az egyiknek teljesülnie kell (azaz bármely két különböző elem relációban áll egymással; az elemek közti reláció lehet kölcsönös is, és az elemek önmagukkal is relációban állhatnak)
  A fenti relációk közül legalább egynek mindig teljesülnie kell, de egyszerre akár több is teljesülhet (vö. Vajda 1996: 36). Szigorúbb feltétel, hogy a≠b esetén az (a,b)∈ρ és (b,a)∈ρ relációk közül pontosan az egyik teljesül (pl. Dringó-Kátai 1986: 28, Bonifert-Kovácsné Győri 1987: 32).^⇒
  Például a természetes számokon értelmezett
  • "kisebb-egyenlő, mint" ( ≤ ) és "nagyobb-egyenlő, mint" ( ≥ ) relációk trichotómak (és reflexívek)
  • "kisebb, mint" ( < ) és "nagyobb, mint" ( > ) relációk trichotómak (és irreflexívek)

A trichotómia lényege szemléletesen fogalmazva az, hogy egy trichotóm reláció segítségével egy halmaz bármelyik két (különböző) eleme összehasonlítható egymással. (Aszimmetrikus vagy antiszimmetrikus reláció esetén ennek a halmazok rendezésekor^⇒ nagy jelentősége lesz.)

---

A trichotómia fogalma nem egyértelműen jelenik meg a szakirodalomban. Például bevezethetjük az alábbi fogalmakat is (vö. MaYoR 2020):

• összefüggőség: tetszőleges a∈A és b∈A, a≠b elemekre az (a,b)∈ρ és (b,a)∈ρ relációk közül legalább az egyik teljesül;
• dichotómia: tetszőleges a∈A és b∈A, a≠b elemekre az (a,b)∈ρ és (b,a)∈ρ relációk közül pontosan az egyik teljesül.

A "megengedő" trichotómia esetében az összefüggőséget követeljük meg. A trichotómia "megengedő" meghatározása az a=b esetben nem mond semmit sem az elemek közti relációról (azaz mind (a,a)∈ρ, mind (a,a)∉ρ teljesülését megengedjük).

A "szigorú" trichotómia esetében a dichotómiát követeljük meg (amely magában foglalja az összefüggőséget). A "szigorú" trichotómia egyik elfogadott definíciója az, hogy bármely a, b∈I esetén a ρ(a,b), ρ(b,a) és a=b relációk közül pontosan egy teljesül; ebben az esetben, ha a=b, akkor sem ρ(a,b), sem ρ(b,a) nem teljesül, vagyis a reláció irreflexív. Ebben az értelemben például a < reláció trichotóm, de a ≤ reláció nem az.

---

Az egyes relációtulajdonságok szemléltetése gráfokkal

• reflexivitás: a gráf minden csomópontjához egy hurokél tartozik
  
• irreflexivitás: a gráf egyetlen csomópontjához sem tartozik hurokél
  
• szimmetria: a gráf minden összekötött (azaz relációban levő) csomópontját két, ellentétes irányú él köti össze (hurokélek is lehetségesek!)
  
• antiszimmetria: nem létezik két olyan összekötött csomópont, amelyet két, ellentétes irányú él köt össze (azaz a gráfban a relációban levő csomópontokat legfeljebb egy él kötheti össze); hurokélek azonban lehetségesek
  
• aszimmetria: nem létezik két olyan összekötött csomópont, amelyet két, ellentétes irányú él köt össze (azaz a gráfban a relációban levő csomópontokat legfeljebb egy él kötheti össze); hurokélek nem lehetségesek
  
• tranzitivitás: ha egy csomópontból egy másik csomóponton keresztül eljuthatunk egy harmadik csomópontba (a csomó­pontokat összekötő élek irányát követve), akkor az első csomó­pontból közvetlenül, egy lépésben (azaz egy összekötő élen keresztül) is eljuthatunk a harmadik csomópontba
  
• trichotómia: bármely két csomópont össze van kötve, és az összekötött csomópontok közül az egyikből mindig közvetlenül eljuthatunk a másik csomópontba; hurokélek lehetségesek (azonban a közvetlen visszajutást, azaz a két csomópontot ellentétes irányban összekötő párhuzamos éleket a trichotómia szigorúbb feltétele esetében nem engedjük meg)