Composite Relations
Let R be a relation from a set A to a set B and S a relation from B to a set C.
The composite of R and S is the relation consisting of ordered pairs (a, c), where a ∈ A, c ∈ C, and for which there exists an element b ∈ B such that (a, b) ∈ R and (b, c) ∈ S.
We denote the composite of R and S by S ◦ R.
Computing the composite of two relations requires that we find elements that are the second element of ordered pairs in the first relation and the first element of ordered pairs in the second relation.
Q. What is the composite of the relations R and S, where R is the relation from {1, 2, 3} to {1, 2, 3, 4} with R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} and S is the relation from {1, 2, 3, 4} to {0, 1, 2} with S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}?
S ◦ R is constructed using all ordered pairs in R and ordered pairs in S, where the second element of the ordered pair in R agrees with the first element of the ordered pair in S.
For example, the ordered pairs (2, 3) in R and (3, 1) in S produce the ordered pair (2, 1) in S ◦ R.
Computing all the ordered pairs in the composite, we find
S ◦ R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)}.
n-ary Relations and Their Applications
Let A 1 , A 2 ,..., A n be sets. An n-ary relation on these sets is a subset of A . The sets A 1 , A 2 ,..., A n Are called the domains of the relation, and n is called its degree.
Let R be the relation on N × N × N consisting of triples (a,b,c), where a, b, and c are integers with a
Then (1, 2, 3) ∈ R, but (2, 4, 3) ∉ R. The degree of this relation is 3. Its domains are all equal to the set of natural numbers.
Equivalence Relations
A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.
Two elements a and b that are related by an equivalence relation are called equivalent. The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a particular equivalence relation.
Q. Let R be the relation on the set of real numbers such that aRb if and only if a − b is an integer. Is R an equivalence relation?
Because a − a = 0 is an integer for all real numbers a, aRa for all real numbers a.
Hence, R is reflexive. Now suppose that aRb. Then a − b is an integer, so b − a is also an integer. Hence, bRa. It follows that R is symmetric.
If aRb and bRc, then a − b and b − c are integers. Therefore, a − c = (a − b) + (b − c) is also an integer.
Hence, aRc. Thus, R is transitive. Consequently, R is an equivalence relation.
Q. Suppose that R is the relation on the set of strings of English letters such that aRb if and only if l(a) = l(b), where l(x) is the length of the string x. Is R an equivalence relation?
Because l(a) = l(a), it follows that aRa whenever a is a string, so that R is reflexive.
Suppose that aRb, so that l(a) = l(b). Then bRa, because l(b) = l(a). Hence, R is symmetric.
Finally, suppose that aRb and bRc. Then l(a) = l(b) and l(b) = l(c). Hence, l(a) = l(c),so aRc.
Equivalence Classes
Let A be the set of all students in your school who graduated from high school. Consider the relation R on A that consists of all pairs (x, y), where x and y graduated from the same high school.
Given a student x, we can form the set of all students equivalent to x with respect to R.
This set consists of all students who graduated from the same high school as x did. This subset of A is called an equivalence class of the relation.
Q. Let R be the relation on the set of real numbers such that aRb if and only if a − b is an integer. What is the equivalence class of an integer for the equivalence relation ?
Because an integer is equivalent to itself and its negative in this equivalence relation, it follows that [a] = {−a, a}.
This set contains two distinct integers unless a = 0.
For instance, [7] = {−7, 7}, [−5] = {−5, 5}, and [0] = {0}.
Graphs
A graph G = (V , E) consists of V , a nonempty set of vertices (or nodes) and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.
The set of vertices V of a graph G may be infinite. A graph with an infinite vertex set or an infinite number of edges is called an infinite graph, and in comparison, a graph with a finite vertex set and a finite edge set is called a finite graph.
A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices is called a simple graph
Graphs that may have multiple edges connecting the same vertices are called multigraphs.
A directed graph (or digraph) (V , E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of vertices.
Graph Terminology and Special Types of Graphs
Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v.
The set of all neighbors of a vertex v of G = (V , E), denoted by N(v), is called the neighborhood of v.
The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex.
A vertex of degree zero is called isolated.
A vertex is pendant if and only if it has degree one.
Let G = (V , E) be an undirected graph with m edges. Then 2m = ∑ v ∈ V deg(v). (Note that this applies even if multiple edges and loops are present.)
An undirected graph has an even number of vertices of odd degree.
When (u, v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v is said to be adjacent from u. The vertex u is called the initial vertex of (u, v), and v is called the terminal or end vertex of (u, v). The initial vertex and terminal vertex of a loop are the same.
In a graph with directed edges the in-degree of a vertex v, denoted by deg−(v), is the number of edges with v as their terminal vertex. The out-degree of v, denoted by deg+(v), is the number of edges with v as their initial vertex.
Let G = (V , E) be a graph with directed edges. Then ∑ v ∈ V deg− (v) = ∑ v ∈ V deg+ (v) = |E|
Complete Graphs
A complete graph on "n" vertices, denoted by "Kn" , is a simple graph that contains exactly one edge between each pair of distinct vertices.
A simple graph for which there is at least one pair of distinct vertex not connected by an edge is called noncomplete.
Cycles, Wheels and n - cubes (n-dimensional hypercube)
A cycle contains vertices v1, v2, ... , vN and edges {v1, v2}, ... , {vN-1, vN} for N ≥ 3
When we add an additional vertex to a cycle vertices (N) ≥ 3 and connect it to all the other vertices of the cycle, we get a Wheel.
An n-dimensional hypercube, or n-cube, denoted by Qn is a graph that has vertices representing the 2n bit strings of length "n". Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position.
Bipartite Graphs
A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 (so that no edge in G connects either two vertices in V1 or two vertices in V2).
A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color.
A graph is bipartite if and only if it is not possible to start at a vertex and return to this vertex by traversing an odd number of distinct edges.
Matching, Maximum matching and Complete matching
A matching M in a simple graph G = (V , E) is a subset of the set E of edges of the graph such that no two edges are incident with the same vertex.
A matching is a subset of edges such that if {s, t} and {u, v} are distinct edges of the matching, then s, t , u, and v are distinct.
A maximum matching is a matching with the largest number of edges.
We say that a matching M in a bipartite graph G = (V , E) with bipartition (V1, V2) is a complete matching from V1 to V2 if every vertex in V1 is the endpoint of an edge in the matching, or equivalently, if |M|=|V1|.
Example : Maximum matching and Complete matching
Suppose that there are "m" men and "n" women on an island.
A matching in this graph consists of a set of edges, where each pair of endpoints of an edge is a husband-wife pair.
A maximum matching is a largest possible set of married couples,
A complete matching of V1 is a set of married couples where every man is married, but possibly not all women.
Isomorphism of Graphs
The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there exists a one to one and onto function f from V1 to V2 with the property that a and b are adjacent in G1 if and only if f(a) and f(b) are adjacent in G2 , for all a and b in V1. Such a function f is called an isomorphism.
Two simple graphs that are not isomorphic are called nonisomorphic.
In other words, when two simple graphs are isomorphic, there is a one-to-one correspondence between vertices of the two graphs that preserves the adjacency relationship
Isomorphism of simple graphs is an equivalence relation.
Determining whether Two Simple Graphs are Isomorphic
Isomorphic simple graphs must have the same number of vertices, because there is a one-to-one correspondence between the sets of vertices of the graphs.
Isomorphic simple graphs also must have the same number of edges
In addition, the degrees of the vertices in isomorphic simple graphs must be the same.
The number of vertices, the number of edges, and the number of vertices of each degree need to be checked. If any of these quantities differ in two simple graphs, these graphs cannot be isomorphic.
However, when these invariants are the same, it does not necessarily mean that the two graphs are isomorphic.
Q. Check if the graphs in Figure 9 and 10 are isomorphic.
In Figure 9, Both G and H have five vertices and six edges. However, H has a vertex of degree one, namely, e, whereas G has no vertices of degree one. It follows that G and H are not isomorphic.
In Figure 10, The graphs G and H both have eight vertices and 10 edges. They also both have four vertices of degree two and four of degree three. Because these invariants all agree, it might be possible that these graphs are isomorphic.
However, G and H are not isomorphic. To see this, note that because deg(a) = 2 in G, a must correspond to either t , u, x, or y in H, because these are the vertices of degree two in H. However, each of these four vertices in H is adjacent to another vertex of degree two in H, which is not true for a in G.
Another way to see that G and H are not isomorphic is to note that the subgraphs of G and H made up of vertices of degree three and the edges connecting them must be isomorphic if these two graphs are isomorphic