1.3.4. Tranzitivitás
Tranzitív reláció: Egy H
halmazon értelmezett ρ binér relációt
akkor mondunk tranzitívnak, ha bármely a,b,c H-ra a ρ b és b ρ c-ből következik, hogy a ρ c.
Példák tranzitív relációkra:
- A pozitív természetes számok halmazán: a kisebb b-nél.
- A pozitív természetes számok halmazán: a osztója b-nek.
- A sík valamennyi háromszögének a halmazán: a hasonló b-hez.
- A sík valamennyi egyenesének a halmazán: a párhuzamos b-vel.
- Az A részhalmaza B-nek (A
B).
Megjegyzés.
A tranzitív reláció gráfreprezentációjában az egymással tranzitív relációban lévő elemekhez tartozó irányított utak hossza legalább 2.