Relacija je matematično orodje, s katerim opišemo odnos med elementi množic. V matematiki se z relacijami srečujemo pogosto, pri čemer so primeri relacij: enakost (), relacija "manjše ali enako" (), inkluzija množic () in deljivost števil (). Slednji primeri relaciji so dvomestne ali binarne relacije – možno pa je definirati tudi relacije za več elementov iz več različnih množic.[1]
Relacijski graf :
Formalno je (dvomestna) relacija iz množice v množico podmnožica kartezičnega produkta:
.
Ponavadi uporabimo zapis ( je v relaciji z ), da označimo dejstvo, da je .
Relacija "je večje kot" v množici naravnih števil. Relacija je enaka: . Vmesni način zapisa je veliko bolj naraven kot zapis .
Vsaka funkcija je enočlena relacija, saj je njen graf . Pri funkciji vsakemu priredimo natanko en . Torej ima lastnost enoličnosti. To pri splošni relaciji ni nujno, poleg tega pa je element lahko povezan z več elementi iz .
Naj bo relacija v množici . Definicijsko območje relacije , označeno z , je množica vseh prvih koordinat parov iz relacije . Zaloga vrednosti relacije , označena z , je množica vseh drugih koordinat parov iz relacije :[2]
Na primer, za relacijo je definicijsko območje , zaloga vrednosti pa .
Zgornje lastnosti relacij se odražajo tudi grafično na relacijskem grafu. Na primer, če je refleksivna, potem je v vsaki točki relacije grafa zanka (zanka v je usmerjena povezava, ki povezuje vozlišče samo s seboj). Če je simetrična, potem vse povezave v nastopajo v parih. To pomeni, da če imamo povezavo od do , obstaja tudi obratna povezava. Če je tranzitivna, potem velja – če iz nekega vozlišča grafa lahko pridemo v drugo v dveh korakih, lahko pridemo tudi v enem.
Ovojnica relacije je najmanjša relacija z določeno lastnostjo , ki vsebuje dano relacijo. Najpogosteje obravnavane ovojnice so refleksivna ovojnica, simetrična ovojnica, tranzitivna ovojnica in tranzitivno-refleksivna ovojnica. Refleksivna ovojnica relacije je enaka , njena simetrična ovojnica pa je enaka .
Tranzitivno ovojnico relacije označimo z . Je unija vseh pozitivnih potenc relacije :
Tranzitivno-refleksivno ovojnico relacije označimo z , definirana je zelo podobna kot . Velja da je unija vseh nenegativnih potenc relacije :
Naj bo relacija na množici . Relacija sama po sebi ni tranzitivna, saj na primer velja in , ampak ne velja . Da lahko pridelamo v tranzitivno relacijo, ji moramo dodati vse pare, ki manjkajo zaradi tranzitivnosti. Tranzitivna ovojnica je torej:
↑Tepeh, Aleksandra; Škrekovski, Riste; Univerza v Mariboru, Fakulteta za elektrotehniko, računalništvo in informatiko; Univerza v Ljubljani, Fakulteta za matematiko in fiziko (2018). Diskretna matematika (v angleščini). Univerzitetna založba Univerze v Mariboru. doi:10.18690/978-961-286-152-0. ISBN978-961-286-152-0.{{navedi knjigo}}: Vzdrževanje CS1: več imen: seznam avtorjev (povezava)