נושא: אלגוריתמים

נשלח בתאריך: 21 October 2007 בשעה 12:24 | IP רשוּם

היי

אני מחפש אלגוריתם למציאה האם בגרף מסויים קיים string sink כלומר צומת בעלת in degree>=1 ו out degree=0.

הגרף מיוצג במטריצת סמיכויות, והסיבוכיות צריכה להיות לינארית (לא ריבועית למרות המטריצה...)

רעיון מישהו?

נשלח בתאריך: 21 October 2007 בשעה 13:40 | IP רשוּם

לינארית בתלות במה ? במס' הקדקודים ? במס' הקשתות ? בגודל המטריצה ?

בעקרון קל לתאר מקרה (כלומר גרף) שעבורו לא ניתן למצוא אם קיים sink כנ"ל ללא מעבר על כל המטריצה, למשל גרף שמטריצת הסמיכויות שלו היא כזאת:

במטריצה כנ"ל יש sink כזה אבל לא ניתן למצוא אותו ללא מעבר על כל המטריצה.

האם ידוע משהו נוסף על הגרף (למשל קשירות) ?

נשלח בתאריך: 22 October 2007 בשעה 16:19 | IP רשוּם

בתלות במס הקודקודים.

ניתן גם להניח שאין בגרף מעגלים עצמיים ואין קשר דו כיווני בין אף זוג קודקודים..

גם אני לא מוצא דרך בה האלגוריתם לא יעבור על כל המטריצה במקרי קיצון