Relationen

Definition Das kartesische Produkt  "A × B " ist die Menge aller Paare, deren linke Komponente aus der linken Menge des Produkts und deren rechte Komponenten aus der rechten Menge des Produkts stammt.

Zweistellige Relationen

Definition Eine zweistellige Relation  (binary relation ) zwischen "A " und "B " ist jede Teilmenge des kartesischen Produkts "A  × B ". Die Elemente der Relation werden auch „Kanten “ genannt.

Bemerkung Wenn von einer „Relation“ gesprochen wird, ist hier bis auf weiteres eine binäre Relation damit gemeint.

Vorgänger und Nachfolger

Definition Der Vorbereich  (domain ) einer Relation ist die Menge "{ a  | a  ∈ A ∧ ∃b  ∈ B .(a , b ) ∈ R  }", also die Menge der ersten Komponenten der Elemente von "R ".

Definition Der Nachbereich  (codomain ) einer Relation "R " ist die Menge "{ b  | b  ∈ B  ∧ ∃a .(a , b ) ∈ R  }", also die Menge der zweiten Komponenten der Elemente von "R ".

Definition Der Selektion  eines Wertes "a₀ " ist die Menge aller Paare einer gegebenen Relation "R " mit diesem Wert als erster Komponente "{ (a , b ) | ∃a .∃b .(a , b ) ∈ R  ∧ a  = a₀  }".

Definition Ein direkter Nachfolger  (direct successor ) eines Wertes "a " ist jeder Wert "b  ∈ B " für den "(a , b ) ∈ R ". Ein direkter Nachfolger eines Wertes wird manchmal auch nur als Nachfolger  des Wertes bezeichnet, wenn dadurch keine Mißverständnisse zu befürchten sind.

Definition Ein direkter Vorgänger  (direct predecessor ) eines Wertes "b " ist jeder Wert "a  ∈ A " für den "(a , b ) ∈ R ". Ein direkter Vorgänger eines Wertes wird manchmal auch nur als Vorgänger  des Wertes bezeichnet, wenn dadurch keine Mißverständnisse zu befürchten sind.

Definition Die Menge der (direkten )Nachfolger  (successor set ) eines Wertes "a " wird auch mit "R (a )" (das Bild von "a " unter "R ", the image of  "a " under  "R ") oder "R ({a })" (das Bild des Singletons "{a }" unter "R ", the image of the singleton  "{a }" under  "R ") bezeichnet und ist "{ b  | b  ∈ B  ∧ (a , b ) ∈ R }". Dies nennt man auch den Schnitt von "R " nach "a " oder man spricht von der Selektion von "a ", gefolgt von der Projektion auf "B ".

Definition Die Menge der (direkten )Vorgänger  (predecessor set ) eines Wertes "b " wird auch mit "R ⁻¹(b )" bezeichnet und ist "{  a  | a  ∈ A ∧ (a , b ) ∈ R }". Dies nennt man auch den Schnitt von "R " nach "a " oder man spricht von der Selektion von "a ", gefolgt von der Projektion auf "B ".

Definition Der Nachfolgergrad  oder Ausgangsgrad  (out-degree ) eines Wertes "a " ist die Kardinalität der Menge "R (a )" der Nachfolger von "a ".

Definition Der Vorgängergrad  oder Eingangsgrad  (in-degree ) eines Wertes "b " ist die Kardinalität der Menge "R ⁻¹(b )" der Vorgänger von "b ".

Definition Eine Senke  (sink ) ist ein Wert mit Ausgangsgrad 0.

Definition Eine Quelle  (source ) ist ein Wert mit Eingangsgrad 0.