Hi,

I am a little confused about the topsort(Q(e))<topsort(Z(e)) property mentioned in the aufgabe 3b. I understand the topological sorting algorithm i use should have the property mentioned above. But what exactly does this property mean?

Thanks in advance
SV

Hi,

if I remember the lecture correctly e is an edge in the graph, Q(e) is where e starts, and Z(e) is where it ends.
So basically, when you apply this order, you order the nodes from start to end of the circuit. The gates that get hit by the input first have low values, the gates just before the output have the highest value.
That's also why you can use this order for the next part of the exercise.

Hope that helps,
Philipp

Hi Philip,

Thank you for the response.

Yes...Q(e) is the node from which the Kante starts and V(e) is the node at which it ends. But, how do you know that the nodes at the begining of the circuit have low values and nodes just before the end have high values? What values are we talking about? Are we talking about talking about the binary value 0/1 that the gate holds? Or are we talking about the number assigned to the Gate (V5, V2 etc)?

Thanks
SV

Zitat

eine bijektive Abbildung topsort: V -> {1,2,...,|V|}

|V| being the number of elements in V.
That means we are looking for one and only one number in the range of 1 through |V| for every element in V. (Like assigning it a unique id.)

Now if you assign the last gate in the circuit the lowest number, then of course there will be one edge e going into it that comes from a node with a higher number. That would violate the given rule. So it might be a good idea to give the last node the highest number and proceed from there.

Philipp

Thanks Philipp. That really helped.

SV