Algorithms

Question

Focus on the word constraint , I am little confused (in meaning of the word)here. What should be  the answer  2 or 16.

We are interested in topological orderings of the following DAG that satisfy one or both of the following constraints:
1. 4 appears before 3
2. 8 appears after 7

How many such orderings are there?
16
Correct Option

Solution :
16
Topological sort is of the form 1 , followed by a topological ordering of $\{2,3,4,5\}$, followed by 6 , followed by a topological ordering $\{7,8,9\}$. Nodes $\{2,3,4,5\}$ have ( 4 choose 2 ) $=6$ topological orderings of which only one, 2-3-4-5 has 3 before 4 . All other orderings have 4 before 3: 2-4-3-5, 2-4-5-3, 4-2-3-5, 4-2-5-3, 4-5-2-3.
Nodes $\{7,8,9\}$ have 3 topological orderings, $7-8-9,8-7-9,8-9-7$, of which two have 8 before 7 and one has 8 after 7. There are $6 \times 3=18$ total topological orderings of which $1 \times 2=2$ violates both conditions, so 16 satisfy one condition or both.

Answer 1

There are total of 18 topological orderings possible.

Out of which only 2 does not satisfy both the constraints .

1$\rightarrow$ 2$\rightarrow$4$\rightarrow$5$\rightarrow$6$\rightarrow$8$\rightarrow$7$\rightarrow$9$\rightarrow$10

1->2->4->5->6->8->9->7->10

If the question is which follows both 1 and 2,then answer is $5$.

If the question is only about either 1 or 2 ,then also answer is $16$

Comments

@vishnu777

I am asking what is the meaning of  “one or both satisfy the following constraints”.

What I am thinking (the meaning)  is “ one or both rules to be followed”.

But in the solution contain the order which does not follow any of the above rule.

---

It means the ordering must satisfy atleast one condition i.e either 1 or both conditions must be true.

I hope you got clarified!!