Analiză discretă

Clase de echivalență

Teorema. Să presupunem că A este dat și U este o relație de echivalență pe A × A. Setul de seturi
Ua = b | (a, b) Despre U>
formează (după îndepărtarea celor coincide) partiția setului A.

Dovada. În primul rând, dovedim că dacă seturile Ua și Ub se intersectează, atunci coincid. Într-adevăr, dacă b U Ua. aceasta înseamnă că (a, b) aproximativ U. Dar relația tranzitive (a, b) Despre U și (b, c) Despre U implică (a, c) aproximativ U. astfel încât Ua ⊂ Ub.

Din cauza simetriei relației, avem de asemenea 0 Ub. din care Ub ⊂ Ua. și prin urmare aceste seturi sunt egale.

Fiecare astfel de subset este evident neimpozabil - este determinat de un element care intră în el. Fiecare element al setului (evident, de asemenea) aparține uneia dintre aceste subseturi, deci avem o partiție.

Subgrupele discutate în teoremă sunt numite clase de echivalență. Vom avea nevoie de ele în curând.

Să presupunem că avem o relație U definită pe setul A. Este deseori necesar să închidem tranzit: pentru a construi un raport mai mare TU. care ar fi tranzitiv și, în același timp, cea mai mică din toate relațiile tranzitorii care conțin U.

TU: = U;
pentru că eu o fac
pentru j Despre A face
pentru k Despre A nu
dacă (j, i) Despre TU ∧ (i, k) Despre TU atunci
TU: = TU ∪
Fi
od
od
od

Aici od este brațul de închidere pentru a face. și fi este consola de închidere pentru dacă.

Algoritmul constă într-o atribuire inițială și un ciclu primitiv triplă cu variabilele i, j, k. în care dacă există perechi (j, i) și (i, k) în relație. atunci perechea (j, k) este inclusă în ea.

Trucul este că algoritmul funcționează corect numai dacă ciclul pentru "indexul intermediar" i este extern. Vom reveni la acest algoritm mai târziu. Va fi recomandabil să luați în considerare o parte din îmbunătățirea sa.

Relația transitivă antisimetrică U. dată pe setul A definește o ordine parțială a acestui set. Datorită lui, putem compara elementele între ele, dar nu toate elementele sunt comparabile.

Când specificăm o ordine parțială, dacă o pereche de elemente (a, b) aparține lui U, atunci spunem că a precede b. Dacă nici unul dintre aceste două elemente nu precede altul, ele spun că nu sunt comparabile.

Condiția antisimetrică este necesară pentru a exclude posibilitatea unor elemente echivalente. Condiția de tranziție este necesară pentru construirea lanțurilor.

Economistul italian Vilfredo Pareto (1848-1923) a sugerat utilizarea unei construcții în astfel de sarcini, care în onoarea sa este numită granița de frontieră Pareto. Acum o vom descrie.

În figură, setul A constă din puncte îndrăznețe trase pe plan. Un punct precede celălalt dacă ambele coordonate nu sunt mai mici decât coordonatele corespunzătoare celeilalte și cel puțin una dintre coordonate este strict mai mare. În acest caz, granița Pareto este formată din puncte pictate în roșu.

Relațiile multi-locale sunt utilizate pe scară largă într-unul dintre tipurile de baze de date.

Informațiile din baza de date relațională sunt stocate în tabele. și fiecare tabel este tratat ca o anumită relație multi-loc. De exemplu, să luăm un fragment al cărții de înregistrare a grupului de studenți (acestea sunt folosite în departamentul de studenți al biroului decan)

Fiecare linie a tabelului (numărul de serie pe linia de noi nu vom rang) poate fi privit ca un set de cinci elemente: (nume, №zach, Otm1, Otm2, Otm3). și deci ca element al produsului cartezian de cinci seturi SFIO × N × M1 × M2 × M3.

Astfel, fiecare astfel de tabel poate fi considerat o relație de cinci poziții.

În bazele de date relaționale, informațiile sunt specificate de un set de astfel de tabele-relații, iar toate acțiunile privind informațiile și cerințele pentru acestea sunt descrise în termenii acestor tabele.

1. Clasificarea relațiilor. Clase de echivalență.