שאלה

שאלה

Nir (guest) 03 Sep 2012 10:36

שלום.

1. צריך להראות דוגמא לרשת זרימה אציקלית שבה קיבלו כל קשת 1 ויש זרימה חוסמת שערכה 2 וזרימת מקסימום שערכה 10. איך אפשר לעשות את זה?

2.מה הסיבוכיות של קורסקל ללא מיון? אני רואה בכל מיני שאלות סימון של אלפה, ואני לא כ"כ מבין מה זה.

תודה רבה!

Re: שאלה

RaeNye 03 Sep 2012 11:08

1) We saw in class an example of a network with a blocking flow of value 1, while the maximal possible flow was 2.

Try to generalize this.

2) After sorting edges, Kruskal performs |E| union/find operations.
Using the relevant data structure (learned in the Data Structures course) we can do this in time $O(|E| \alpha(|E|,|V|))$, where $\alpha$ is the inverse Ackermann function, a very slowly growing function.

Normally, the $O(|E|\log(|V|))$ overhead of sorting dominates the running time, but if you take this out of the equation, you're left with the slightly super-linear $O(|E| \alpha(|E|,|V|))$.

Nir (guest) 03 Sep 2012 15:13

Thanks!