ש"ב 2 , שאלות 4 ו-8

ש"ב 2 , שאלות 4 ו-8

denisg 09 Nov 2013 19:27

היי,
1. הניסוח בשאלה 4 לא ברור כל כך, מה צריך למצוא בשאלה (מה זה מינימום על קבוצה)
2. בשאלה 8 כשמבקשים סיבוכיות לינארית, הכוונה O(|V|+|E|)?

תודה

Re: ש"ב 2 , שאלות 4 ו-8

Shai V 09 Nov 2013 19:47

1. The minimum of a group is the smallest element in the group. In this case we identify each vertex with a number between 1 and $|V|$. We are asking for the vertex with the smallest number out of the group $R(v)$.

2. Yes, whenever we say "linear" in this course, we always mean $O(|V|+|E|)$.

Re: ש"ב 2 , שאלות 4 ו-8

Oren Magen 17 Nov 2013 09:08

Hey Shai, It's not clear to me though how the vertices are numbered - are they numbered by any pattern? or randomly ?

Re: ש"ב 2 , שאלות 4 ו-8

Shai V 17 Nov 2013 14:51

The numbering of the vertices is part of the input.

Re: ש"ב 2 , שאלות 4 ו-8

Oren Magen 17 Nov 2013 16:03

I mean: What does the numbering dictates? some order? if I'm at vertex 4 for example, I can only go to vertices 5 till n now? and if so, what if there are no arches to this direction?

Re: ש"ב 2 , שאלות 4 ו-8

Shai V 17 Nov 2013 20:47

You are given a directed graph G=(V,E), and some numbering on the vertices. The numbering is arbitrary. If you can reach vertices 5,8 and 123 from vertex $10$, then $\rho(10)=5$.