6.4 Lesson: Binary relations: Sets

• After completing this lesson you should be able to find which elements of two given sets are related by a binary operation.
• Binary relations on a set
• A binary relation on a set A is a subset of A x A.
• The set A is called the domain of the binary relation.
• An element that is related to itself is indicated by an arrow called a self-loop
• The binary relation on a set is simply a relationship where the elements of the relationship come from the same original set. For example, the numbers a and b are elements of the set of negative integers, Z^–. Then the relation, W, on Z^– could be defined as aWb if a and b have a difference of 3. Note: The set Z^– would be referred to as the “domain” of the binary relation.
• Arrow diagrams for a binary relation on a set require only a single list (one copy) of each element of the domain.If there is a relation between two different elements, then an arrow is drawn from one to the other just as you have done in previous arrow diagrams.
• However, if an element maps to itself, a self-loop is drawn, which leaves and returns to the same element in a “loop.”
• Arrows may seem to “overlap” if the elements have a relationship in both directions. The second arrow will need to be slightly curved so the diagram is easy-to- read.

6.5 Lesson: Binary relations: Properties

• After completing this lesson you should be able to solve a mathematical problem using properties of the binary relation when given two sets and a binary relation.
• Properties of relations

• R is a relation on a set A.

• The relation R is reflexive if for every x ∈ A, xRx.
• The relation R is anti-reflexive if for every x ∈ A, it is not true that xRx.
• The relation R is transitive if for every x,y, z ∈ A, xRy and yRz imply that xRz.
• The relation R is symmetric if for every x,y ∈ A, xRy implies that yRx.
• The relation R is anti-symmetric if for every x,y ∈ A, xRy and yRx imply that x = y.

• Alternatively, R is anti-symmetric if for every x,y ∈ A, x ≠ y implies that it is not true that xRy or that it is not true that yRx.

6.6 Lesson: Binary relations: Directed graphs

• Now that you know the properties of relations, this lesson will introduce you to a part of discrete mathematics that is sometimes referred to as Graph Theory. 
• Directed graphs
• A directed graph (or digraph, for short) consists of a pair (V, E). 
• V is a set of vertices, and E, a set of directed edges, is a subset of V × V. An individual element of V is called a vertex. 
• The vertex u is the tail of the edge (u, v) and vertex v is the head.
• 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.
• Walks in directed graphs

• Trails, circuits, paths, and cycles
• A trail is an open walk in which no edge occurs more than once.
• A circuit is a closed walk in which no edge occurs more than once.
• A path is a trail in which no vertex occurs more than once.
• 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 directed graph or digraph consists of two sets: V (vertices) and E (edges).
• Vertices, set V, are visually represented by a labeled dot or circle. The elements, u and v ∈ V, are the head and tail (respectively) of the “edge.”
• Set E, the edges, are a subset of V x V. Visually, the “edges,” are the arrows diagramed from one vertex, v (the tail), to another vertex, u (the head). Edges can also be self-loops if the head and tail consist of the same vertex.
• Vertices are also described by the number of edges pointing into it (indegree) and number of edges pointing out of it (outdegree).
• Walks within a directed graph are made up of a number of sequential edges whose head is the tail of the previous edge. In other words, on an arrow diagram, if two elements are not directly related, then it may be possible to “walk” from one element (vertex) to the other (vertex) by passing through other vertices.
• Review the following terms related to directed graphs:

6.7 Module 18: Graph Powers

• Composition of relations
• Graph powers and the transitive closures
• Directed graphs and adjacency matrix
• Graph powers and matrix multiplication

6.8 Lesson: Composition of relations

• After completing this lesson you should be able to interpret the composition of relations when given a set and two relations.
• Composition of relations
• The composition of relations R and S on set A is another relation on A, denoted S∘R. The pair (a,c)∈S∘R if and only if there is a b∈A such that (a,b)∈R and (b,c)∈S.
• Composition of relations and directed graphs

• A relation is a link between two sets and is a collection of ordered pairs that contains one object from each of the given set. The arrow diagram for a binary relation is a directed graph.
• The composition of binary relations is a concept of forming a new relation from two given relations.
• The composition of two relations, B and W, on set Y is denoted W∘B.
• The ordering of a composition is to apply the output of the second function as the input to the first function. For example, for (W∘B)(4) apply B(4) first.
• The composition of two relations, B and W on set Y, is itself a relation. It is defined by the following: the pair (a,b)∈W∘B if and only if there is another value, k∈Y such that (a,k)∈B and (k,b)∈W. This means that you have a relation W∘B from a to b if and only if you can reach from a to b in two steps.

6.9 Lesson: Graph powers and the transitive closure

• The terminology for powers of graphs is similar to that for exponentiation of numbers: G² is called the square of G; G³ is called the cube of G.
• In this lesson you will also learn about the union of graphs known as transitive closure. 
• At the end of this lesson you should be able to solve for the transitive closure of a graph.
• Graph powers
• The graph G^k is defined to be the directed graph whose edge set is E^k and is called the k^th power of G. 
• Let G be a directed graph. Let u and v be any two vertices in G. 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.
• The transitive closure
• The relation R⁺ is called the transitive closure of R and is the smallest relation that is both transitive and includes all the pairs from R.
• If G is a directed graph, then G⁺ is called the transitive closure of G.

• To find the transitive closure of relation R, start with the pairs in R and add pairs until you cannot add any more pairs.
• According to the graph power theorem, given a directed graph, G and any two vertices in G (u and v) then 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.
• In a directed graph, the number of lengths of walks from one vertex to another is the graph power.
• Powers of relations is the number of times (length of walks) a relation is composed with itself. For example, if it takes 2 walks to get from a to c, by a to b and b to c, then it is graph power 2. When a relation is composed with itself, then the resulting relation must contain pairs from the original G with a walk length of 2 in order to be valid. If the same relation is composed yet again – a third time – the resulting relation would contain only pairs whose walks in G are length 3. This pattern continues. The number of times (length of walks) a relation is composed with itself is known as the power of the relation.
• If you create the union of all G^k , then the resulting relation from the union is the smallest relation that is transitive and contains all the pairs from G. This is referred to as the transitive closure of G and is denoted as G⁺ .

6.10 Lesson: Directed graphs and adjacency matrices

• After completing this lesson you should be able to determine the adjacency matrix corresponding to a directed graph.
• Adjacency matrices
• An n × m matrix over a set S is an array of elements from S with n rows and m columns. 
• Each element in a matrix is called an entry.
• A matrix is called a square matrix if the number of rows is equal to the number of columns.
• A directed graph G with n vertices can be represented by an n × n matrix over the set {0, 1} called the adjacency matrix for G. 
•  A Boolean matrix is a matrix whose entries are from the set {0, 1}. 
• If A and B are n × n matrices, the dot product of row i of A and column j of B is the sum of the product of each entry in row i from A with the corresponding entry in column j from B:
• A matrix is an array of numbers in rows and columns. A matrix’s size, e.g. matrix M, is denoted by m × n and is read, “M is an m by n matrix.” The m and n represent the number of rows and columns respectively. A square matrix has an equal number of rows and columns.
• It is very important to remember the order of values in the notation:The number of rows is always first, with the number of columns second: rows × columns = r × c.
• A mnemonic device (memory aid) is very helpful here. For example, you could think of “RC cola” or “RC” to help you remember “rows by columns.”
• Each element within the matrix is referred to as an “entry” and is denoted by M_i,j where once again, it is rows (i) and columns (j).
• An adjacency matrix of a directed graph, G, with n vertices is the n × n matrix whose elements come from the set {0, 1}. The rows and columns of the matrix correspond to the vertices in the directed graph. If an edge exists from vertex i to vertex j, then a 1 is placed in the matrix at the corresponding position M_i,j. If no edge exists, a zero is placed.

6.11 Lesson: Graph powers and matrix multiplication

• After completing this lesson you should be able to determine a graph power using the adjacency matrix and matrix multiplication.
• Boolean matrix multiplication
• If A and B are n × n matrices over the integers, then the matrix product of A and B, denoted AB or A·B, is another n × n matrix such that (AB)_i,j is the result of taking the dot product of row i of matrix A and column j of matrix B.
• However, matrix multiplication is not commutative because there are matrices A and B for which AB ≠ BA. The k^th power of a matrix A is the product of k copies of A:
• Relationship between graph powers and matrix powers
• Let G be a directed graph with n vertices and let A be the adjacency matrix for G. Then for any k ≥ 1, A^k is the adjacency matrix of G^k, where Boolean addition and multiplication are used to compute A^k.
• If A and B are two m × n matrices, then the matrix sum of A and B, denoted A + B, is also an m × n matrix such that (A + B)_i,j = A_i,j + B_i,j for all 1 ≤ i ≤ m and 1 ≤ j ≤ n.

• Addition and graph union

• Let G and H be two directed graphs with the same vertex set. Let A be the adjacency matrix for G and B the adjacency matrix for H. Then the adjacency matrix for G ∪ H is A + B, where Boolean addition used on the entries of matrices A and B.
• A Boolean matrix contains only elements from the set {0, 1}. Addition and multiplication of Boolean matrices is performed using Boolean addition and multiplication for each element.
• Matrix Addition and Directed Graphs:Matrix addition is the addition of each element whose relative positions within each matrix is the same. For example, to create A + B, where A and B are 5 x 5 matrices, you would add each corresponding element. A_3,4 + B_3,4 would be put in position (A + B)_3,4 etc.
• If two directed graphs have the same set of vertices, then the union of the two graphs can be accomplished using matrix addition.
• Matrix Multiplication and Directed Graphs:Each entry in the product matrix is computed using a dot product. For example, to create the entry M_{3, 4} from A × B, given A, B, and M are 5 × 5 matrices, you would multiply all the entries in row 3 of A times all the entries in column 4 of B. There would be 5 pairs of numbers to multiply, then add together.
• Matrix multiplication is not commutative. That is, the order of the multiplication completely changes the answer. For example, in regular arithmetic, 2 times 3 is 6 and so is 3 times 2. But in matrix arithmetic, A × B is usually not equal to B × A.
• Matrix multiplication is associative. This means (A × B) × C = A × (B × C)
• A matrix multiplied by itself k times is referred to as the k^th power of a matrix A.
• Use these steps to perform matrix multiplication to compute G^k from a directed graph, G:Create the adjacency matrix A for directed graph G.
• Compute A^k by repeated matrix multiplication.
• The final A^k matrix is the adjacency matrix for G^k .

6.12 Module 19: Order Relations

• Partial order relations
• Partial order and Hasse diagrams
• Strict order relations
• Strict orders and directed acyclic graphs

6.13 Lesson: Partial order relations

• A partially ordered relation of the set (or poset) must have three of the properties of relations: reflexive, transitive, and anti-symmetric. 
• After completing this lesson you should be able to determine a digraph of the partial order relation when given a finite set and a partial order relation of the set.
• Partial orders
• A relation R on a set A is a partial order if it is reflexive, transitive, and anti-symmetric.
• The domain along with a partial order defined on it is denoted (A, ⪯) and is called a partially ordered set or poset.
• Two elements of a partially ordered set, x and y, are said to be comparable if x ⪯ y or y ⪯ x. 
• Otherwise they are said to be incomparable. A partial order is a total order if every two elements in the domain are comparable. 
• An element x is a minimal element if there is no y ≠ x such that y ⪯ x. 
• n element x is a maximal element if there is no y ≠ x such that x ⪯ y.
• A relation, R, on a set A is a partial order relation if it is transitive, reflexive, and anti-symmetric. Specifically, aRb is notated by a ⪯ b and is read “a is at most b.”
• The domain of a partially ordered set (poset) is denoted by (A, ⪯).
• Comparable elements of a poset are two elements, x and y, such that x ⪯ y or y ⪯ x. Otherwise, x and y are incomparable.
• A total order is a partial order relation where every two elements in the domain are comparable.
• A maximal element is a vertex where on a directed graph, the only arrows out of them are to themselves or none.
• A minimal element is a vertex where on a directed graph, the only arrows into them are from themselves or none.

6.14 Lesson: Partial order and Hasse diagrams

• After completing this lesson you should be able to solve for a Hasse diagram of the partial order relation when given a finite set and a partial order relation on the set.
• A Hasse diagram, named after the 20th century German mathematician Helmut Hasse, is a useful way to depict a partial order on a finite set.
• In a Hasse diagram, each element is shown by a labeled point. However, unlike digraphs, Hasse diagrams have very few edges – only lines depicting relative precedence of the elements.
• To create a Hasse diagram, use the following rules:If x ⪯ y, then make the x element appear lower in the diagram than y.
• If x ⪯ y and there is no z where x ⪯ z or z ⪯ y, then draw a segment connecting x and y.
• In Hasse diagrams, self-loops are removed and the transitive and reflexive properties are assumed.

6.15 Lesson: Strict order relations

• After completing this lesson you should be able to determine a digraph of the strict order relation when given a finite set and a strict order relation on the set.
• Strict orders
• A relation R is a strict order if R is transitive and anti-reflexive.
• Two elements, x and y, are said to be comparable if x ≺ y or y ≺ x.
• Otherwise, the elements are said to be incomparable.
• A strict order is a total order if every pair of elements is comparable. 
• An element x is a minimal element if there is no y such that y ≺ x. 
• An element x is a maximal element if there is no y such that x ≺ y.
• Relations with strict order have the transitive and anti-symmetry properties, but they are not reflexive.
• The symbol used to show a strict order relation is ≺. The domain is denoted by (A, ≺).
• The definitions for strict order are very similar to partial order relations. The main difference is the reflexive (or equality) being removed for strict order.

6.16 Lesson: Strict order relations and directed acyclic graphs

• There are special types of directed graphs without cycles, aptly named directed acyclic graphs (DAG). 
• After completing this lesson you should be able to analyze the properties of a digraph of an ordering relation including cyclic, acyclic, length cycle, and ordering.
• Directed acyclic graphs
• A directed acyclic graph (or DAG for short) is a directed graph that has no positive length cycles.
• Topological sorts of DAGs
• A topological sort for a DAG is an ordering of the vertices that is consistent with the edges in the graph.
• Directed acyclic graphs (DAG) are directed graphs with no positive length cycles.
• A DAG can be used to represent a strict order.
• DAGs are useful for representing precedence relationships.

6.17 Module 20: N‐ary Relations

• N-ary equivalence relations
• N-ary relations and relational databases

6.18 Lesson: N-ary equivalence relations

• n this lesson you’ll learn another type of relationship: equivalence relations. An equivalence relation has the properties similar to previous relations; however, in addition to being reflexive and transitive, it is also symmetric. 
• After completing this lesson you should be able to determine a partition defined by the equivalence class when given an equivalence relation via a graph.
• Equivalence relations
• A relation R is an equivalence relation if R is reflexive, symmetric, and transitive. If a relation R is an equivalence relation, the notation a~b is used to express aRb. a~b is read “a is equivalent to b”.
• If A is the domain of an equivalence relation and a ∈ A, then [a] is defined to be the set of all x ∈ A such that a~x. The set [a] is called an equivalence class. 
• The theorem can be used to show that an equivalence relation defines a partition of the domain. A partition of a set A is a set of non-empty subsets of A that are pairwise disjoint and whose union is A.
• A set of sets is pairwise disjoint if the intersection of any pair of the sets is empty.
• An equivalence relation has all three of the following properties: symmetry, reflexive, and transitive. An equivalence relation, R, is denoted as a ~ b for aRb.
• An equivalence relation is easy to spot when shown as a directed graph: each vertex has a self- loop.
• An equivalence class is denoted by [a] and is defined to be the set of all x ∈ A such that a ~ x, given A is the domain of an equivalence relation and a is also an element of A. The example of the set of natural numbers, which all have the same remainder when divided by 3, would have classes of [0], [1], and [2].
• According to the structure of equivalence relations theorem, two equivalence classes are either identical or completely different (disjoint).
• The set of all distinct equivalence classes of set A is called a partition of the set A. The “distinct” qualification just means a class is only included once if there are two equal equivalence classes.
• Pairwise disjoint sets have no intersection of any of the sets.

6.19 Lesson: N-ary relations and relational databases

• After completing this lesson you should be able to solve for all equivalent items within a set of N‐ary relations.
• Relational databases

The definition of a binary relation (a relation between two sets) can be generalized to relations on more than two sets:

• A relation on sets A₁, A₂,…,A_n is a subset of A₁ x A₂ x … x A_n.
  Each element of the relation is an n-tuple in which the i^th entry in the n-tuple is from A_i.
• A database is a large collection of data records that is searched and manipulated by a computer. 
• The relational database mode stores data records as relations. 
• The type of data stored in each entry of the n-tuple is called an attribute.
• A query to a database is a request for a particular set of data. 
• A key is an attribute or set of attributes that uniquely identifies each n-tuple in the database.
• The selection operation
• The selection operation chooses n-tuples from a relational database that satisfy particular conditions on their attributes. 
• The projection operation
• The projection operation takes a subset of the attributes and deletes all the other attributes in each of the n-tuples.
• A relation on multiple sets, say A₁ , A₂ , A₃ , …, A_n is a subset of A₁ x A₂ x A₃ x … x A_n . Each element of the relation is an n-tuple in which a particular element, say the j^th entry in the n-tuple is A_j .
• A relational database stores a large collection of records as relations.
• An attribute describes the type of data found in each entry of an n-tuple.
• A query to a relational database is just a request for a particular piece or pieces of data.
• A key is an attribute (or set of attributes) which provides a unique identity for each n-tuple in the database.
• One common type of query on a database is called the selection operation and is denoted by Select[ … ]. For example, Select [Complete = No ∧ Date < 6/21/2013] from Participation Activity 6.19.2 in your text selects only the n-tuples with “no” under the “complete” attribute AND whose date is before 6/21/2013.
• The projection operation is denoted by Project [list of attributes]. This operation yields a list which is a subset of the attributes in an n-tuple (deleting all other attributes before the output is displayed). Also, the final step of the operation is to merge any duplicate instances of the subset output.

7.1 Unit 7: Graphs and Trees

• Undirected graphs
• Graph isomorphism
• Paths, cycles, and connectivity
• Trees and their properties
• Tree traversals and spanning trees

7.2 Module 21: Undirected Finite Graphs and Diagrams

• Introduction to undirected graphs
• Graph theory and common graphs
• Undirected graph representations
• Graph isomorphism

7.3 Lesson: Introduction to undirected graphs

• After completing this lesson you should be able to determine the edges and vertices of an undirected graph.
• Graphs in computer science
•  In an undirected graph, the edges are unordered pairs of vertices, which is useful for modeling relationships that are symmetric. 
•  graph is finite if the vertex set is finite. 
•  A single element of V is called a vertex and is usually represented pictorially by a dot with a label.
• Graph terminology
• If there is an edge between two vertices, they are said to be adjacent. In the graph above, d and e are adjacent, but d and b are not adjacent.
• Vertices b and e are the endpoints of edge {b, e}. The edge {b, e} is incident to vertices b and e.
• A vertex c is a neighbor of vertex b if {b, c} is an edge. In the graph above, the neighbors of b are the vertices a, c, and e.
• In a simple graph, the degree of a vertex is the number of neighbors it has. In the graph above, the degree of b is 3 and the degree of vertex a is 2. The degree of vertex b is denoted by deg(b).
• The total degree of a graph is the sum of the degrees of all of the vertices. The total degree of the graph above is 2 + 3 + 3 + 2 + 2 = 12.
• In a regular graph, all the vertices have the same degree. In a d-regular graph, all the vertices have degree d. The graph above is not regular because deg(a) ≠ deg(b). However the graph below is 3-regular.
• A graph H = (V_H, E_H) is a subgraph of a graph G = (V_G, E_G) if V_H ⊆ V_G and E_H ⊆ E_G. Note that any graph G is a subgraph of itself. The diagram below shows a subgraph H of the graph G:
• Parallel edges are multiple edges between the same pair of vertices.
• A graph can also have a self-loop which is an edge between a vertex and itself. 
• If a graph does not have parallel edges or self-loops, it is said to be a simple graph. 
• Similar to directed graphs, an undirected graph consists of edges and vertices. However, in an undirected graph the edges are unordered.
• An undirected graph can be described in terms of its vertices and edges and is denoted (V, E), where V is the set of all vertices in the graph and E is the set of all edges.
• Undirected graphs are useful in modeling symmetric relationships. For example, people on a social media site can be modeled with vertices. An edge will connect two vertices if the individuals are “friends” in the network. If A is a friend to B, B is also a friend to A.
• Undirected graphs can be either finite or infinite. Finite undirected graphs have a finite number of vertices.
• All vertices in an undirected graph do not need to be connected to each other; it can consist of a collection of connected pieces.
• Review the following descriptions and terms used to describe undirected graphs:Edge: described by its vertices and is denoted {a,b} to represent an edge whose endpoints are the vertices a and b
• Adjacent edge: two edges that share a common vertex
• Adjacent vertices: two vertices with an edge connecting them
• Incident: the edge and vertex of the adjacent edge; e.g., the edge {a,b} is incident to vertices a and b.
• Parallel edges: edges that connect to the same pair of vertices
• Self-loop: an edge that begins and ends at the same vertex
• Simple graph: undirected graphs that have neither parallel edges nor self-loops
• Degree of a vertex v: the number of edges whose endpoints include v
• Total degree of a graph: the sum of the degrees of each vertex in a graph
• Regular graph: all vertices have the same degree
• d-regular graph: d is the degree of each vertex
• Graphs and subgraphs: Every graph is a subgraph of itself. A subgraph S of a graph G is itself a graph whose set of vertices are a subset of the vertices of G and whose edges are a subset of the edges of G.