Backgrounds: 1. Given a binary relation R on a certain finite set S, we can cons
ID: 3878725 • Letter: B
Question
Backgrounds:
1. Given a binary relation R on a certain finite set S,
we can consider an equivalence relation on the set S
that contains the relation R.
2. Of all equivalence relations to be obtained from this
relation R, we can think of the minimum equivalence relation.
It must be the one that is contained in any and every such
equivalence relation.
Example:
1 0 0
0 1 0
0 0 0
For the above relation on a set of three elements,
each of the following is an equivalence relation that contains
the given binary relation:
1 0 0 1 1 1 1 1 0
0 1 0 1 1 1 1 1 0
0 0 1 1 1 1 0 0 1
The first one above is the minimum equivalence relation containing
the given binary relation.
3. How to get it?
Perform the following operations in succession:
a. Symmetric closure on the given binary relation R to result in
s(R)
b. Transitive closure operation on the resulting relation, s(R),
to result in ts(R).
c. Finally, Reflexive closure on ts(R), to get rts(R) which is
the wanted minimum equivalence relation.
You can perform above three operations in a different sequence.
But, not every different sequence will result in what is wanted as the Symmetric
Closure must be performed always before the Transitive Closure.
Task:
Write a well-documented program that does:
1. Repeat
a. Input the size of an adjacency matrix (<=20)
b. Input a matrix exactly of that size.
c. Compute the minimum equivalence relation
and hence its adjacency matrix.
d. And, print out both the input matrix and
the resulting (Min. Eq. Relation) matrix.
until all inputs are done.
2. Print out the number of input cases that have been
processed.
NOTE: In computing the Transitive Closure of a (binary) relation
use the Warshall's algorithm.
The Warshall's algorithm:
public void Closure (int Size, int[][] Rel)
{
int From, To, Via;
for (Via=0; Via < Size; Via++)
for (From=0; From < Size; From++)
for (To=0; To < Size; To++)
if ((Rel[From][Via]==1) && (Rel[Via][To]==1))
// Above has some redundant parentheses just in case
Rel[From][To] = 1;
//End of Via loop, and hence end of other two loops.
} //End of java method Closure.
Inputs: Use the following four input cases.
1 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 1 0 1 0
0 0 0 0 1 1 0 0
1 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0
1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Explanation / Answer
package com.example.java; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("Enter no. of input cases: "); int numInputCases = sc.nextInt(); for(int t=0;tRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.