נושאים פעיליםנושאים פעילים  הצגת רשימה של חברי הפורוםרשימת משתמשים  חיפוש בפורוםחיפוש  עזרהעזרה
  הרשמההרשמה  התחברותהתחברות RSS עדכונים
מדעי המחשב
RSS UnderWarrior Forums : RSS מדעי המחשב
נושא

נושא: שאלה בגרפים

 שליחת תגובהשליחת נושא חדש
כותב
הודעה << נושא קודם | נושא הבא >>
אורח
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 15 January 2008 בשעה 12:02 | IP רשוּם
ציטוט אורח

גרף נקרא כמעט ללא מעגלים אם הוא ללא מעגלים, או שהסרה של קשת אחת תהפוך אותו לגרף ללא מעגלים.

נתון גרף מכוון, צריך למצוא אלגוריתם לינארי שבודק אם הגרף הוא כמעט ללא מעגלים.
חזרה לתחילת העמוד הצג את כרטיס החבר של אורח חפש הודעות אחרות של אורח בקר בדף הבית של אורח
 
צחי@
משתמש חבר
משתמש חבר


הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
נשלח בתאריך: 15 January 2008 בשעה 19:50 | IP רשוּם
ציטוט צחי@
תיקח את אלגוריתם DFS ותבצע בו שינויים:

1. אם בשלב ה-visit הגעת לקדקוד "אפור", כלומר, קדקוד שביקרת בו אבל לא סיימת לבקר בכל הקדקודים שניתן להגיע אליהם ממנו, זאת אומרת שהקשת שעליה עברת בשביל להגיע אליו סוגרת מעגל.

2. במקרה שאתה נתקל במקרה כזה, תגדיל מונה מסויים ב-1 (ערך התחלתי של המונה הוא 0).

3. אם המונה הגיע לערך גדול מ-1, ז"א שהגרף אינו "כמעט ללא מעגלים".

שים לב שיש לבצע DFS חוזר על כל רכיבי הקשירות של הגרף במידה ונשארו כאלה.
DFS על גרף שמיוצג כרשימת סמיכויות יעילותו (O(V+E
חזרה לתחילת העמוד הצג את כרטיס החבר של צחי@ חפש הודעות אחרות של צחי@ בקר בדף הבית של צחי@
 
אורח
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 16 January 2008 בשעה 10:23 | IP רשוּם
ציטוט אורח

חשבתי על זה גם, אבל זה לא מכסה את כל המקרים.

לדוגמא עבור הגרף הזה זה לא עובד- http://www.upfree.net/9415100 למרות שהוא "כמעט ללא מעגלים".
חזרה לתחילת העמוד הצג את כרטיס החבר של אורח חפש הודעות אחרות של אורח בקר בדף הבית של אורח
 
צחי@
משתמש חבר
משתמש חבר


הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
נשלח בתאריך: 16 January 2008 בשעה 12:28 | IP רשוּם
ציטוט צחי@

צודק, אבל לדעתי אפשר לתקן זאת בקלות - ברגע שאתה מגלה סגירת מעגל, תמחוק את הקשת שסוגרת מעגל ותתחיל לבצע DFS מהתחלה.

אם תמצא מעגל נוסף, המשמעות היא שישנה יותר מקשת אחת שצריך למחוק כדי שהגרף יהיה ללא מעגלים, ולכן הגרף אינו "כמעט ללא מעגלים"

DFS * 2 עדיין לינארי ב-|V|+|E|

 
חזרה לתחילת העמוד הצג את כרטיס החבר של צחי@ חפש הודעות אחרות של צחי@ בקר בדף הבית של צחי@
 
אןרח
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 16 January 2008 בשעה 14:03 | IP רשוּם
ציטוט אןרח
זה לא בדיק נכון,כי הקשת שסוגרת מעגל -יכולה להיות כל קשת במעגל ולכן זה תלי מאיזה קודקוד אתה מתחיל את ה DFS , יכול להיות שתשרוף את הקשת שבכלל לא משותפת לשני המעגלים ואז אתה מגיע לתוצאה לא נכונה.
חזרה לתחילת העמוד הצג את כרטיס החבר של אןרח חפש הודעות אחרות של אןרח בקר בדף הבית של אןרח
 
אמיר
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 20 February 2008 בשעה 09:06 | IP רשוּם
ציטוט אמיר
אני צריך חומר על "בעיית הסוכן הנוסע"
חזרה לתחילת העמוד הצג את כרטיס החבר של אמיר חפש הודעות אחרות של אמיר בקר בדף הבית של אמיר
 
אמיר
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 20 February 2008 בשעה 09:07 | IP רשוּם
ציטוט אמיר

מי יכול לעזור לי בבקשה,אני צריך חומר על נושא "בעיית הסוכן הנוסע",

תודה 
חזרה לתחילת העמוד הצג את כרטיס החבר של אמיר חפש הודעות אחרות של אמיר בקר בדף הבית של אמיר
 

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

  שליחת תגובהשליחת נושא חדש
גרסת הדפסה גרסת הדפסה

קפיצה לפורום
אינך יכול/ה לשלוח נושאים חדשים בפורום זה
אינך יכול/ה להגיב לנושאים בפורום זה
אינך יכול/ה למחוק את הודעותיך ותגוביך בפורום זה
אינך יכול/ה לערוך את הודעותיך ותגובותיך בפורום זה
אינך יכול/ה לצור סקרים בפורום זה
אינך יכול/ה להצביע בסקרים בפורום זה