A relation is a subset of the cartesian product of a set with another set. A relation contains ordered pairs of elements of the set it is defined on. To learn more about relations refer to the article on “Relation and their types“.
What is a Symmetric Relation?
A relation R on a set A is called symmetric relation if and only if
∀ a, b ∈ A, if (a, b) ∈ R then (b, a) ∈ R and vice versa i.e.,
∀ a, b ∈ A, (a, b) ∈ R(b, a) ∈ R,
where R is a subset of (A x A), i.e. the cartesian product of set A with itself.
(b, a) ∈ R, This means if an ordered pair of elements “a” to “b” (aRb) is present in relation R, then an ordered pair of elements “b” to “a” (bRa) should also be present in relation R. If any such bRa is not present for any aRb in R then R is not a symmetric relation.
Example:
Consider set A = {a, b}
then R = {(a, b), (b, a)} is symmetric relation but
R = { (a, b), (a, a) } is not a symmetric relation as for (a, b) tuple, (b, a) tuple is not present.
Properties of Symmetric Relation
- Empty relation on any set is always symmetric.
- Universal relations are always symmetric.
- If the relation is reflexive/irreflexive then it need not be symmetric.
How to verify Symmetric Relation?
To verify a symmetric relation do the following:
- Manually check for the existence of every bRa tuple for every aRb tuple in the relation.
- If any of the tuples does not exist then the relation is not symmetric else it is symmetric.
Follow the below illustration for a better understanding
Illustration:
Consider set A = { 1, 2, 3, 4 } and a relation R = { (1, 2), (1, 3), (2, 1), (3, 4), (3, 1) }
For the pair (1, 2) in R:
=> The reversed pair (2, 1) is present in the relation.
=> This pair satisfies the conditionFor the pair (1, 3) in R:
=> The reversed pair (3, 1) is present in the relation.
=> This pair satisfies the conditionFor the pair (2, 1) in R:
=> The reversed pair (1, 2) is present in the relation.
=> This pair satisfies the conditionFor the pair (3, 4) in R:
=> The reversed pair (4, 3) is not present in the relation.
=> This pair does not satisfy the conditionFor the pair (3, 1) in R:
=> The reversed pair (1, 3) is present in the relation.
=> This pair satisfies the conditionAs the pair (3, 4) does not satisfy the condition, the relation is not symmetric.
Below is the code implementation of the idea:
C++
#include <bits/stdc++.h>using namespace std;class Relation {public: bool checkSymmetric(set<pair<int, int> > R) { // Property 1 if (R.size() == 0) { return true; } for (auto i = R.begin(); i != R.end(); i++) { // Making a mirror tuple auto temp = make_pair(i->second, i->first); if (R.find(temp) == R.end()) { // If bRa tuple does not exists in relation // R return false; } } // bRa tuples exists for all aRb in relation R return true; }};// Driver codeint main(){ // Creating relation R set<pair<int, int> > R; // Inserting tuples in relation R R.insert(make_pair(1, 1)); R.insert(make_pair(1, 2)); R.insert(make_pair(2, 1)); R.insert(make_pair(2, 3)); R.insert(make_pair(3, 2)); R.insert(make_pair(3, 4)); Relation obj; // R is not symmetric as (4, 3) tuple is not present if (obj.checkSymmetric(R)) { cout << "Symmetric Relation" << endl; } else { cout << "Not a Symmetric Relation" << endl; } return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class pair { int first, second; pair(int first, int second) { this.first = first; this.second = second; }}class GFG { static class Relation { boolean checkSymmetric(Set<pair> R) { // Property 1 if (R.size() == 0) { return true; } for (var i : R) { // Making a mirror pair // Eg : (1, 2) => mirror pair = (2, 1) pair temp = new pair(i.second, i.first); if (!R.contains(temp)) { // If bRa tuple does not exists in // relation R return false; } } // bRa tuples exists for all aRb in relation R return true; } } public static void main(String[] args) { // Creating relation R Set<pair> R = new HashSet<>(); // Inserting tuples in relation R R.add(new pair(1, 1)); R.add(new pair(1, 2)); R.add(new pair(2, 1)); R.add(new pair(2, 3)); R.add(new pair(3, 2)); R.add(new pair(3, 4)); Relation obj = new Relation(); // R is not symmetric as (4, 3) tuple is not present if (obj.checkSymmetric(R)) { System.out.println("Symmetric Relation"); } else { System.out.println("Not a Symmetric Relation"); } }}// This code is contributed by lokeshmvs21. |
Python3
class Relation: def checkSymmetric(self, R): # Property 1 if len(R) == 0: return True for i in R: if (i[1], i[0]) not in R: # If bRa tuple does not exists in relation R return False # bRa tuples exists for all aRb in relation R return True# Driver codeif __name__ == '__main__': # Creating relation R R = {(1, 1), (1, 2), (2, 1), (2, 3), (3, 2), (3, 4)} obj = Relation() # R is not symmetric as (4, 3) tuple is not present if obj.checkSymmetric(R): print("Symmetric Relation") else: print("Not a Symmetric Relation") |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class pair { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; }}public class GFG { class Relation { public bool checkSymmetric(HashSet<pair> R) { // Property 1 if (R.Count == 0) { return true; } foreach(var i in R) { // Making a mirror pair // Eg : (1, 2) => mirror pair = (2, 1) pair temp = new pair(i.second, i.first); if (!R.Contains(temp)) { // If bRa tuple does not exists in // relation R return false; } } // bRa tuples exists for all aRb in relation R return true; } } static public void Main() { // Code // Creating relation R HashSet<pair> R = new HashSet<pair>(); // Inserting tuples in relation R R.Add(new pair(1, 1)); R.Add(new pair(1, 2)); R.Add(new pair(2, 1)); R.Add(new pair(2, 3)); R.Add(new pair(3, 2)); R.Add(new pair(3, 4)); Relation obj = new Relation(); // R is not symmetric as (4, 3) tuple is not present if (obj.checkSymmetric(R)) { Console.WriteLine("Symmetric Relation"); } else { Console.WriteLine("Not a Symmetric Relation"); } }}// This code is contributed by lokesh |
Javascript
class Relation { constructor() {} checkSymmetric(R) { // Property 1 if (R.size === 0) { return true; } for (const i of R) { // Making a mirror tuple const temp = [i[1], i[0]]; if (!R.has(temp)) { // If bRa tuple does not exists in relation // R return false; } } // bRa tuples exists for all aRb in relation R return true; }}// Driver codefunction main() { // Creating relation R const R = new Set(); // Inserting tuples in relation R R.add([1, 1]); R.add([1, 2]); R.add([2, 1]); R.add([2, 3]); R.add([3, 2]); R.add([3, 4]); const obj = new Relation(); // R is not symmetric as (4, 3) tuple is not present if (obj.checkSymmetric(R)) { console.log("Symmetric Relation"); } else { console.log("Not a Symmetric Relation"); }}main();// This code is contributed by akashish__ |
Not a Symmetric Relation
Time Complexity: O(N * log N) where N is the number of tuples in the relation
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
