[-] A hint for Q4d.
by abuaffas - Saturday, 20 June 2009 20:19:53

A graph G is a single-path graph iff the graph GSCC of G is a single-path graph.
In addition, GSCC is a single-path graph iff it satisfies the conditions in part A and part B and each component Ci of GSCC satisfies the condition in part C.

thread
[-] Re: A hint for Q4d.
by roeih - Tuesday, 23 June 2009 18:24:45
why not use only the algorithm in part a if we know that G-SCC is directed and without circles?
thread
[-] Re: A hint for Q4d.
by eial - Tuesday, 23 June 2009 19:20:52
because by it's definition, a GSCC graph has a circle because if not, then you could not reach all vertexs from every vertex.
thread
[-] Re: A hint for Q4d.
by binenboi - Tuesday, 23 June 2009 19:29:52
You don't know that you can reach all vertexs from every vertex. If it was the situation than the  GSCC  was one vertex and you could do DFS-visit on any vertex and check if you got forward-edjes/צלעות חוצות
רגע למה אנחנו כותבים באנגלית בכלל?
thread
Re: A hint for Q4d.
by eial - Tuesday, 23 June 2009 19:49:37
check the graph's definition here
btw, do we need to prove the algorithm in 4d or just show it like in 3e?
thread
[-] Re: A hint for Q4d.
by roeih - Tuesday, 23 June 2009 19:47:05
אתה טועה, בתרגול 7 הוכחנו משפט שאומר כי גרף רכיבים קשירים היטב הינו חסר מעגלים
thread
Re: A hint for Q4d.
by binenboi - Tuesday, 23 June 2009 20:09:10
זה גם מה שכתוב בקישור לויקיפדיה ונראה לי שכן צריך להוכיח
thread
Re: A hint for Q4d.
by eial - Tuesday, 23 June 2009 20:45:10
גרף רכיבים קשירים חסר מעגלים, כי אתה ממיר כל רכיב קשירות לקודקוד
גרף קשיר היטב הוא גרף בעל רכיב קשירות אחד
thread
[-] Re: A hint for Q4d.
by keinanh - Tuesday, 23 June 2009 21:33:32
האם יש צורך להוכיח את הרמז הנתון? נראה כי המקום לכתיבת הפיתרון לא מאפשר זאת...
thread
Re: A hint for Q4d.
by abuaffas - Tuesday, 23 June 2009 22:06:52
You don't need to prove the hint.
You don't need to prove the algorithm correctness. Running time analysis is only required.
thread