שאלות באלגוריתמים על גרפים.

[ron369]

עברת על כל הש"ב של הטכניון?!

משקיע הסמסטר אתה, הא...

 

[yuvalmadar]

הורדתי, לא עברתי ../images/Emo3.gif

אבל בזמן הבחינה היה לי זמן לעבור על טונות חומר העזר שלי, וראיתי את זה שם.

(כמה התלהבתי למצוא את זה! רק כדי לגלות שאין פתרון ואין לי שום מושג למה הבאתי את זה לבחינה בכלל

)

 

[ron369]

איזה מעצבן ../images/Emo4.gif

גם לי היה את זה באיזה מבחן, אם אני לא טועה. *אנחה*

 

[gil levi]

אם אתה רוצה אני יכול לשלוח לך במייל

המון תרגילים. הורדתי תרגילים ופתרונות באלגוריתמים משני קורסים שונים (כלומר שניתנו בסמסטרים שונים), לא כולל את זה שאני עושה עכשיו.

 

[yuvalmadar]

של איזה אוני'?

בכל מקרה, תשלח גם לי בבקשה.

Yuvalm2 /שטרודל/ gmail /נקודה/ com​

(מנסה להתחמק מבוטים

)

 

[gil levi]

את"א.

שלחתי. כאן: http://www.math.tau.ac.il/~veraa/efficiency06b/efficiency.html יש עוד שני דפי תרגיל אבל עם פתרונות רק לראשון.

 

[yuvalmadar]

תודה לך! ../images/Emo13.gif

 

[ron369]

אולי פשוט תעלה הכל? ../images/Emo13.gif

ואם לא, אז אתה יכול לשלוח לי ל:

[email protected]​

? (תודה)

 

[gil levi]

אני חושב שאני אעלה את זה

בשרשור נפרד, אבל לא היום. שלחתי לך למייל.

 

[ron369]

תודה ../images/Emo13.gif

(ביום חמישי המבחן

)

 

[gil levi]

בהצלחה!

 

[gil levi]

שאלה לשניכם (רון ויובל).

אז איך הרמה של התרגילים?

 

[yuvalmadar]

האמת היא שלא יצא לי לעבור עליהם ../images/Emo13.gif

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

 

[ron369]

לא יודע עדיין, רציתי להתחיל ללמוד,

אבל יש לי פרוייקט ב-C שלא מסתיים (אמרתי 3000 שורות קוד כבר? תגמר!!!!!!!!!!!!!!!!!!!!!!). אבל אני מניח שאחרי אלגוריתמים אני ארגיש יותר טוב. אחרי משהוא טכני אימים, משהוא רחוק מלהיות טכני כמו... רחוק מאד. אין לי כוח לחשוב על אסוציאציה

 

[gil levi]

נו, איך היה המבחן?

זה היה אתמול, לא?

 

[yuvalmadar]

אני חושב שהלך לי די טוב ../images/Emo13.gif

בנוגע לרון, אתן לו לספר מה קרה.

 

[yuvalmadar]

שאלה קצת נדושה, אבל בכל מקרה ../images/Emo13.gif

הוכח/הפרך כל טענה - 1. (u,v) גשר => u או v צמתי הפרדה. 2. u צמת הפרדה => כל קשת מהצורה (u,v) או (v,u) היא גשר.

 

[vinney]

נו באמת, יובל

1. מה קורה כשמנתקים גשר? 2. האם כל הגרפים בעולם הם מצורת שרוך?

 

[yuvalmadar]

אמרתי שהיא נדושה ../images/Emo9.gif

אז אני לא יצירתי, תתבע אותי!

 

[yuvalmadar]

לא שהבנתי את התשובות שלך, אגב ../images/Emo13.gif

אני הסתפקתי בדוגמאות נגדיות ספציפיות.

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