Übungsblatt3 - Aufgabe 3b

Re: Übungsblatt3 - Aufgabe 3b

sv70 — Wed, 27 Nov 2013 12:08:28 +0100

Thanks Philipp. That really helped.

SV

Re: Übungsblatt3 - Aufgabe 3b

pmallot — Fri, 22 Nov 2013 12:22:45 +0100

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

Re: Übungsblatt3 - Aufgabe 3b

sv70 — Fri, 22 Nov 2013 09:56:54 +0100

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

Re: Übungsblatt3 - Aufgabe 3b

pmallot — Fri, 22 Nov 2013 08:42:20 +0100

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

Übungsblatt3 - Aufgabe 3b

sv70 — Fri, 22 Nov 2013 00:28:14 +0100

Hi,

I am a little confused about the topsort(Q(e))
Thanks in advance
SV