Scribd
Upload
57 views7 pages

Topological Sorting in Posets

The document discusses topological sorting of directed acyclic graphs (DAGs). It defines topological sorting as a linear ordering of the vertices in a DAG such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. It provides an example of a topological sorting of a graph and notes that topological sorting is not unique for a graph and that it is not possible for graphs that are not DAGs. It also outlines an algorithm for constructing a compatible total ordering from a partial ordering in a poset.

Uploaded by

Ankita Pradhan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
57 views7 pages

Topological Sorting in Posets

The document discusses topological sorting of directed acyclic graphs (DAGs). It defines topological sorting as a linear ordering of the vertices in a DAG such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. It provides an example of a topological sorting of a graph and notes that topological sorting is not unique for a graph and that it is not possible for graphs that are not DAGs. It also outlines an algorithm for constructing a compatible total ordering from a partial ordering in a poset.

Uploaded by

Ankita Pradhan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

DISCRETE 

MATHEMATICS

PROJECT :- 4

PRESENTED BY :-  V Sai Manasa


                                (210101120040)

GUIDED BY :- Dr. Ashok Misra


Topological Sort :- For a directed acyclic graph (DAG) is a linear
ordering of vertices such that for every directed edge (u , v) , vertex u comes
before v in the ordering.

For a DAG :-
Topological sort is not unique.
Topological Sorting for a graph is not possible if the graph is not a DAG.
For example, a topological sorting of the following graph is “5 4 2 3 1 0”.
There can be more than one topological sorting for a graph. For example,
another topological sorting of the following graph is “4 5 2 3 1 0”. The first
vertex in topological sorting is always a vertex with in-degree as 0 (a vertex
with no incoming edges).
Concept :-  Topological sorting means "linearization of a
partial orderings".
Topological sorting in a poset P = (A , ) is a linear ordering
of the members of the poset by constructing a compatible
total ordering relation on P such that a b t whenever ab .
t

Compatible total ordering :- Let (A , ) be a poset . A total ordering is said


to be compatible
t with the partial ordering if a b t
Whenever ab .
Constructing a total ordering from a partial ordering is called topological sorting.

 Every finite non empty (S , ) has at least one minimal element.


The topological sorting algorithm :- Let P= (A , ) be any non finite poset.
We define a total ordering on the poset (A , ) as follows :-
 Choose a minimal element .
 If (A } , ,then (A } , is also a poset.
 If (A } , , choose a minimal element A }
 If there are additional elements left, continue this process by choosing to be
a minimal element in A {, ,…….}, as long as elements remain.
Example :- Find all the compatible total ordering for the poset ({1 , 2 , 4 , 5 ,
12 , 20}). ab if a.

Solution :- The Hasse diagram of the partial order and the compatible total
ordering are :-

12. . 20 Compatible total ordering is :-

4 . 1. 1 2t 5 12 20
2. 1 5 2 4 20
2 . .5 3. 1 2 5 4 12
. 4. 1 5 2 4 12
1

Hasse Diagram
Conclusion :- Topological sort is used for partial defined orders. In recent
years , the algorithm was developed for parallel computation. In general use,
this algorithm is used in cases for which a graphic model is available for
people to understand bigger problems.

Applications :-
 Finding cycle in a graph.
 Sentence ordering.
 Course schedule problem.
 Other applications like manufacturing workflows, data visualization and
context-free grammar.

You might also like