Relations, Properties, Directed Graphs, Composition of Relations

Relations

• A binary relation between two sets A and B is a subset $R$ of $A \times B$.
• A function $f$ from a set $X$ to a set $Y$, denoted $f : X \rightarrow Y$, is a subset of $X \times Y$, such that for every element $x \in X$ there is exactly one element $y \in Y$ such that $(x, y) \in f$.
• For a relation, the condition that for every element of the domain there should be a single element of the target is dropped.
• Consider the set of faculty members $F$ at the university and the set of students $S$ of that university, and the relation $R$ between a faculty member $f \in F$ and a student $s \in S$ that $f$ teaches a class that is taken by a student.
• A faculty member would be teaching multiple students.
• A student taking multiple courses would have multiple instructors.
• A faculty member might be on sabbatical and not be teaching a class in that semester.

Faculty - Student Example

• Let $F =${Alice, John, Mary}$and$S = ${David, Elizabeth, Karen, Richard, Sarah}$.
• Let $R =${(A, D), (A, E), (A, R), (A, S), (M, D), (M, E), (M, K)}$⊆$F \times S
• Representations:
  • Arrow Diagram
  • Matrix Representation

Relations on Infinite Sets

• Let A = ${2, 3}$ and define the relation $M$ between $A$ and $Z^+$ such that $a M x$ iff $x$ is an integer multiple of $a$
  • Examples: $2 M 2, 2 M 4, 2 M 6, . . . 3 M 3, M 6, . . .$
• Define the relation $C$ between the reals $R$ and $Z$ such that for $x \in R$ and $y \in Z$, $|x - y| \le 1$
  • Some examples: $0.9 C 1, 1.1 C 1, 1.1 C 2$
• Define the relation R between Z and Z such that $x R y$ iff $x \le y$. This is called a binary relation on a set.

Relations on a Set

• A binary relation on a set $A$ is a subset of $A \times A$.
• The set $A$ is called the domain of the binary relation.
• Let $A =${a, b, c, d, e}$and define the binary relation$R$on$A$as:$R = ${ (a, b), (b, c), (e, c), (c, e), (d, a), (d, d) }$
• Matrix Representation
• Arrow Diagram
• Simple Arrow Diagram

Relation Properties - Reflexive

• A relation on a set has the property of being reflexive if every element of the set is related to itself. That is, for all $x \in A$, $(x, x) \in R$.
• Example: Consider the set $A =${3, 4, 5, 6, 7, 8}$. Define relation$R$to be the set of pairs$(x, y)$where$2 | (x - y)$. That is, a pair is in the relation if the difference of the two values is even. For all$x \in A$,$x - x = 0, i.e. even. So this relation is even.

Relation Properties - Anti-Reflexive

• A relation on a set is anti-reflexive (irreflexive) if none of the elements is related to itself.
• Example The relation S$defined on$A = ${3, 4, 5, 6, 7, 8}$ by $(x, y) \in S$ when $|x - y| = 2$ is anti-reflexive, because the difference between an element and itself is never 2.
• Note: Some relations are neither reflexive nor anti-reflexive.

Relation Properties - Symmetric

• A relation has the property of being symmetric if when any element of the set is related to another, then the second element is also related to the first. That is, for all $x$ and $y \in A$, if $(x, y) \in R$ then $(y, x) \in R$.
• A symmetric relationship in our graphs looks like a flower petal or a self-loop.

Relation Properties - Anti-Symmetric

• A relation has the property of being anti-symmetric if when any element of the set is related to another element, then the second element is not related to the first. That is, for all $x$ and $y \in A$, if $(x, y) \in R$ and $x ≠ y$ then $(y, x) \notin R$.
• Example: The relation $S$ defined on $A =${3, 4, 5, 6, 7, 8}$by$(x, y) \in S$when$x - y = 2 is anti-symmetric.
• Note: Some relations are neither symmetric nor anti-symmetric.

Anti-Symmetric and Reflexive

• The definition of anti-symmetry does not prevent the relation to be reflexive, because of the condition x ≠ y.
• Examples:
  • The relation S$defined on$A = ${3, 4, 5, 6, 7, 8}$ by $(x, y) \in S$ when $x \le y$ is anti-symmetric.
  • The relation $S$ defined on $A =${3, 4, 5, 6, 7, 8}$by$(x, y) \in S$when$x - y \le 1 is anti-symmetric.

Relation Properties - Transitive

• A relation has the property of being transitive if when any one element of the set is related to another, and that second element is related to a third, then the first element is also related to the third. That is, for all x$,$y$and$z \in A$, if$(x, y) \in R$and$(y, z) \in R$then$(x, z) \in R.

Determining the Properties of a Relation

• The relation ≤$on the set of$R
  • \forall x \in R, x \le x, hence reflexive.
  • \forall x, y \in R$if$x ≠ y$and$x \le y$then$y \nleq x, hence anti-symmetric.
  • \forall x, y, z \in R$if$x \le y$and$y \le z$then$x \le z, hence transitive.
• The relation same parity on the set Z; i.e. xPy iff parity(x) = parity(y)
  • \forall x \in Z, parity(x) = parity(x), hence reflexive.
  • \forall x, y \in Z, if parity(x) = parity(y), then parity(y) = parity(x), hence symmetric.
  • \forall x, y, z \in Z, if parity(x) = parity(y) and parity(y) = parity(z), then parity(x) = parity(z), hence transitive.
• The relation predecessor on the set Z; i.e. xPy iff x = y − 1)
  • \forall x \in R, x ≠ x - 1 hence anti-reflexive.
  • \forall x, y \in R$, if$x = y - 1$, then$y ≠ x - 1 hence anti-symmetric.
  • \forall x, y, z \in R$, if$x = y - 1$and$y = z - 1$, then$x ≠ z - 1, hence not transitive.

Directed Graphs

Formal Definition of a Graph

• A directed graph G consists of two finite sets: a nonempty set V(G) of vertices (plural of vertex ) and a set E(G) of directed edges E(G) ⊆ V(G) \times V(G)
• Example: V (G) =${a, b, c, d, e}$, $E(G) =${ (a, b), (a, d), (b, c), (c, e), (d, d), (e, c) }
• Each vertex is represented a dot with a label.
• Each edge is represented by an arrow from a tail vertex to a head vertex.
• If the head and the tail of an edge are the same vertex, the edge is called a self-loop
• The in-degree of a vertex is the number of edges pointing into it. The out-degree of a vertex is the number of edges pointing out of it.

Walk in a Directed Graph

• A walk from v0$to$vl$in a directed graph$G is a sequence of alternating vertices and edges that starts and ends with a vertex.
  • < v0, (v0, v1), v1, (v1, v2), v2 . . . vl-1, (vl-1, vl), vl >
• Each edge in the sequence appears after its tail and before its head.
• Since the edges in a walk are completely determined by the vertices, a walk can also be denoted by the sequence of vertices:
  • < v0, v1, v2 . . . vl-1, vl >
• The sequence of vertices is a walk only if (vi-1, vi) \in E$for each$i = 1, 2, . . . l.
• The length of a walk is l, the number of edges in the walk.
• An open walk is a walk in which the first and last vertices are not the same. A closed walk is a walk in which the first and last vertices are the same.
• < a, b, c, e > is an open walk of length 3
• < c, e, c > is a closed walk of length 2
• < a, b, d > is not a walk
• < d, d, a, b, c, e, c, e > is a walk of length 8

Trails, circuits, paths, and cycles

• A trail is a walk in which no edge occurs more than once.
• A path is a walk in which no vertex occurs more than once.
• A circuit is a closed trail.
• A cycle is a circuit of length at least 1 in which no vertex occurs more than once, except the first and last vertices which are the same.
• < a, b, c, b, d > is a trail
• < a, b, c, e > is path
• < d, a, b, c, b, d > is a circuit
• < d, a, b, d > is a cycle
• Notes:
  • A trail of length 1 is an edge
  • a cycle of length 1 is a self-loop

Composition of Relations

• The composition of relations R and S on set A is another relation on A, denoted S \circ R$. The pair$(a, b) \in S \circ R$if and only if there is a$b \in A$such that$(a, b) \in R$and$(b, c) \in S.

Composition of a relation with itself

• A relation on a set can be composed with itself.
• For example, consider a relation P on a set of people that expresses parent-child relationships.
  • x P y means x is a parent of y.
• Consider the relation P \circ P = P^2$;$x P \circ P z means there is y such that x is the parent of y and y is the parent of z; i.e. x is the grand-parent of z
• This can be extended to P \circ P \circ P = P^3, i.e. great-grand-parent, and so on.
• In the corresponding graph, x P \circ P z means there is a sequence of the edges between x and z.
• This can be considered the second power of the graph G^2

Graph Powers

• Note G^4 = G^2$, hence$G^5 = G^3$,$G^6 = G^4 = G^2 and so on.
• Define G^+ = G^1 \cup G^2 \cup G^3 \cup . . .
• Although G^+$is defined as an infinite union, if$|V | = n$is finite, we only need to calculate up to$G^n
• If G represents the arrow diagram of a relation R on a set A, then G^+$is the arrow diagram of the relation$R^+ called the transitive closure of the relation R

Graph Power Theorem

• Let G be a directed graph. Let u and v be any two vertices in G.
• Theorem There is an edge from u to v in G^k if and only if there is a walk of length k from u to v in G.
• Proof by induction:
  1. Prove that the theorem holds for the base case, i.e. G^1$$
  2. Prove that if the theorem holds for the case k, it must also hold for the case k + 1