Part 01-Discrete mathematics for gate-Partial Order Relations and it’s matrix representation

Part 01-Discrete mathematics for gate-Partial Order Relations and it’s matrix representation

https://www.gyanodhan.com/video/7B5.%20GATE%20CSEIT/Discrete%20Mathematics%202/523.%20Day%2003%20%20Part%2001-Discrete%20mathematics%20for%20gate-Partial%20Order%20Relations%20and%20it%27s%20matrix%20representation.mp4

Partial Order Relations and Its Matrix Representation (Discrete Mathematics for GATE)

1. Introduction to Partial Order Relations
A partial order relation (poset) is a binary relation $R$ on a set $S$ that satisfies the following properties:

• Reflexivity: $aRa$ for all $a\in S$

• Antisymmetry: If $aRb$ and $bRa$, then $a=b$

• Transitivity: If $aRb$ and $bRc$, then $aRc$

A set $S$ along with a partial order relation $R$ is called a partially ordered set (poset).

2. Matrix Representation of Partial Order Relations
The relation matrix of a partial order relation on a finite set is a square matrix MRM_RMR​ of size $n\times n$, where:

• Mij=1M_{ij} = 1Mij​=1 if aiRaja_i R a_jai​Raj​

• Mij=0M_{ij} = 0Mij​=0 otherwise

Example:
Let $S=\{1,2,3\}$ with a relation $R=\{(1,1),(2,2),(3,3),(1,2),(2,3)\}$.

The relation matrix MRM_RMR​ is:

MR=[110011001]M_R = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}MR​=​100​110​011​​

• The diagonal elements are 1, ensuring reflexivity.

• The matrix is not symmetric, proving antisymmetry.

• The transitive closure can be found using the Warshall’s Algorithm.

3. Hasse Diagram Representation
A Hasse diagram is a graphical representation of a poset where:

• Reflexive edges are omitted.

• Transitive edges are removed for simplicity.

• Elements are arranged hierarchically.

For the above example, the Hasse Diagram is:

4. Applications of Partial Order Relations

• Scheduling Problems

• Hierarchical Structures

• Dependency Graphs in Computer Science

• Data Organization in Databases

Would you like a detailed explanation or GATE-level problems on this topic?

Part 01-Discrete mathematics for gate-Partial Order Relations and it’s matrix representation

DIGITAL NOTES ON Discrete Mathematics B.TECH II YEAR

Discrete Mathematical Structures Unit-1