Discrete Mathematics for Computer Science

Ordering Relations 199

INPUT: A finite set X = (X 1, X2 ..... Xn}I with an ordering relation R on X

OUTPUT:" An R-minimal element of X

for i = 2 to n do

if (xi R y holds) then

y =xi

print y

Example 12. Find a minimal element in the partial order shown:

3

5

1 2

4

Solution.

Data Values

x1 = 5

X2 = 3

X3 = 4

X4 = 1

x5 =-2

Tracing the Execution

y=X1 y=^5

for/ = 2

if x 2 R y means if 3 R 5

R does not hold for 3 and 5

for/ = 3

if x 3 R y means if 4 R 5

y=^4

for i = 4

if x 4 R y means if I R 4

R does not hold for 1 and 4

for i = 5

if x 5 R y means if 2 R 5

R does not hold for 2 and 5

Print final value: y = 4 I